All-integer column generation for set partitioning: Basic principles and extensions
E Rönnberg, T Larsson - European Journal of Operational Research, 2014 - Elsevier
European Journal of Operational Research, 2014•Elsevier
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 …
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 …
Abstract
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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果