An integer optimality condition for column generation on zero–one linear programs
| Autor: | Elina Rönnberg, Torbjörn Larsson |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Linear programming Beräkningsmatematik 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Column generation Integer programming Mathematics Optimality conditions 021103 operations research Applied Mathematics Zero (complex analysis) Computational mathematics Zero–one linear programming Dual (category theory) Linear programming relaxation Computational Mathematics Integer linear programming Discrete optimisation Computational Theory and Mathematics 010201 computation theory & mathematics Integer (computer science) |
| Zdroj: | Discrete Optimization. 31:79-92 |
| ISSN: | 1572-5286 |
| DOI: | 10.1016/j.disopt.2018.09.001 |
| Popis: | Column generation is a linear programming method that, when combined with appropriate integer programming techniques, has been successfully used for solving huge integer programs. The method alternates between a restricted master problem and a column generation subproblem. The latter step is founded on dual information from the former one; often an optimal dual solution to the linear programming relaxation of the restricted master problem is used. We consider a zero–one linear programming problem that is approached by column generation and present a generic sufficient optimality condition for the restricted master problem to contain the columns required to find an integer optimal solution to the complete problem. The condition is based on dual information, but not necessarily on an optimal dual solution. It is however most natural to apply the condition in a situation when an optimal or near-optimal dual solution is at hand. We relate our result to a few special cases from the literature, and make some suggestions regarding possible exploitation of the optimality condition in the construction of column generation methods for integer programs. Funding agencies Swedish Research Council [621-2005-2874] |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect