Construction of Value Functions of Integer Programs with Finite Domain

Value functions play a central role in integer programming duality, and they are also used to develop solution methods for stochastic integer programs, bilevel integer programs, and robust optimization problems. In this paper, we propose a column-by-column algorithm for constructing the value functions of integer programs with finite domain over the set of level-set minimal vectors. The proposed algorithm starts with the first column and sequentially adds the rest of the columns one by one. Each time a column is added, a new set of level-set minimal vectors is generated based on the previous set, and the optimal objective values over the level-set minimal vectors are also computed. The advantage of the proposed algorithm is that no integer program needs to be solved in the algorithm for instances with nonnegative constraint matrices. Computational results on benchmark instances show that the proposed algorithm can achieve a speedup of up to three orders of magnitude compared with a state-of-the-art algorithm. We also extend the proposed algorithm to build value functions of integer programs with negative elements in the constraint matrix.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.

Funding: This research was supported by the National Natural Science Foundation of China [Grants 72001125 and 72371140].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0757) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0757). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.