All-integer column generation for set partitioning: Basic principles and extensions

作者：Ronnberg Elina^*; Larsson Torbjorn

来源：European Journal of Operational Research, 2014, 233(3): 529-538.

DOI：10.1016/j.ejor.2013.08.036

• Integer programming
• Column generation
• Set partitioning
• Quasi-integrality
• All-integer pivots

Column generation, combined with an appropriate integer programming technique, has shown to be a powerful tool for solving huge integer programmes arising in various applications. In these column generation approaches, the master problem is often of a set partitioning type.
The set partitioning polytope has the quasi-integrality property, which enables the use of simplex pivots for finding improved integer solutions, each of which is associated with a linear programming basis. By combining such pivots with column generation, one obtains a method where each found solution to a restricted master problem is feasible, integer, and associated with a dual solution that can be used in a column generation step.
This paper presents a framework for such an all-integer column generation approach to set partitioning problems. We give the basic principles of all-integer pivots and all-integer column generation. We also state optimality conditions and introduce means for preserving a basis in the event that a heuristic is applied to the master problem. These extensions introduce flexibility in the design of a specific solution scheme of this kind, and with proper settings optimal or approximate solutions can be sought for.

• 出版日期2014-3-16