Back

G-2013-79

Integral simplex using decomposition with primal cuts

, , , and

BibTeX reference

The integral simplex using decomposition (ISUD) algorithm [Zaghrouti, A., Soumis, F., Elhallaoui, I.: Integral simplex using decomposition for the set partitioning problem. Accepted for publication. Operations Research (2013)] is a dynamic constraint reduction method that aims to solve the popular set partitioning problem (SPP). It is a special case of primal algorithms, i.e. algorithms that furnish an improving sequence of feasible solutions based on the resolution, at each iteration, of an augmentation problem that either determines an improving direction, or asserts that the current solution is optimal. To show how ISUD is related to primal algorithms, we introduce a new augmentation problem, MRA. We show that MRA canonically induces a decomposition of the augmentation problem and deepens the understanding of ISUD. We characterize cuts that adapt to this decomposition and relate them to primal cuts. These cuts yield a major improvement over ISUD, making the mean optimality gap drop from 33.92% to 0.21% on some aircrew scheduling problems.

, 13 pages

This cahier was revised in January 2016

Research Axis

Publication

, , , and
Experimental Algorithms, Lecture Notes in Computer Science, 8504, Springer International Publishing, 22–33, 2014 BibTeX reference

Document

G1379R.pdf (400 KB)