Logic-based Benders Decomposition

The Logic-based Benders Decomposition (LBBD) [1] is a powerful generalization of the Benders Decomposition method. While classical Benders decomposition requires the subproblem to be LP and generalized Benders requires convexity, LBBD extends the framework to handle subproblems of any kind, including non-convex programming, Constraint Programming (CP), or problem-specific algorithms. The theory and its applications are detailed extensively in Hooker’s books [2] [3]. The core idea is to replace the concept of LP duality with inference duality. Instead of relying on a dual LP to generate cuts, LBBD uses a logical inference or a “proof” from the subproblem solver to derive logic-based Benders cuts.

Inference Duality

Consider a general optimization problem

\[\min_{x} \{ f(x) \mid \mathcal{C}(x), x \in \mathcal{D} \}\]

where \(f(x)\) is the objective function, \(\mathcal{C}(x)\) is the set of constraints, and \(\mathcal{D}\) is the domain of the variables. The inference dual [1] [2] [3] of this problem finds the best possible lower bound \(\beta\) on the objective value that can be inferred from the constraints.

\[\max_{\beta, P} \{ \beta \mid (\mathcal{C}(x), x \in \mathcal{D}) \vdash_P (f(x) \geq \beta) \}\]

The notation \(S \vdash_P L\) means that the statement \(L\) can be inferred from the set of premises \(S\) using a proof \(P\) from a specific proof system. The inference dual seeks the tightest lower bound \(\beta\) that can be deduced. A key result is that when we assume \(\infty\) objective values for infeasible problems and \(-\infty\) for unbounded ones, strong duality holds [1]: the optimal value of the original problem is equal to the optimal value of its inference dual.

LBBD Reformulation

LBBD addresses problems with the following structure, where variables are partitioned into master problem variables \(x\) and subproblem variables \(y\).

\[\begin{split}\begin{aligned} \min_{x, y} \quad & f(x, y) \\ \text{s.t.} \quad & \mathcal{C}(x, y) \\ & \mathcal{C}'(x) \\ & x \in \mathcal{D}_x \\ & y \in \mathcal{D}_y \end{aligned}\end{split}\]

When the master problem proposes a solution \(\bar{x}\), the following subproblem is solved.

\[\begin{split}\begin{aligned} \min_{y} \quad & f(\bar{x}, y) \\ \text{s.t.} \quad & \mathcal{C}(\bar{x}, y) \\ & y \in \mathcal{D}_y \end{aligned}\end{split}\]

The inference dual seeks the tightest possible lower bound \(\beta\) on the objective value that can be logically inferred from the subproblem’s constraints. For a given \(\bar{x}\), it is formulated as follows.

\[\begin{aligned} \max_{\beta, P} \{\beta \mid (\mathcal{C}(\bar{x}, y), y \in \mathcal{D}_y) \vdash_P (f(\bar{x}, y) \geq \beta)\} \end{aligned}\]

Here, \(\vdash_P\) indicates that the conclusion \(f(\bar{x}, y) \geq \beta\) is derivable from the subproblem constraints using a proof \(P\) from a specific inference system. Solving this dual yields an optimal lower bound \(\beta^*\), representing the strongest conclusion we can draw about the cost associated with the master decision \(\bar{x}\).

The Benders master problem is then formulated to find the best master variables \(x\) while respecting the information learned from previous iterations. Let \(\bar{x}^k\) be the master solution at iteration \(k\), and let \(B_{\bar{x}^k}(x)\) be the function representing the lower bound generated from that iteration’s subproblem. The master problem at iteration \(K\) becomes follows.

\[\begin{split}\begin{aligned} \min_{x, z} \quad & z \\ \text{s.t.} \quad & \mathcal{C}'(x) \\ & z \geq B_{\bar{x}^k}(x), \quad \forall k = 1, \dots, K \\ & x \in \mathcal{D}_x \end{aligned}\end{split}\]

The constraints \(z \geq B_{\bar{x}^k}(x)\) are the logic-based Benders cuts.

Note

Here we use \(z\) to represent the objective function of the master problem in consistency with Hooker’s notation [3]. However, The master problem objective can also be expressed using only terms with \(x\) in \(f(x, y)\), plus an estimator variable representing the subproblem’s contribution, similar to other Benders methods in this tutorial. BendersLib uses the latter internally.

Logic-based Benders Cuts

A key challenge in implementing LBBD is translating the general cut \(z \geq B_{\bar{x}^k}(x)\) from the master problem into a concrete mathematical constraint. Unlike the standard cuts in Classical Benders Decomposition, Combinatorial Benders Decomposition, L-shaped Method, or Integer L-shaped Method, logic-based Benders cuts are problem-specific.

Note

Hooker’s Book (Chapter 3) [3] summarized various forms of logic-based Benders cuts, including no-good cuts, analytical cuts, etc.

Example

When the expression \(B_{\bar{x}^k}(x)\) in the original cut \(z \geq B_{\bar{x}^k}(x)\) is replaced by \(\beta_k = B_{\bar{x}^k}(\bar{x}^k)\), the cut takes the following form.

\[(x = \bar{x}^k) \Rightarrow (z \geq \beta_k)\]

This is essentially the CombinatorialOC in Combinatorial Benders Decomposition and Integer L-shaped Method. It states that if the master problem again chooses the solution \(\bar{x}^k\), then the objective \(z\) must be at least the lower bound \(\beta_k\) that was inferred for this solution. This logical form can be directly translated into indicator constraints, which are supported by many modern mathematical programming solvers. It can be linearized using big-M formulations, which has been introduced in Combinatorial Benders Decomposition and Integer L-shaped Method.

\((x = \bar{x}^k) \Rightarrow (z \geq \beta_k)\) is presented here for illustrative purposes. It can be weaker than \(z \geq B_{\bar{x}^k}(x)\) because it only enforces the bound when \(x\) exactly matches \(\bar{x}^k\), providing no gradient information for other values of \(x\).

Depending on the subproblem outcome for a given \(\bar{x}^k\), the cut conveys different information.

• When the subproblem is feasible, an optimality cut of the form \(z \geq B_{\bar{x}^k}(x)\) is added. This informs the master problem of the cost consequence of repeating the decision \(\bar{x}^k\).

• When the subproblem is infeasible, the proof of infeasibility identifies a subset of decisions in \(\bar{x}^k\) that make subproblem infeasible. A feasibility cut (e.g., no-good cut) is generated to forbid this specific combination of critical decisions in future iterations.

The LBBD framework is particularly well-suited for problems involving integer variables in both the master and subproblems. When applying LBBD to stochastic programming problems, cuts are generated for each discrete scenario or aggregated for all scenarios, similar to L-shaped Method and Integer L-shaped Method.

Note

Combinatorial Benders Decomposition is a special case of LBBD. In CBD, the subproblems are typically MILPs, and the “proofs” correspond to an IIS (for feasibility cuts) or the optimal objective value itself (for optimality cuts), which are then formulated using NoGoodFC and CombinatorialOC, respectively. LBBD generalizes this by formalizing the use of any valid deductive system to create problem-specific cuts, enabling the handling of a broader class of subproblems beyond MILPs.

Algorithm

The LBBD algorithm follows the same iterative master-subproblem scheme as other Benders methods.

1. Initialization

   • Initialize a lower bound \(LB = -\infty\) and an upper bound \(UB = +\infty\).

   • The master problem starts with constraints \(\mathcal{C}'(x)\) and domain \(x \in \mathcal{D}_x\).

   • Set the iteration counter \(k = 1\).

2. Step 1: Solve the master problem

   • Solve the current master problem to obtain a solution \((\bar{x}_k, \bar{z}_k)\).

   • Update the lower bound: \(LB = \max(LB, \bar{z}_k)\).

3. Step 2: Check for convergence

   • If \(UB - LB \leq \epsilon\) (for a small tolerance \(\epsilon\)), STOP. The optimal solution has been found.

4. Step 3: Solve the subproblem

   • Fix \(x = \bar{x}_k\) and solve the subproblem.

   Note

   The subproblem can be solved using any appropriate method, including (but not limited to) MILP solvers, CP solvers, or custom/problem-specific algorithms (e.g., network flow algorithms, shortest path algorithms, etc.).

5. Step 4: Generate and add a cut

   • Analyze the proof from the subproblem to generate a logic-based Benders cut.

   • If the subproblem is infeasible, the cut excludes the infeasible master solution.

   • If the subproblem is feasible with cost \(z^*_k\), update the upper bound \(UB = \min(UB, z^*_k)\) and add a cut enforcing that the cost must be at least \(z^*_k\) if the master decisions are repeated.

   • Add the generated cut to the master problem.

6. Step 5: Loop

   • Increment \(k = k + 1\) and go back to Step 1.

The main challenge in applying LBBD is to design a problem-specific cut generation procedure that can extract a strong, concise logical explanation from the subproblem solution process.

See also

• Hooker’s book [3] that comprehensively covers LBBD theory and applications.

• LBBD for planning and scheduling with specific examples and logic-based Benders cuts [4].

• LBBD for stochastic optimization with specific examples and logic-based Benders cuts [5].

• Examples: Logic-Based Benders Decomposition, Stochastic Logic-Based Benders Decomposition, L-shaped Method by Logic-based Benders Decomposition, and Facility Location (Gurobi).

References

[1] (1,2,3)

Hooker, J. N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96(1), 33–60. https://doi.org/10.1007/s10107-003-0375-9

[2] (1,2)

Hooker, J. N. (2019). Logic-based Benders decomposition for large-scale optimization. In J. M. Velásquez-Bermúdez, M. Khakifirooz, & M. Fathi (Eds.), Large Scale Optimization in Supply Chains and Smart Manufacturing: Theory and Applications (pp. 1–26). Springer International Publishing. https://doi.org/10.1007/978-3-030-22788-3_1

[3] (1,2,3,4,5)

Hooker, J. (2024). Logic-Based Benders Decomposition: Theory and Applications. Springer International Publishing. https://doi.org/10.1007/978-3-031-45039-6

[4]

Hooker, J. N. (2007). Planning and scheduling by logic-based Benders decomposition. Operations Research, 55(3), 588–602. https://doi.org/10.1287/opre.1060.0371

[5]

Elçi, Ö., & Hooker, J. (2022). Stochastic planning and scheduling with logic-based Benders decomposition. INFORMS Journal on Computing, 34(5), 2383–2865. https://doi.org/10.1287/ijoc.2022.1184