报告题目：Nested Set Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization

报告简介：It is widely acknowledged that deep dual-optimal inequalities (DDOIs) (Ben Amor et al. 2006) can stabilize the dual of a linear programming problem and accelerate convergence. However, we find that adding DDOIs 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 stabilize the dual on the one hand while reducing the primal degeneracy on the other hand. In this paper, we study a nested multi-stage set covering problem, in which the results of the previous stage become the entities that comprise the next stage decisions. We propose a nested set covering model, which can be viewed as a traditional set covering problem with DDOIs. Different from the standard DDOIs, this new type also increases the dimension of the dual problem, and we herein name it as Lift-DDOIs. Furthermore, we demonstrate that a large number of DDOIs/Lift-DDOIs could 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 take advantages of both dual stabilization and degeneracy alleviation. We also demonstrate the above findings and methods can be adapted to the set packing problem. A comprehensive computational study on the airline crew scheduling problem shows that the proposed Lift-DDOIs and the column-and-row generation algorithm with pruning and-pricing mechanism can reduce the solution time by an average of 73.52% compared to a standard column generation approach for traditional set covering problems.

主讲人简介：梁哲，国家杰青、首届国家杰青延续项目获得者，同济大学教授。理论研究主要集中在大规模组合优化、整数规划领域；应用研究主要集中在交通、物流特别是航空运营管理领域。在管理科学和交通领域期刊INFORMS Journal on Computing, Transportation Science, European Journal of Operational Research 等发表论文40余篇。团队研发的多个智能航空运营决策系统已经在10余家航司和机场应用，产生了较好的经济效益。