Integral Simplex Using Decomposition for the Set Partitioning Problem

Since the 1970's, 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. The existence of such a sequence with non-increasing costs was proved by [Balas, E., M.W. Padberg. 1972. On the set-covering problem. Operations Research 20(6) 1152-1161.] but degeneracy makes it difficult to find the terms of the sequence. This paper uses ideas from the improved primal simplex [Elhallaoui, I., A. Metrane, G. Desaulniers, F. Soumis. 2011. An improved primal simplex algorithm for degenerate linear programs. INFORMS Journal on Computing 23(4) 569-577.] 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.