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.