.png){kind=icon}
.png){kind=icon}
Return
All-integer column generation for set partitioning: Basic principles and extensions
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2013.08.036.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2013 Elsevier B.V. All rights reserved.
Keywords:
Integer programming
Column generation
Set partitioning
Quasi-integrality
All-integer pivots
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W