Logic Based Benders Decomposition

The classical Benders Decomposition method decomposes a problem into two loosely connected subproblems. It enumerates values for the connecting variables. For each set of values enumerated, it solves the subproblem that results from fixing the connecting variables to these values. The solution of the subproblem generates a Benders cut that the connecting variables must satisfy in all subsequent solutions enumerated.

The process continues until the master problem and subproblem converge providing the same value. The classical Benders approach, however, requires that the subproblem is a continuous linear or nonlinear programming problem.

Logic-Based Benders Decomposition LBBD is an extension of the tranditional scheme that enables generic solvers to be used as subproblem solvers.

We have applied LBDD to scheduling problems with alternative resources in the field of embedded system design. The structure of a solver exploits problem decomposition, where task to resource assignments influence the objective function and are performed via an Integer Linear Programming  (ILP) solver. The scheduling part (with fixed resources), instead, is better dealt with Constraint Programming (CP).

The figure depicts the overall process. Resource allocation is computed by optimizing the objective function. The valid allocation is passed to the scheduling component. If a schedule exist for such allocation, the process converges to the optimal solution. Otherwise a no good is generated (as a linear constraint) and passed to the resource allocation component.

Two aspects influence the overall process: (1) to avoid the generation of trivially infeasible solutions in the allocation part, the ILP model should embed a scheduling problem relaxation; (2) tight no-goods can heavily reduce the number of iterations of the overall solution process.

We have faced different problems with this structure: those where the objective function depends only on the resource allocation variables, and those where also scheduling decision impact the objective function. We have deeply investigated tight relaxation and tight cuts to speed up the solution process.