Column generation using non-optimal dual solutions: Optimality conditions and over-generation
(English)Manuscript (preprint) (Other academic)
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 use of a dual solution to the restricted master problem is essential when new columns are derived by solving a subproblem. Even if the problem to be solved is an integer programming one, this dual solution is usually optimal with respect to the linear programming relaxation of either the original problem or of a restriction thereof formed further down a branch-and-price-tree.
This paper addresses the situation that arises when columns of a binary problem are generated using any dual solution, and we derive optimality conditions for determining when the master problem has been augmented with enough columns to contain an integer optimal solution to the complete master problem.
We discuss the concept of over-generation of columns, which means to augment the restricted master problem with a set of columns, to ensure progress of the algorithm and also to make sure that the columns of the restricted master problem eventually comply with the optimality conditions. To illustrate the over-generation strategy, we compare our results with special cases that are already known from the literature, and we make some new suggestions.
Binary program, column generation, optimality conditions, overgeneration
IdentifiersURN: urn:nbn:se:liu:diva-76090OAI: oai:DiVA.org:liu-76090DiVA: diva2:512198