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.
Published November 2013 , 13 pages
This cahier was revised in January 2016