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.