Integral Simplex Using Decomposition for the Set Partitioning Problem

Abdelouahab Zaghrouti (), François Soumis () and Issmail El Hallaoui ()
Additional contact information
Abdelouahab Zaghrouti: Département de Mathématiques et Génie Industriel, GERAD, and Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada
François Soumis: Département de Mathématiques et Génie Industriel, GERAD, and Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada
Issmail El Hallaoui: Département de Mathématiques et Génie Industriel, GERAD, and Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada

Operations Research, 2014, vol. 62, issue 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: integral simplex; set partitioning problem; decomposition (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1247 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:2:p:435-449

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().