Combinatorial Benders Decomposition ============================================ .. currentmodule:: benderslib .. role:: raw-latex(raw) :format: latex .. default-role:: raw-latex 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: .. math:: \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} Here, :math:`x` are the binary **complicating variables**, and :math:`y` can be either integer or continuous variables. If we fix the :math:`x` variables to a specific value :math:`\bar{x}`, the remaining problem in :math:`y` can be MILP, LP, or feasibility problem (when :math:`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 :math:`x`, while the subproblem evaluates the consequences of that choice. The **master problem** includes the complicating variables :math:`x` and an auxiliary variable :math:`\theta` that estimates the cost of the subproblem. .. math:: \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} For a given solution :math:`\bar{x}` from the master problem, the **subproblem** is solved. .. math:: \begin{aligned} z = \min_{y} \quad & q^T y \\ \text{s.t.} \quad & By \geq b - A \bar{x} \\ & y \in Y \end{aligned} This can be a LP, MILP, pure integer LP, or feasibility problem (when :math:`q=0`). However, the complicating variables :math:`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 :math:`y` satisfies the constraints. This leads to a **no-good cut** (feasibility cut). 2. **Feasible:** An optimal :math:`\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 :math:`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 :doc:`lbbd` 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 :math:`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 :math:`\bar{x}`. * **What is the logic?** If the subproblem is infeasible, we add a cut to forbid the combination of :math:`x` values that caused the infeasibility. Let :math:`I_1` be the set of indices of binary variables that are 1 in the current solution :math:`\bar{x}`, and :math:`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. .. math:: \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. .. math:: \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 :math:`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 :abbr:`Irreducible Inconsistent Subsystem (a minimal subset of constraints and/or variable bounds that cause the infeasibility)` (IIS). * In contrast to IIS, the set :math:`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 :math:`\bar{x}`, yielding an optimal cost :math:`z^*`. * **What is the logic?** The cut must inform the master problem that if it keeps the :math:`x` the same, the subproblem cost will be at least :math:`z^*`. This is done using a "big-M" formulation. If the :math:`x` solution remains unchanged, the cut :math:`\theta \geq z^*` is active. Otherwise, it is relaxed. * **The Cut:** We add the following linear constraint to the master problem. .. math:: \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 :doc:`ilshaped` for more details), when there is only one scenario in stochastic programming. * The value of :math:`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. #. **Initialization** * Initialize a lower bound :math:`LB = -\infty` and an upper bound :math:`UB = +\infty`. * The master problem starts with the constraints :math:`x \in X`. * Set the iteration counter :math:`k = 1`. #. **Step 1: Solve the master problem** * Solve the current master problem to obtain a solution :math:`(\bar{x}_k, \bar{\theta}_k)`. * The objective :math:`c^T \bar{x}_k + \bar{\theta}_k` is a lower bound on the optimal solution. Update :math:`LB = \max(LB, c^T \bar{x}_k + \bar{\theta}_k)`. #. **Step 2: Check for convergence** * If :math:`UB - LB \leq \epsilon` (for a small tolerance :math:`\epsilon`), **STOP**. The optimal solution has been found. The best solution found so far that yielded a feasible subproblem is the optimal solution. #. **Step 3: Solve the subproblem** * Solve the subproblem with :math:`x` fixed to :math:`\bar{x}_k`. #. **Step 4: Generate and add a cut** * **Case A: Subproblem is infeasible.** * Identify a (:math:`I_1`, :math:`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 :math:`z^*_k`. * This provides a valid feasible solution for the original problem with total cost :math:`c^T \bar{x}_k + z^*_k`. * Update the upper bound: :math:`UB = \min(UB, c^T \bar{x}_k + z^*_k)`. * Identify a (:math:`I_1`, :math:`I_0`) and add a **combinatorial optimality cut** to the master problem. #. **Step 5: Loop** * Increment :math:`k = k + 1` and go back to **Step 1**. The main customization required for implementing Combinatorial Benders Decomposition lies in the logic for generating (:math:`I_1`, :math:`I_0`) for both the feasibility and optimality cuts, as this is problem-dependent and crucial for the algorithm's efficiency. .. seealso:: * Huang et al. [3]_ and Zohali et al. [4]_ formulated both feasibility and optimality cuts. * Rahmaniani et al. [5]_ discussed Benders decomposition with discrete subproblems. * Combinatorial Benders Decomposition is suitable for what kind of problems: `StackExchange/OR `_ * Combinatorial Benders Decomposition for assembly line balancing (without using BendersLib): `GitHub/hw23 `_ * BendersLib's implementation of optimality and feasibility cuts: :class:`CombinatorialOC` and :class:`NoGoodFC`. * BendersLib's implementation of the Benders method: :class:`CombinatorialBenders`. * **Examples**: :doc:`../examples/basic/cbd` and :doc:`../examples/advanced/cbd_iis`. References -------------------------------------------- .. [1] Codato, G., & Fischetti, M. (2006). Combinatorial Benders’ cuts for mixed-integer linear programming. Operations Research, 54(4), 756–766. https://doi.org/10.1287/opre.1060.0286 .. [2] Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3), 133–142. https://doi.org/10.1016/0167-6377(93)90002-X .. [3] Huang, D., Mao, Z., Fang, K., Fu, E., & Pinedo, M. L. (2024). An Improved Combinatorial Benders Decomposition Algorithm for the Human-Robot Collaborative Assembly Line Balancing Problem. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2023.0279 .. [4] Zohali, H., Naderi, B., & Roshanaei, V. (2022). Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition. INFORMS Journal on Computing, 34(1), 315–332. https://doi.org/10.1287/ijoc.2020.1015 .. [5] Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders Decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817. https://doi.org/10.1016/j.ejor.2016.12.005