689 / 2024-05-10 22:27:12

Nested Set Covering/Packing Problem: Degeneracy Detection and Dual Stabilization

Set covering/packing problem; DDOI; Dual stabilization; Degeneracy; Airline crew scheduling

It is widely acknowledged that deep dual-optimal inequalities (DDOIs) can stabilize the dual of a linear programming problem and accelerate the computational process. However, we find that DDOI is not a free lunch but always comes with a price, that is, it will increase the primal degeneracy. As a result, when addressing a linear programming problem, it is critical to stablize the dual on the one hand while reducing the primal degeneracy on the other hand. In this paper, we study a nested set covering problem with multiple stages, in which the results of the previous stage become the elements that comprise the next stage decisions. This problem can be formulated as a set covering model with DDOIs. We prove that the standard reduced costs computed from the dual of DDOI-enhanced model can lead to degenerate variables and pivots. To resolve this issue, we propose strengthened reduced costs that can prescreen and prune degenerate variables, thereby improving solution efficiency. We also demonstrate the above findings can be adapted to the set packing problem. Furthermore, we develop a nested column-and-row generation algorithm to solve the proposed models, and conduct a computational study on the airline crew scheduling problem. The experiments show the effectiveness of DDOIs and strengthened reduced costs on degeneracy detection and dual stabilization.