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 large-scale 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; OR-Library 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.90064Zaghrouti, Abdelouahab; Soumis, François; El Hallaoui, Issmail 2014 all top 5 Cited by 25 Authors 8 Elhallaoui, Issmail 7 Soumis, François 3 Desaulniers, Guy 3 Rosat, Samuel 3 Zaghrouti, Abdelouahab 2 Desrosiers, Jacques 2 Foutlane, Omar 2 Gauthier, Jean-Bertrand 2 Hansen, Pierre 2 Lübbecke, Marco E. 1 Bock, Stefan 1 Bouarab, Hocine 1 Chakour, Driss 1 Contardo, Claudio 1 Costa, Luciano da Fontoura 1 Kuschel, Torben 1 Larsson, Torbjörn 1 Lessard, François 1 Lodi, Andrea 1 Maher, Stephen J. 1 Quesnel, Frédéric 1 Rönnberg, Elina 1 Saddoune, Mohammed 1 Witt, Jonas T. 1 Yarkony, Julian all top 5 Cited in 11 Serials 4 European Journal of Operational Research 2 SN Operations Research Forum 1 Discrete Applied Mathematics 1 Operations Research 1 Operations Research Letters 1 Computers & Operations Research 1 Annals of Operations Research 1 Mathematical Programming. Series A. Series B 1 INFORMS Journal on Computing 1 Discrete Optimization 1 EURO Journal on Computational Optimization Cited in 4 Fields 15 Operations research, mathematical programming (90-XX) 2 Combinatorics (05-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Numerical analysis (65-XX) Citations by Year