Retour

G-2015-44

Integral simplex using decomposition with primal cutting planes

, , et

référence BibTeX

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

Axes de recherche

Application de recherche

Publications

, , et
Experimental Algorithms, 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 – July 1, 2014. Proceedings, Lectures Notes in Computer Science, 8504, 22–33, 2014 référence BibTeX