Groupe d’études et de recherche en analyse des décisions

G-2015-44

Integral simplex using decomposition with primal cutting planes

, , et

We propose a primal algorithm for the Set Partitioning Problem based on the Integral Simplex Using Decomposition of Zaghrouti et al. (2014). We present the algorithm in a pure primal form, and relate it to other augmenting methods. We show that cutting planes can be transferred to the complementary problem, and we characterize the set of transferable cuts as a nonempty subset of primal cuts that are tight to the current solution. We prove that these cutting planes always exist, we propose efficient separation procedures for primal clique and odd-cycle cuts, and prove that their search space can be restricted to a small subset of the variables making the computation efficient. Numerical results demonstrate the effectiveness of adding cutting planes to the algorithm; tests are performed on small and large-scale set partitioning problems from aircrew and bus-driver scheduling instances up to 1,600 constraints and 570,000 variables.

, 33 pages