EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3143. Construction of value functions of integer programs with finite domain
Invited abstract in session WB-25: Topics in Integer Programming II, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Junlong Zhang
|
| Industrial Engineering, Tsinghua University |
Abstract
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. We propose a column-by-column algorithm for constructing the value functions of integer programs with finite domain over the set of so-called level-set minimal vectors. The proposed algorithm starts with the first column and sequentially adds the rest columns one by one. The advantage is that no integer program needs to be solved in the algorithm and no dominated vectors are generated (only level-set minimal vectors are generated). Computational results on benchmark instances show that the proposed algorithm can reduce the computation time by 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.
Keywords
- Programming, Integer
Status: accepted
Back to the list of papers