ISUD
swMATH ID:  34491 
Software Authors:  Zaghrouti, Abdelouahab; Soumis, François; El Hallaoui, Issmail 
Description:  ISUD: Integral simplex using decomposition for the set partitioning problem. 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. E. Balas and M. W. Padberg [Oper. Res. 20, 1152–1161 (1972; Zbl 0254.90035)] 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 largescale problems (with up to 500,000 variables) for which optimal integer solutions are often obtained without any branching. 
Homepage:  https://pdfs.semanticscholar.org/4f77/1677fc174992b95d1d4e0bd4aa794aaa9bf9.pdf 
Related Software:  DeeperCut; GCG; SCIP; CPLEX; ORLibrary 
Cited in:  15 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Integral simplex using decomposition for the set partitioning problem. Zbl 1295.90064 Zaghrouti, Abdelouahab; Soumis, François; El Hallaoui, Issmail 
2014

all
top 5
Cited by 25 Authors
all
top 5
Cited in 11 Serials
Cited in 4 Fields
15  Operations research, mathematical programming (90XX) 
2  Combinatorics (05XX) 
1  Linear and multilinear algebra; matrix theory (15XX) 
1  Numerical analysis (65XX) 