Feasibility-Aware Imitation Learning for Benders Decomposition
作者: Bernard T. Agyeman, Zhe Li, Ilias Mitrai, Prodromos Daoutidis
分类: math.OC, eess.SY
发布日期: 2026-04-07
💡 一句话要点
提出可行性感知模仿学习框架，加速Benders分解求解混合整数优化问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: Benders分解 模仿学习 混合整数优化 可行性感知 智能体 控制应用
📋 核心要点
- Benders分解在求解混合整数优化问题时，计算瓶颈在于迭代求解复杂度不断提升的主问题。
- 论文提出可行性感知模仿学习框架，预测主问题整数变量，并结合可行性割集进行约束。
- 实验结果表明，该方法在保证解的精度的前提下，能够有效减少求解时间，优于现有模仿学习方法。
📝 摘要（中文）
混合整数优化问题广泛存在于控制应用中。Benders分解是一种常用的求解此类问题的算法，它将问题分解为一个混合整数主问题和一个连续子问题。一个关键的计算瓶颈是迭代过程中重复求解日益复杂的主问题。本文提出了一种可行性感知模仿学习框架，用于预测每次迭代中主问题的整数变量的值，同时考虑关于容许整数分配的约束以及累积的Benders可行性割。该智能体使用两阶段程序进行训练，该程序将行为克隆与基于可行性的logit调整相结合，以使预测偏向于满足不断发展的割集的分配。该智能体部署在基于智能体的Benders分解框架中，该框架将显式可行性检查与有时限的求解器计算有效下界相结合。所提出的方法保留了有限收敛性质，因为在每次迭代中都会验证下界。对一个典型的案例研究的应用表明，所提出的方法相对于现有的用于加速Benders分解的模仿学习方法，提高了求解时间，同时保持了求解精度。
🔬 方法详解
问题定义：Benders分解是一种求解混合整数优化问题的常用方法，但其迭代过程中需要重复求解复杂度不断增加的混合整数主问题，这成为了计算瓶颈。现有方法，如直接使用混合整数规划求解器，计算成本高昂。而传统的模仿学习方法可能难以保证解的可行性，导致算法收敛速度慢甚至无法收敛。
核心思路：论文的核心思路是利用模仿学习来预测主问题的整数变量，从而避免每次迭代都从头开始求解复杂的混合整数规划问题。同时，为了保证解的可行性，论文提出了可行性感知的训练方法，将可行性割的信息融入到模仿学习的过程中，引导智能体学习到满足约束的解。
技术框架：整体框架是一个基于智能体的Benders分解流程。首先，使用模仿学习智能体预测主问题的整数变量。然后，进行显式可行性检查，验证预测的解是否满足约束。如果解不可行，则使用有时限的求解器计算一个有效的下界。最后，将新的可行性割添加到割集中，并重复上述步骤，直到找到最优解。该框架结合了模仿学习的快速预测能力和传统Benders分解的收敛保证。
关键创新：最重要的创新点在于可行性感知的模仿学习训练方法。传统的模仿学习方法通常只关注行为的模仿，而忽略了解的可行性。论文提出的方法通过两阶段训练过程，将可行性信息融入到模仿学习的过程中。第一阶段使用行为克隆进行初步训练，第二阶段使用基于可行性的logit调整，对预测结果进行修正，使其更倾向于满足可行性割。
关键设计：两阶段训练过程是关键设计。第一阶段，使用行为克隆，通过最小化预测动作与专家动作之间的交叉熵损失来训练智能体。第二阶段，引入基于可行性的logit调整。具体来说，对于每个可能的整数变量赋值，计算其违反可行性割的程度，并根据违反程度调整logit值。logit调整的目的是降低违反可行性割的赋值的概率，从而引导智能体学习到满足约束的解。此外，使用有时限的求解器计算下界，保证了算法的收敛性。
🖼️ 关键图片
📊 实验亮点
实验结果表明，所提出的可行性感知模仿学习方法能够有效加速Benders分解的求解过程。在典型的案例研究中，该方法相对于现有的模仿学习方法，在保证解的精度的前提下，显著减少了求解时间。具体性能提升数据未知，但论文强调了其优于现有模仿学习方法的加速效果。
🎯 应用场景
该研究成果可应用于各种涉及混合整数优化的控制应用，例如电力系统优化、供应链管理、生产调度等。通过加速Benders分解的求解过程，可以更高效地解决这些实际问题，降低计算成本，提高决策效率。未来，该方法可以进一步扩展到更复杂的优化问题，并与其他优化算法相结合，以获得更好的性能。
📄 摘要（原文）
Mixed-integer optimization problems arise in a wide range of control applications. Benders decomposition is a widely used algorithm for solving such problems by decomposing them into a mixed-integer master problem and a continuous subproblem. A key computational bottleneck is the repeated solution of increasingly complex master problems across iterations. In this paper, we propose a feasibility-aware imitation learning framework that predicts the values of the integer variables of the master problem at each iteration while accounting for feasibility with respect to constraints governing admissible integer assignments and the accumulated Benders feasibility cuts. The agent is trained using a two-stage procedure that combines behavioral cloning with a feasibility-based logit adjustment to bias predictions toward assignments that satisfy the evolving cut set. The agent is deployed within an agent-based Benders decomposition framework that combines explicit feasibility checks with a time-limited solver computation of a valid lower bound. The proposed approach retains finite convergence properties, as the lower bound is certified at each iteration. Application to a prototypical case study shows that the proposed method improves solution time relative to existing imitation learning approaches for accelerating Benders decomposition, while preserving solution accuracy.