Nested Set-Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization

• 成果类型: Article; Early Access
• 署名作者: Guo, Siqi; Xiao, Fan; Liang, Zhe
• 署名单位: Tongji University; Shanghai University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.0720
• 发表日期: 2025
• 关键词: branch-and-price; Column Generation; dynamic constraint; linear-programs; algorithms; row; aggregation; DECOMPOSITION; inequalities

摘要

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.