Indicator Cuts for Benders Decomposition with Mixed-Integer Subproblems

Classical Benders decomposition fails when the subproblem is a mixed-integer program, due to the absence of strong duality. We propose a novel class of dual-free indicator cuts that are applicable to all Benders-decomposable problems with a pure-integer master problem and mixed-integer linear programming (MILP) subproblems. These cuts are derived from the monotonicity property of the subproblem value function, allowing us to construct valid cuts without relying on duality. We also introduce a theoretical framework for comparing the effectiveness of different indicator cuts. This framework unifies several previously disconnected methods that exploit subproblem monotonicity. Two MILP formulations of the proposed cuts are developed, along with two implementation techniques to improve computational performance. The proposed method is tested on a multi-phase energy system design problem. Numerical results show that the indicator cuts significantly outperform CPLEX in both runtime and solution quality, and the empirical performance aligns with the theoretical predictions.

Article

Download

View PDF