Combinatorial Benders Decomposition

Original Problem

The Combinatorial Benders Decomposition (CBD) [1] extends the classical Benders framework to problems where fixing the complicating variables results in a subproblem that is itself can be a combinatorial optimization problem. This is in contrast to classical Benders, where the subproblem is a LP. Consider a MILP of the form:

\[\begin{split}\begin{aligned} \min_{x, y} \quad & c^T x + q^T y \\ \text{s.t.} \quad & Ax + By \geq b \\ & x \in X \subseteq \{0,1\}^n \\ & y \in Y \end{aligned}\end{split}\]

Here, \(x\) are the binary complicating variables, and \(y\) can be either integer or continuous variables. If we fix the \(x\) variables to a specific value \(\bar{x}\), the remaining problem in \(y\) can be MILP, LP, or feasibility problem (when \(q=0\) ). The main challenge is that MILPs do not have a strong, readily-available dual like LPs do. Therefore, the classical method of generating cuts from dual solutions is not applicable. The Combinatorial Benders Decomposition overcomes this by deriving “combinatorial” cuts.

Reformulation

Similar to the classical approach, the problem is decomposed into a master problem and a subproblem. The master problem determines the values for the complicating variables \(x\), while the subproblem evaluates the consequences of that choice. The master problem includes the complicating variables \(x\) and an auxiliary variable \(\theta\) that estimates the cost of the subproblem.

\[\begin{split}\begin{aligned} \min_{x, \theta} \quad & c^T x + \theta \\ \text{s.t.} \quad & x \in X \subseteq \{0,1\}^n \\ & \dots (\text{no-good cuts}) \\ & \dots (\text{combinatorial optimality cuts}) \\ \end{aligned}\end{split}\]

For a given solution \(\bar{x}\) from the master problem, the subproblem is solved.

\[\begin{split}\begin{aligned} z = \min_{y} \quad & q^T y \\ \text{s.t.} \quad & By \geq b - A \bar{x} \\ & y \in Y \end{aligned}\end{split}\]

This can be a LP, MILP, pure integer LP, or feasibility problem (when \(q=0\)). However, the complicating variables \(x\) are required to be binary. The outcome of solving this subproblem informs the generation of a new cut for the master problem.

  1. Infeasible: No \(y\) satisfies the constraints. This leads to a no-good cut (feasibility cut).

  2. Feasible: An optimal \(\bar{y}\) is found. This leads to a combinatorial optimality cut.

Note

There are several cases of the subproblem. Among them the MILP subproblem is the most general.

  • MILP: In this case both no-good cuts and combinatorial optimality cuts are generated, unless the MILP is ensured to be always feasible. The subproblem is solved using a MILP solver, or specialized combinatorial algorithms.

  • Feasibility problem (when \(q=0\)): In this case only no-good cuts are generated, and the subproblem is not necessarily be solved by a mathematical programming solver. Instead, constraint programming or specialized feasibility algorithms can be used.

  • LP: In this case, classical Benders Decomposition can be preferred due to its stronger cuts from duality, but Combinatorial Benders Decomposition can still be applied. Both no-good cuts and combinatorial optimality cuts are generated. The subproblem is solved using a LP solver.

In the cases that subproblems are not solved by mathematical programming solvers, the term Logic-based Benders Decomposition may be used interchangeably with Combinatorial Benders Decomposition in the literature, as the former emphasizes the subproblem can be any types of optimization problems.

Benders Cuts

Since LP duality cannot be used, combinatorial cuts are generated by identifying a small subset of the master problem decisions \(x\) that are responsible for either the subproblem’s infeasibility or its optimality for a given cost.

No-good Cut (Feasibility Cut)

  • When is it generated? When the subproblem is infeasible for a given \(\bar{x}\).

  • What is the logic? If the subproblem is infeasible, we add a cut to forbid the combination of \(x\) values that caused the infeasibility. Let \(I_1\) be the set of indices of binary variables that are 1 in the current solution \(\bar{x}\), and \(I_0\) be the set of indices for variables that are 0. The cut ensures at least one of these variables changes its value.

  • The Cut: We add the following linear constraint [1] to the master problem.

    \[\sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \geq 1\]

    Some literature presents the cut in the following equivalent form.

    \[\sum_{i \in I_1} x_i - \sum_{i \in I_0} x_i \leq |I_1| - 1\]

Note

  • For the cut to be strong, the set \(I_1 \cup I_0\) should be as small as possible, ideally containing only the variables relevant to the subproblem’s infeasibility. This can be found by identifying an Irreducible Inconsistent Subsystem (IIS).

  • In contrast to IIS, the set \(I_1 \cup I_0\) can also be determined heuristically based on problem-specific insights. It is not necessarily minimal, but it should still be as small as possible to enhance the cut’s effectiveness.

Combinatorial Optimality Cut

  • When is it generated? When the subproblem is feasible for a given \(\bar{x}\), yielding an optimal cost \(z^*\).

  • What is the logic? The cut must inform the master problem that if it keeps the \(x\) the same, the subproblem cost will be at least \(z^*\). This is done using a “big-M” formulation. If the \(x\) solution remains unchanged, the cut \(\theta \geq z^*\) is active. Otherwise, it is relaxed.

  • The Cut: We add the following linear constraint to the master problem.

    \[\theta \geq z^* - M \left( \sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \right)\]

Note

  • This type of cut can be seen a special case of integer L-shaped cut [2] (see Integer L-shaped Method for more details), when there is only one scenario in stochastic programming.

  • The value of \(M\) should be as small as possible to keep the cut strong. A valid choice is any upper bound on the subproblem cost.

Algorithm

The iterative procedure for Combinatorial Benders Decomposition is as follows.

  1. Initialization

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

    • The master problem starts with the constraints \(x \in 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{\theta}_k)\).

    • The objective \(c^T \bar{x}_k + \bar{\theta}_k\) is a lower bound on the optimal solution. Update \(LB = \max(LB, c^T \bar{x}_k + \bar{\theta}_k)\).

  3. Step 2: Check for convergence

    • If \(UB - LB \leq \epsilon\) (for a small tolerance \(\epsilon\)), STOP. The optimal solution has been found. The best solution found so far that yielded a feasible subproblem is the optimal solution.

  4. Step 3: Solve the subproblem

    • Solve the subproblem with \(x\) fixed to \(\bar{x}_k\).

  5. Step 4: Generate and add a cut

    • Case A: Subproblem is infeasible.

      • Identify a (\(I_1\), \(I_0\)) that causes the infeasibility (e.g., from an IIS).

      • Add a no-good cut to the master problem to eliminate this combination of binary variables.

    • Case B: Subproblem is feasible.

      • Let the optimal subproblem cost be \(z^*_k\).

      • This provides a valid feasible solution for the original problem with total cost \(c^T \bar{x}_k + z^*_k\).

      • Update the upper bound: \(UB = \min(UB, c^T \bar{x}_k + z^*_k)\).

      • Identify a (\(I_1\), \(I_0\)) and add a combinatorial optimality cut to the master problem.

  6. Step 5: Loop

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

The main customization required for implementing Combinatorial Benders Decomposition lies in the logic for generating (\(I_1\), \(I_0\)) for both the feasibility and optimality cuts, as this is problem-dependent and crucial for the algorithm’s efficiency.

See also

References