Nested Set-Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization
Operations Research · 2025 · Volume 73 · Issue 6
Abstract
It is widely acknowledged that deep dual-optimal inequalities (DDOIs) can stabilize the dual of a linear programming problem and accelerate its convergence. However, we find that adding DDOIs is not free but always comes with a price; that is, it increases the number of primal degenerate bases, and extra effort might be needed to achieve dual feasibility and prove its optimality. As a result, when addressing a linear programming problem, it is critical to stabilize the dual on the one hand, reducing primal degeneracy on the other hand. In this paper, we study a nested multistage set-covering problem in which the results of the previous stage become the entities that make up the next stage decisions. We propose a nested set-covering model (NCM), which can be viewed as a traditional set-covering problem with DDOIs. Unlike the standard DDOIs, this new type of DDOI also increases the dimension of the dual problem, and we refer to it herein as Lift-DDOI. Furthermore, we demonstrate that introducing a large number of DDOIs/Lift-DDOIs may exacerbate the problem degeneracy. To resolve this issue, we derive strengthened reduced costs that can prescreen and prune degenerate variables and a pruning-and-pricing mechanism that utilizes both standard and strengthened reduced costs to price out promising variables. An efficient nested column-and-row generation algorithm is developed to exploit both the dual stabilization and degeneracy alleviation effects. We also demonstrate that the above findings and methods can be adapted to nested set-packing problems. A comprehensive computational study on the airline crew scheduling problem shows that the proposed Lift-DDOIs and the column-and-row generation algorithm with the pruning-and-pricing mechanism can reduce the solution time by an average of 71.43% compared with a standard column-generation approach for traditional set-covering problems. Funding: This research was supported by the National Natural Science Foundation of China [Grants 72425001, 72231006, 724B2025, and 72301165]. Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.0720 .
Keywords
Transportation, set covering/packing problem, deep dual-optimal inequality, dual stabilization, degeneracy, airline crew scheduling, column-and-row generation
Enable JavaScript for citation tools and additional paper interactions.