Nested Set-Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization
研究嵌套多阶段集合覆盖问题，提出一种嵌套列行生成算法，通过强化简约成本预剪枝退化变量，同时缓解原始退化并稳定对偶值，加速线性规划求解。
Stabilize the Dual Value and Alleviate the Primal Degeneracy of Linear Programs Simultaneously Dual-optimal and deep dual-optimal inequalities (DOIs/DDOIs) are known to aid dual stabilization and accelerate convergence. In “Nested Set-Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization,” Siqi Guo, Fan Xiao, and Zhe Liang observe that DOIs/DDOIs also increase primal degeneracy, thereby extra effort is needed to prove optimality. Therefore, when addressing linear programs, it is critical to stabilize the dual as well as reduce primal degeneracy. This paper studies a nested multistage set-covering problem and proposes a nested set-covering model, which can be viewed as a traditional set-covering problem with special DDOIs. The authors 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 the benefits of both dual stabilization and degeneracy alleviation.