Tutorials
=============

This tutorial section offers an overview of the Benders Decomposition theory,
covering its development over more than fifty years.
There are several important variants of Benders Decomposition listed below.
They are implemented (:doc:`../api/benders`, :doc:`../examples/index`) in BendersLib, and these representative variants
will help guide the design (:doc:`../manual/index`, :doc:`../api/index`) of the library.

.. list-table:: Benders Decomposition Variants
    :widths: 50 20 20 20
    :header-rows: 1
    :name: benders-variants

    * - Name
      - P\. Type
      - M.P. Type
      - S.P. Type
    * - (Classical) Benders Decomposition [#]_
      - MILP
      - MILP
      - LP
    * - Combinatorial Benders Decomposition [#]_
      - MILP
      - MILP
      - Feasibility
    * - Generalized Benders Decomposition [#]_
      - NLP
      - NLP
      - Convex NLP
    * - L-shaped Method [#]_
      - Stochastic LP
      - LP
      - LP
    * - Integer L-shaped Method [#]_
      - Stochastic MILP
      - MILP (binary)
      - MILP (binary)
    * - Logic-based Benders Decomposition [#]_
      - Any
      - Any
      - Any

*P.: Original problem, M.P.: Master problem, S.P.: Sub problem,
MILP: Mixed-Integer Linear Programming, LP: Linear Programming, NLP: Non-Linear Programming.*

A Benders Decomposition method is composed of a **master problem**, one or more
**subproblems**, **Benders cuts**,
and a **Benders algorithm** that orchestrates the solution process, to solve the
original mathematical programming problem.
These components make one Benders method different from another.
A brief introduction of the components of these variants is given below.


* :doc:`classical` is essentially a Kelley's
  :abbr:`cutting-plane method (methods iteratively refine a feasible set or objective function by linear inequalities)` [#]_
  for solving MILPs. It works by splitting a problem into two parts: a master problem that handles
  the difficult (integer) decisions and a subproblem that deals with the consequences of those decisions.
  The master problem, an MILP, proposes a set of integer variables, and the subproblem, a much simpler LP,
  checks the feasibility and optimality of that proposal. Information from the subproblem's dual solution is
  then used to generate linear *Benders optimality cuts* and *Benders feasibility cuts* that are added to the master problem,
  systematically refining the solution until an optimum is found.

* :doc:`cbd`
  extends the cutting-plane approach to MILPs where the subproblem is itself a
  combinatorial problem, typically a MILP. Like the classical method, it divides the problem into a master problem
  and a subproblem that assesses the consequences, based on pure binary complicating variables.
  The fundamental difference is that the subproblem is not a simple LP, meaning its solution does not provide
  the dual information used in classical Benders. Instead, cuts are generated through combinatorial arguments:
  *no-good cuts* are derived from proofs of subproblem infeasibility,
  while *combinatorial optimality cuts* are logical constraints that connect a specific set of master decisions
  to the resulting subproblem cost.

* :doc:`gbd`
  is an extension of the classical method to solve convex NLPs.
  It partitions the problem based on variable type, where the master problem handles complicating variables
  and the subproblem solves a convex NLP for fixed values of these variables.
  The key is the use of nonlinear duality theory to generate cutting planes, known as *Lagrangian cuts*,
  that approximate the subproblem's objective function.

* :doc:`lshaped`
  is a specialized version of Benders Decomposition for Stochastic Linear Programming problems.
  The first-stage decisions (master problem) are made before uncertainty is resolved,
  and the second-stage decisions (subproblem) adapt to the outcomes.
  The method iteratively adds *optimality cuts* (for expected future costs) and *feasibility cuts*
  (to handle scenarios where second-stage constraints cannot be met) to the master problem,
  refining the first-stage decision until an optimal solution is found.
  It can be seen as a specific application of :doc:`classical` to Stochastic Programming.

* :doc:`ilshaped`
  adapts the L-shaped method for stochastic programs where some decision variables in the second stage are integers.
  This introduces non-convexity, so linear programming duality cannot be directly applied.
  Instead, the integer L-shaped method can be seen as a combination of :doc:`lshaped` and :doc:`cbd`.
  The cuts are derived from the structure of the integer subproblem, often using *no-good cuts* to exclude infeasible first-stage decisions
  and *combinatorial optimality cuts* to capture the cost implications of specific first-stage decisions.

* :doc:`lbbd`
  is a framework that combines Benders Decomposition with logic-based methods (e.g., Constraint Programming).
  It is highly flexible and can be applied to a wide range of optimization problems.
  The master problem provides a partial assignment of variables, and the subproblem,
  determines the consequences. Instead of relying on traditional duality, LBDD uses inference and combinatorial arguments
  to generate cuts. For example, if a subproblem is infeasible, a *no-good cut* is generated to exclude that specific
  assignment of master variables.


.. seealso::

   * A review of Benders Decomposition by Rahmaniani et al. [#]_.
   * A review of Jacques Benders' life and work by Aardal et al. [#]_.
   * A review of Integer Linear Programming that covers Benders Decomposition by Clautiaux and Ljubić [#]_.
   * Useful practical guidelines for implementing (Logic-based) Benders Decomposition (Section 2.7) [#]_.


Contents
-------------

.. toctree::
   :maxdepth: -1

   classical.rst
   cbd.rst
   gbd.rst
   lshaped.rst
   ilshaped.rst
   lbbd.rst
   enhance.rst

References
-------------

.. [#] Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252. https://doi.org/10.1007/BF01386316
.. [#] 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
.. [#] Geoffrion, A. M. (1972). Generalized Benders Decomposition. Journal of Optimization Theory and Applications, 10(4), 237–260. https://doi.org/10.1007/BF00934810
.. [#] Van Slyke, R. M., & Wets, R. (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17(4), 638–663. https://doi.org/10.1137/0117061
.. [#] 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
.. [#] 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
.. [#] Kelley, Jr., J. E. (1960). The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics, 8(4), 703–712. https://doi.org/10.1137/0108053
.. [#] 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
.. [#] Aardal, K., Hurkens, C., & Lenstra, J. K. (2025). Jacques Benders and his decomposition algorithm. Operations Research Letters, 63, 107361. https://doi.org/10.1016/j.orl.2025.107361
.. [#] Clautiaux, F., & Ljubić, I. (2025). Last fifty years of integer linear programming: A focus on recent practical advances. European Journal of Operational Research, 324(3), 707–731. https://doi.org/10.1016/j.ejor.2024.11.018
.. [#] Hooker, J. (2024). Logic-Based Benders Decomposition: Theory and Applications. Springer International Publishing. https://doi.org/10.1007/978-3-031-45039-6