BendersDecompositionSolver

Definition and implementation of the BendersDecompositionSolver class, which implements the CDASolver interface within the SMS++ framework to automate the Benders decomposition of a block-structured problem.

Attached to a suitably structured Block (B), BendersDecompositionSolver keeps the "complicating" (first-stage) Variable of (B) in a master problem and projects out the Variable of each sub-Block, representing the resulting value function as a BendersBFunction. The Benders optimality and feasibility cuts are produced by the BendersBFunction through the standard C05Function interface, so the solver concentrates on the automation layer: detecting the complicating Variable, building one BendersBFunction per sub-Block, assembling the master problem and driving the cut loop.

The Block (B) is assumed to have the following structure:

• the root (B) plays the role of the master: its Objective and Constraint are the first-stage objective and feasible region, and its ColVariable are the complicating Variable;

• each sub-Block is a subproblem, with its own Variable, Objective and Constraint, coupled to the master only through the appearance of (some of) the complicating Variable in (some of) its Constraint.

The same Block, however, admits many Benders reformulations, and which one is wanted is a choice of whoever poses the problem: two parameters say it. The vintMasterBlock one names the positions of the sub-Block the master keeps for itself, the subproblems being the ones that are left, and vintMasterVars names the positions of the complicating Variable among those the master exposes. Both empty, which is the default, is the structure described above.

Two regimes are supported for solving the master problem, selected by a parameter:

• a convex regime, in which the value functions enter the master objective as C05Function and the master is solved by a bundle-type CDASolver, which performs the (stabilized) cutting-plane loop internally;

• a MILP regime, in which the master is a MILP with epigraph Variable and the Benders cuts are added as dynamic Constraint, the solver driving the outer cut loop until no violated cut remains.

Which of the cuts a degenerate subproblem offers is taken is a parameter as well: a subproblem is very often dual degenerate, so its optimal duals are a face rather than a point and every one of them gives a valid, but not equally strong, cut. Besides the one the incumbent happens to give, BendersDecompositionSolver can generate the Pareto-optimal cut of Magnanti and Wong in the one-step form of Papadakos, i.e., by solving the subproblem at a core point that moves towards the incumbent as the loop proceeds. Feasibility cuts, being rays of the dual polyhedron and therefore defined up to a positive multiplier, can be normalized by a norm of their own coefficients; an infeasible subproblem whose complicating Variable are binary can be cut away by a combinatorial, or no-good, cut, which forbids the assignment at hand and asks nothing at all of the subproblem Solver; and it can be cut away by the cut of a phase one, i.e., of the problem that minimizes the violation of the coupling Constraint on the abstract copy the subproblem makes of itself, which gives each of them a slack with a cost. Which cut a given infeasibility yields is decided by the normalization the multipliers are subject to, and there the costs of the slacks are that normalization: the cut is then the one a bounded separation problem selects rather than whichever ray the Solver happened to return. The costs are either all one or, for each row, the inverse of its norm, which makes the cut independent of how the rows are scaled.

Feasibility and optimality can also be separated together, by one cut-generating problem rather than by two mechanisms: the epigraph inequality joins the coupling Constraint that carry a slack in the phase one, the epigraph Variable enters its value function the way the complicating ones do, and the linearization in both, asked to be nonpositive, is the cut, which is a feasibility one where the multiplier of the epigraph inequality is zero and an optimality one where it is positive. This is the unified cut of Cornuejols and Lemarechal, of Fischetti, Salvagnin and Zanette and of Brandenberg and Stursberg, and what decides how it divides itself between the two roles is the ratio between the cost of the slack of the epigraph inequality and those of the coupling ones.

Projecting the second-stage Variable out is not done on a copy: the complicating Variable are taken out of the Constraint of the subproblems, and in the MILP regime the Block itself is grafted into the master, so while that lasts the Block is not the problem it was. It can be asked to be given back as it was at the end of every compute(), which is what lets another Solver be attached to the same Block and cross-checked against this one, as a BlockSolverConfig with more than one Solver does; what that costs is the reformulation, paid at every compute(), and the cuts, which are pieces of the master and are disposed of with it.

The master and the subproblem Solver are instantiated through the Solver factory and configured via Configuration, so that how the master and the subproblems are solved is not hard-wired. See the class documentation for the full description of the assumptions, parameters and solution recovery.

Both kinds of cut are duals of the subproblem, but they ask different things of the Solver that produces them. Any optimal dual solution gives a valid optimality cut, basic or not, and the "central" solution of an interior-point method can even give a stronger one. The feasibility cut, instead, is the unbounded dual direction, i.e., the Farkas certificate, which is a ray of the dual polyhedron and therefore has nothing to do with the algorithm that finds it. What does destroy it is the presolve, which detects the infeasibility on the reduced problem and returns no certificate for the original one, hence the presolve of the subproblem Solver has to be switched off if feasibility cuts are wanted at all. If the certificate is missing, an exception is thrown rather than silently converging to a wrong optimum. A subproblem that is always feasible, e.g. because the constraints the master can make unsatisfiable carry a slack with a large cost, needs no feasibility cut in the first place and is therefore the robust choice whenever the model allows it.

The method is described in

W. van Ackooij, A. Frangioni, W. de Oliveira "Inexact Stabilized Benders' Decomposition Approaches, with Application to Chance-Constrained Problems with Finite Support" Computational Optimization and Applications 65(3), 637-669, 2016

and in

D. Baena, J. Castro, A. Frangioni "Stabilized Benders Methods for Large-scale Combinatorial Optimization, with Application to Data Privacy" Management Science 66(7), 3051-3068, 2020

while the Pareto-optimal cuts are those of

T.L. Magnanti, R.T. Wong "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria" Operations Research 29(3), 464-484, 1981

in the one-step form of

N. Papadakos "Practical Enhancements to the Magnanti-Wong Method" Operations Research Letters 36(4), 444-449, 2008

the combinatorial cuts are those of

G. Codato, M. Fischetti "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming" Operations Research 54(4), 756-766, 2006

the normalization of the feasibility cuts follows

M. Fischetti, D. Salvagnin, A. Zanette "A Note on the Selection of Benders' Cuts" Mathematical Programming 124(1-2), 175-182, 2010

and a broad survey of all this is

R. Rahmaniani, T.G. Crainic, M. Gendreau, W. Rei "The Benders Decomposition Algorithm: A Literature Review" European Journal of Operational Research 259(3), 801-817, 2017

Getting started

These instructions will let you build BendersDecompositionSolver.

The module also comes ready-made, in any of

sudo add-apt-repository ppa:smspp-project/smspp   # Ubuntu
sudo apt install libsmspp-bds-dev

conda install -c conda-forge smspp-project        # Linux, macOS, Windows

brew tap SMSpp-Project/smspp                      # macOS, Linux
brew install smspp

vcpkg install "smspp[core,bds]"                   # from the sources

where apt and the port give the module alone, while conda and the tap carry the whole framework. What follows is about building it yourself.

Requirements

• SMS++ core library

It's not a build requirement, but you will need a SMS++ Solver capable of solving the master problem, such as BundleSolver for the convex regime or MILPSolver for the MILP regime.

Build and install with CMake

Configure and build the library with:

mkdir build
cd build
cmake ..
cmake --build .

The library has the same configuration options of SMS++.

Optionally, install the library in the system with:

cmake --install .

Usage with CMake

After the library is built, you can use it in your CMake project with:

find_package(BendersDecompositionSolver)
target_link_libraries(<my_target> SMS++::BendersDecompositionSolver)

Build and install with makefiles

Carefully hand-crafted makefiles have also been developed for those unwilling to use CMake. Makefiles build the executable in-source (in the same directory tree where the code is) as opposed to out-of-source (in the copy of the directory tree constructed in the build/ folder) and therefore it is more convenient when having to recompile often, such as when developing/debugging a new module, as opposed to the compile-and-forget usage envisioned by CMake.

Each executable using BendersDecompositionSolver has to include a "main makefile" of the module, which typically is either makefile-c including all necessary libraries comprised the "core SMS++" one, or makefile-s including all necessary libraries but not the "core SMS++" one (for the common case in which this is used together with other modules that already include them). The makefiles in turn recursively include all the required other makefiles, hence one should only need to edit the "main makefile" for compilation type (C++ compiler and its options) and it all should be good to go. In case some of the external libraries are not at their default location, it should only be necessary to create the ../extlib/makefile-paths out of the extlib/makefile-default-paths-* for your OS * and edit the relevant bits (commenting out all the rest).

Check the SMS++ installation wiki for further details.

Getting help

If you need support, you want to submit bugs or propose a new feature, you can open a new issue.

Contributing

Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting merge requests to us.

Authors

Current Lead Authors

• Antonio Frangioni
  Dipartimento di Informatica
  Università di Pisa

• Donato Meoli
  Dipartimento di Informatica
  Università di Pisa

Contributors

License

This code is provided free of charge under the GNU Lesser General Public License version 3.0 - see the LICENSE file for details.

Disclaimer

The code is currently provided free of charge under an open-source license. As such, it is provided "as is", without any explicit or implicit warranty that it will properly behave or it will suit your needs. The Authors of the code cannot be considered liable, either directly or indirectly, for any damage or loss that anybody could suffer for having used it. More details about the non-warranty attached to this code are available in the license description file.