Integral Simplex Using Decomposition for the Set Partitioning Problem
Authors:
- 1 April 2014
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 62 (2) , 435-449
Abstract
Since the 1970s, several authors have studied the structure of the set partitioning polytope and proposed adaptations of the simplex algorithm that find an optimal solution via a sequence of basic integer solutions. Balas and Padberg in 1972 proved the existence of such a sequence with nonincreasing costs, but degeneracy makes it difficult to find the terms of the sequence. This paper uses ideas from the improved primal simplex to deal efficiently with degeneracy and find subsequent terms in the sequence. When there is no entering variable that leads to a better integer solution, the algorithm referred to as the integral simplex using decomposition algorithm uses a subproblem to find a group of variables to enter into the basis in order to obtain such a solution. We improve the Balas and Padberg results by introducing a constructive method that finds this sequence by only using normal pivots on positive coefficients. We present results for large-scale problems (with up to 500,000 variables) for which optimal integer solutions are often obtained without any branching.Keywords
This publication has 9 references indexed in Scilit:
- An Improved Primal Simplex Algorithm for Degenerate Linear ProgramsINFORMS Journal on Computing, 2011
- Column generation decomposition with the degenerate constraints in the subproblemEuropean Journal of Operational Research, 2010
- A new version of the Improved Primal Simplex for degenerate linear programsComputers & Operations Research, 2010
- Column generation in the integral simplex methodEuropean Journal of Operational Research, 2009
- Multi-phase dynamic constraint aggregation for set partitioning type problemsMathematical Programming, 2008
- An Integral Simplex Algorithm for Solving Combinatorial Optimization ProblemsComputational Optimization and Applications, 2002
- The integral basis method for integer programmingMathematical Methods of Operations Research, 2001
- On the Set-Covering Problem: II. An Algorithm for Set PartitioningOperations Research, 1975
- On the Set-Covering ProblemOperations Research, 1972