Wang Rui, Zhang Chuwen, Pu Shanwen, Gao Jianjun, Wen Zaiwen
IEEE Trans Pattern Anal Mach Intell. 2024 Dec;46(12):9439-9455. doi: 10.1109/TPAMI.2024.3416514. Epub 2024 Nov 6.
Integer programming with block structures has received considerable attention recently and is widely used in many practical applications such as train timetabling and vehicle routing problems. It is known to be NP-hard due to the presence of integer variables. We define a novel augmented Lagrangian function by directly penalizing the inequality constraints and establish the strong duality between the primal problem and the augmented Lagrangian dual problem. Then, a customized augmented Lagrangian method is proposed to address the block-structures. In particular, the minimization of the augmented Lagrangian function is decomposed into multiple subproblems by decoupling the linking constraints and these subproblems can be efficiently solved using the block coordinate descent method. We also establish the convergence property of the proposed method. To make the algorithm more practical, we further introduce several refinement techniques to identify high-quality feasible solutions. Numerical experiments on a few interesting scenarios show that our proposed algorithm often achieves a satisfactory solution and is quite effective.
具有块结构的整数规划近年来受到了广泛关注，并被广泛应用于许多实际问题，如列车时刻表编排和车辆路径规划问题。由于存在整数变量，它被认为是NP难问题。我们通过直接惩罚不等式约束来定义一种新颖的增广拉格朗日函数，并建立了原问题与增广拉格朗日对偶问题之间的强对偶性。然后，提出了一种定制的增广拉格朗日方法来处理块结构。特别地，通过解耦连接约束将增广拉格朗日函数的最小化分解为多个子问题，并且可以使用块坐标下降法有效地求解这些子问题。我们还建立了所提方法的收敛性质。为了使算法更具实用性，我们进一步引入了几种改进技术来识别高质量的可行解。在一些有趣场景下的数值实验表明，我们提出的算法通常能获得令人满意的解，并且相当有效。
