# Implementation of the Modern Algorithm

Single MIP

When solving a MIP problem, the classic Benders’ decomposition algorithm often spends a large amount of time in solving the master MIP problems in which a significant amount of rework is done. In the modern approach only one single master MIP problem is solved. Whenever the solver finds a feasible integer solution for the master problem, the subproblem \(PS(x^*)\) is solved after fixing the master problem variable \(x^*\) according to this integer solution.

Callbacks

Modern MIP solvers like CPLEX and Gurobi allow the user control over the
solution process by so-called *callbacks*. Callbacks allow user code in
AIMMS to be executed regularly during an optimization process. If the
solver finds a new candidate integer solution then the user has the
possibility to let the solver call one or more callback procedures. One
of these callbacks is the callback for lazy constraints; that callback
is used in the modern Benders’ decomposition algorithm.

Feasible solutions

If no violated Benders’ cut can be generated, after solving the subproblem, then we have found a feasible solution for the original problem and we can accept the current feasible integer solution as a “correct” solution for the master MIP problem. In the classic algorithm we would now be finished because we would know that no better solution of the original problem exists. In the modern algorithm we have to continue solving the master MIP problem because there might still exist a solution to the master MIP problem that results in a better solution for the original problem.

Lazy constraints

If a Benders’ optimality or feasibility cut is found then this will be
added as a so-called *lazy constraint* to the master MIP problem. Lazy
constraints are constraints that represent one part of the model;
without them the model would be incomplete. In this case the actual
model that we want to solve is the original problem but we are solving
the master MIP problem instead. The Benders’ cuts represent the
subproblem part of the model and we add them whenever we find one that
is violated.

Implementation of `DoBendersDecompositionSingleMIP`

In the remainder of this section we show the implementation of the
modern Benders’ decomposition algorithm as implemented by the procedure
`DoBendersDecompositionSingleMIP`

which was introduced in
Quick Start to Using Benders’ Decomposition. Similar to the procedure
`DoBendersDecompositionClassic`

, the procedure
`DoBendersDecompositionSingleMIP`

starts by making copies of its input
arguments. Next the master problem and the subproblem are created. The
parameters for the number of optimality and feasibility cuts are reset.
Finally, the procedure calls another procedure, namely
`BendersAlgorithmSingleMIP`

, and finishes by deleting the master
problem and the subproblem. As before we leave out parts of the code
that handle details like creating a status file, for the sake of brevity
and clarity.

```
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.
BendersAlgorithmSingleMIP;
GMP::Instance::Delete( gmpM );
GMP::Instance::Delete( gmpS );
```

The procedure `BendersAlgorithmSingleMIP`

The `BendersAlgorithmSingleMIP`

procedure initializes the algorithm by
resetting the parameters for the number of iterations, etc. Then it
calls the procedure `SolveMasterMIP`

which does the actual work.

```
InitializeAlgorithmSingleMIP;
SolveMasterMIP;
```

The procedure `SolveMasterMIP`

The `SolveMasterMIP`

procedure implements the actual Benders’
decomposition algorithm using the modern approach. It first installs a
lazy constraint callback for which the module implements four different
versions. We assume that the control parameters have their default
settings (see this table) in which case the
procedure `BendersCallbackLazyFeasOnlySingleMIP`

is installed. Next
the master problem is solved and if a feasible solution is found, the
subproblem is solved one last time to obtain a combined optimal solution
for the original problem. Finally the algorithm terminates.

```
if ( UseDual ) then
if ( FeasibilityOnly ) then
GMP::Instance::SetCallbackAddLazyConstraint( gmpM,
'GMPBenders::BendersCallbackLazyFeasOnlyDualSingleMIP' );
else
GMP::Instance::SetCallbackAddLazyConstraint( gmpM,
'GMPBenders::BendersCallbackLazyOptAndFeasDualSingleMIP' );
endif;
else
if ( FeasibilityOnly ) then
GMP::Instance::SetCallbackAddLazyConstraint( gmpM,
'GMPBenders::BendersCallbackLazyFeasOnlySingleMIP' );
else
GMP::Instance::SetCallbackAddLazyConstraint( gmpM,
'GMPBenders::BendersCallbackLazyOptAndFeasSingleMIP' );
endif;
endif;
GMP::Instance::Solve( gmpM );
ProgramStatus := GMP::Solution::GetProgramStatus( gmpM, 1 ) ;
if ( ProgramStatus = 'Infeasible' ) then
AlgorithmTerminateSingleMIP( 'Infeasible' );
else
if ( FeasibilityOnly and not UseDual ) then
! Solve feasibility problem fixing the optimal solution of the
! Master problem.
GMP::Solution::SendToModel( gmpM, 1 );
! Update feasibility problem and solve it.
GMP::Benders::UpdateSubProblem( gmpF, gmpM, 1, round : 1 );
GMP::Instance::Solve( gmpF );
else
! Solve Subproblem fixing the optimal solution of the Master problem.
GMP::Solution::SendToModel( gmpM, 1 );
! Update Subproblem and solve it.
GMP::Benders::UpdateSubProblem( gmpS, gmpM, 1, round : 1 );
GMP::Instance::Solve( gmpS );
endif;
AlgorithmTerminateSingleMIP( 'Optimal' );
endif;
```

The procedure `BendersCallbackLazyFeasOnlySingleMIP`

The callback procedure `BendersCallbackLazyFeasOnlySingleMIP`

is
called by the MIP solver whenever it finds a candidate integer solution
for the master problem. This procedure retrieves the candidate integer
solution from the MIP solver. Then it creates the feasibility problem
for the (primal) subproblem if it does not exist yet. The feasibility
problem is updated and solved. If its optimal objective value is larger
than 0, indicating that the subproblem would have been infeasible, we
add a feasibility cut as a lazy constraint to the master MIP. The MIP
solver will not treat this candidate integer solution as a real
solution. If the optimal objective value equals 0 (or is negative) then
we do not add a lazy constraint in which case the MIP solver accepts the
candidate solution as a real solution. Finally, the callback procedure
returns 1 such that the solution process of the master MIP problem
continues.

```
! Get MIP incumbent solution.
GMP::Solution::RetrieveFromSolverSession( ThisSession, 1 );
GMP::Solution::SendToModel( gmpM, 1 );
! Create feasibility problem corresponding to Subproblem (if it does not exist yet).
if ( not FeasibilityProblemCreated ) then
gmpF := GMP::Instance::CreateFeasibility( gmpS, "FeasProb",
useMinMax : UseMinMaxForFeasibilityProblem );
solsesF := GMP::Instance::CreateSolverSession( gmpF ) ;
FeasibilityProblemCreated := 1;
endif;
! Update feasibility problem corresponding to Subproblem and solve it.
GMP::Benders::UpdateSubProblem( gmpF, gmpM, 1, round : 1 );
GMP::SolverSession::Execute( solsesF ) ;
GMP::Solution::RetrieveFromSolverSession( solsesF, 1 ) ;
! Check whether objective is 0 in which case optimality condition is satisfied.
ObjectiveFeasProblem := GMP::SolverSession::GetObjective( solsesF );
if ( ObjectiveFeasProblem <= BendersOptimalityTolerance ) then
return 1;
endif;
! Add feasibility cut to the Master problem.
NumberOfFeasibilityCuts += 1;
GMP::SolverSession::AddBendersFeasibilityCut( ThisSession, gmpF, 1 );
return 1;
```

The procedure `AlgorithmTerminateSingleMIP`

The procedure `AlgorithmTerminateSingleMIP`

is called to finish the
Benders’ decomposition algorithm. This procedure is called directly
after the master MIP problem is solved. Its implementation is similar to
that of the procedure `AlgorithmTerminate`

of
Implementation of the Classic Algorithm and therefore omitted.