1867. The value function of a binary integer program
Invited abstract in session WB-17: Integer Programming, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Junlong Zhang
|
| Industrial Engineering, Tsinghua University |
Abstract
We investigate the value function of a binary integer program, which has received less attention in the literature than that of a general integer program. We find that some basic properties of the value function of a general integer program do not hold for the value function of a binary integer program, e.g., superadditivity and integer programming complementary slackness. Therefore, existing approaches for constructing integer programming value functions are not directly applicable to binary integer programs. In this study, we derive structural properties and propose a column-by-column algorithm and also a merge algorithm to construct the value function of a binary integer program. We demonstrate and compare the performance of the two algorithms through extensive computational experiments. We also extend the proposed approach to solve a type of bilevel binary integer programs.
Keywords
- Combinatorial Optimization
- Programming, Integer
Status: accepted
Back to the list of papers