# Implementation of the Classic Algorithm

The procedure `DoBendersDecomposition`

In this section we show the implementation of the classic Benders’
decomposition algorithm. It follows the classic approach of solving the
master problem and the subproblem in an alternating sequence. The
procedure `DoBendersDecomposition`

, introduced in
Quick Start to Using Benders’ Decomposition, implements the classic algorithm.

Focus on textbook algorithm

The Benders’ cuts can be generated in several ways; in this section we focus on the approach used in the textbook algorithm of the previous section (Benders’ Decomposition - Textbook Algorithm). The textbook algorithm uses the dual formulation of the subproblem and can add both Benders’ optimality and feasibility cuts.

Calling `DoBendersDecompositionClassic`

We have to change some of the control parameters of
this table to let the
`DoBendersDecomposition`

procedure execute the textbook algorithm. The
relevant changes are listed below.

```
generatedMP := GMP::Instance::Generate( SymbolicMP );
! Settings needed to run textbook algorithm:
GMPBenders::FeasibilityOnly := 0;
GMPBenders::AddTighteningConstraints := 0;
GMPBenders::UseDual := 1;
GMPBenders::NormalizationType := 0;
GMPBenders::DoBendersDecompositionClassic( generatedMP, AllIntegerVariables );
```

Implementation of `DoBendersDecompositionClassic`

The `DoBendersDecompositionClassic`

procedure starts by making copies
of its input arguments. Next the master problem and the subproblem are
created. For the subproblem we also create a solver session which gives
us more flexibility passing and retrieving subproblem related
information. The parameters for the number of optimality and feasibility
cuts are reset. Finally, the procedure calls another procedure, namely
`BendersAlgorithm`

, and finishes by deleting the master problem and
the subproblem. For the sake of brevity and clarity, we leave out parts
of the code that handle details like creating a status file; this will
also be the case for the other pieces of code shown in this chapter.

```
OriginalGMP := MyGMP ;
VariablesMasterProblem := MyMasterVariables ;
! Create (Relaxed) Master problem.
gmpM := GMP::Benders::CreateMasterProblem( OriginalGMP, VariablesMasterProblem,
'BendersMasterProblem',
feasibilityOnly : FeasibilityOnly,
addConstraints : AddTighteningConstraints ) ;
! Create Subproblem.
gmpS := GMP::Benders::CreateSubProblem( OriginalGMP, gmpM, 'BendersSubProblem',
useDual : UseDual,
normalizationType : NormalizationType );
solsesS := GMP::Instance::CreateSolverSession( gmpS ) ;
NumberOfOptimalityCuts := 0;
NumberOfFeasibilityCuts := 0;
! Start the actual Benders' decomposition algorithm.
BendersAlgorithm;
GMP::Instance::Delete( gmpM );
GMP::Instance::Delete( gmpS );
```

The procedure `BendersAlgorithm`

The `BendersAlgorithm`

procedure implements the actual Benders’
decomposition algorithm. It initializes the algorithm by resetting the
parameters for the number of iterations, etc. Next the master problem is
solved. The separation step solves the subproblem and checks whether the
current solution is optimal. If it is not optimal then the algorithm
creates a constraint (“cut”) that separates the current solution from
the set of feasible solutions. This constraint is added to the master
problem enforcing that the current solution of the master problem will
not be found again if we solve the master problem once again. This
alternating sequence of solving master problems and subproblems is
repeated until a stopping criterion is met.

```
InitializeAlgorithm;
while ( not BendersAlgorithmFinished ) do
NumberOfIterations += 1;
SolveMasterProblem;
if ( UseDual ) then
if ( FeasibilityOnly ) then
SeparationFeasibilityOnlyDual;
else
SeparationOptimalityAndFeasibilityDual;
endif;
else
if ( FeasibilityOnly ) then
SeparationFeasibilityOnly;
else
SeparationOptimalityAndFeasibility;
endif;
endif;
endwhile;
```

Separation

The code above shows four possible ways of performing the separation
step. The textbook algorithm uses the procedure
`SeparationOptimalityAndFeasibilityDual`

which we will discuss below.
The other three separation procedures are discussed in
Additional Separation Procedures for Benders’ Decomposition.

The procedure `SolveMasterProblem`

The implementation of the `SolveMasterProblem`

procedure is
straightforward. This procedure solves the Benders’ master problem and
retrieves its objective value after checking the program status. If the
program status is infeasible or unbounded then the algorithm terminates.

```
GMP::Instance::Solve( gmpM );
ProgramStatus := GMP::Solution::GetProgramStatus( gmpM, 1 ) ;
if ( ProgramStatus = 'Infeasible' ) then
return AlgorithmTerminate( 'Infeasible' );
elseif ( ProgramStatus = 'Unbounded' ) then
return AlgorithmTerminate( 'ProgramNotSolved' );
endif;
ObjectiveMaster := GMP::Instance::GetObjective( gmpM );
```

The procedure `SeparationOptimalityAndFeasibilityDual`

The procedure `SeparationOptimalityAndFeasibilityDual`

is called by
the Benders’ decomposition algorithm in case the dual of the Benders’
subproblem is used and if both optimality and feasibility cuts can be
generated by the algorithm (we will discuss in
Control Parameters That Influence the Algorithm the case in which only feasibility cuts
are generated). This procedure updates the dual subproblem and solves
it. If the dual subproblem is unbounded then a feasibility cut is added
to the master problem (using an unbounded extreme ray; see the next
paragraph). If the subproblem is bounded and optimal then the objective
value of the subproblem is compared to the objective value of the master
problem to check whether the algorithm has found an optimal solution for
the original problem. If the solution is not optimal yet then an
optimality cut is added to the master problem, using the level values of
the variables in the solution of the dual subproblem.

```
return when ( BendersAlgorithmFinished );
GMP::Benders::UpdateSubProblem( gmpS, gmpM, 1, round : 1 );
GMP::SolverSession::Execute( solsesS ) ;
GMP::Solution::RetrieveFromSolverSession( solsesS, 1 ) ;
ProgramStatus := GMP::Solution::GetProgramStatus( gmpS, 1 ) ;
if ( ProgramStatus = 'Unbounded' ) then
! Add feasibility cut to the Master problem.
NumberOfFeasibilityCuts += 1;
GMP::Benders::AddFeasibilityCut( gmpM, gmpS, 1, NumberOfFeasibilityCuts );
else
! Check whether optimality condition is satisfied.
ObjectiveSubProblem := GMP::SolverSession::GetObjective( solsesS );
if ( SolutionImprovement( ObjectiveSubProblem, BestObjective ) ) then
BestObjective := ObjectiveSubProblem;
endif;
if ( SolutionIsOptimal( ObjectiveSubProblem, ObjectiveMaster ) ) then
return AlgorithmTerminate( 'Optimal' );
endif;
! Add optimality cut to the Master problem.
NumberOfOptimalityCuts += 1;
GMP::Benders::AddOptimalityCut( gmpM, gmpS, 1, NumberOfOptimalityCuts );
endif;
```

Unbounded extreme ray

In textbooks, if the dual subproblem is unbounded then an unbounded extreme ray is chosen and used to generate a feasibility cut. Choosing such an unbounded extreme ray is not trivial but luckily modern solvers like CPLEX and Gurobi can compute an unbounded extreme ray upon request. It is stored in the .Level suffix of the variables. The downside is that preprocessing by CPLEX or Gurobi has to be switched off which can have a negative impact on the performance. So, if the textbook algorithm is selected in which the dual subproblem is used and both optimality and feasibility cuts can be generated by the algorithm, the solver options for switching on the calculation of unbounded extreme ray and for switching off the preprocessor are set during the initialization of the Benders’ decomposition algorithm:

```
if ( UseDual and ( not FeasibilityOnly ) ) then
rval := GMP::SolverSession::SetOptionValue( solsesS, 'unbounded ray', 1 );
if ( rval = 0 ) then
halt with "Solver must support unbounded extreme rays.";
return;
endif;
rval := GMP::SolverSession::SetOptionValue( solsesS, 'presolve', 0 );
if ( rval = 0 ) then
halt with "Switching off the solver option 'presolve' failed.";
return;
endif;
endif;
```

If the solver does not support unbounded extreme rays then the textbook algorithm cannot be used.

The procedure `AlgorithmTerminate`

The procedure `AlgorithmTerminate`

is called whenever the Benders’
decomposition algorithm is finished. Appropriate values are assigned to
the program and solver status of the original problem. If the algorithm
has found an optimal solution then the solutions of the last master
problem and last subproblem are combined into an optimal solution for
the original problem. In the code below, the uncommon situation in which
the algorithm terminates after hitting the iteration limit has been
omitted.

```
BendersAlgorithmFinished := 1;
if ( ProgrStatus = 'Optimal' ) then
GMP::Solution::SetProgramStatus( OriginalGMP, 1, 'Optimal' ) ;
GMP::Solution::SetSolverStatus( OriginalGMP, 1, 'NormalCompletion' ) ;
GMP::Solution::SendToModel( gmpS, 1 ) ;
GMP::Solution::SendToModelSelection( gmpM, 1, VariablesMasterProblem,
AllSuffixNames );
GMP::Solution::RetrieveFromModel( OriginalGMP, 1 );
GMP::Solution::SetObjective( OriginalGMP, 1, BestObjective );
GMP::Solution::SendToModel( OriginalGMP, 1 );
elseif ( ProgrStatus = 'Infeasible' ) then
GMP::Solution::SetProgramStatus( OriginalGMP, 1, 'Infeasible' ) ;
GMP::Solution::SetSolverStatus( OriginalGMP, 1, 'NormalCompletion' ) ;
elseif ( ProgrStatus = 'Unbounded' ) then
GMP::Solution::SetProgramStatus( OriginalGMP, 1, 'Unbounded' ) ;
GMP::Solution::SetSolverStatus( OriginalGMP, 1, 'NormalCompletion' ) ;
else
GMP::Solution::SetProgramStatus( OriginalGMP, 1, 'ProgramNotSolved' ) ;
GMP::Solution::SetSolverStatus( OriginalGMP, 1, 'SetupFailure' ) ;
endif;
```