Feasibility-Aware Imitation Learning for Benders Decomposition
This work addresses a specific bottleneck in optimization algorithms for control applications, representing an incremental improvement over prior imitation learning methods.
The paper tackles the computational bottleneck of repeatedly solving complex master problems in Benders decomposition for mixed-integer optimization by proposing a feasibility-aware imitation learning framework that predicts integer variable values while ensuring feasibility. The method improves solution time compared to existing imitation learning approaches while preserving accuracy, as shown in a case study.
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.