# Additional Separation Procedures for Benders’ Decomposition

In Implementation of the Classic Algorithm we showed the implementation of the
procedure `SeparationOptimalityAndFeasibilityDual`

as used by the
textbook algorithm. The Benders’ module implements also three other
separation procedure that can be used by the Benders’ decomposition
algorithm depending on the setting of the control parameters `UseDual`

and `FeasibilityOnly`

. In this chapter we explain the implementation
of these procedures.

The procedure `SeparationFeasibilityOnly`

The procedure `SeparationFeasibilityOnly`

is called by the Benders’
decomposition algorithm in case the primal of the Benders’ subproblem is
used (parameter `UseDual`

equals 0) and if only feasibility cuts can
be generated by the algorithm (parameter `FeasibilityOnly`

equals 1).
This procedure 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 equals 0 (or is negative)
then we have found an optimal solution for the original problem and the
algorithm terminates. If the optimal objective value is larger than 0,
indicating that the subproblem would have been infeasible, we add a
feasibility cut to the master problem. The feasibility cut is created
using the dual solution of the feasibility problem. By the dual solution
we mean the shadow prices of the constraints and the reduced costs of
the variables in the feasibility subproblem.

```
return when ( BendersAlgorithmFinished );
! 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
if ( MasterHasBeenSolved ) then
return AlgorithmTerminate( 'Optimal' );
endif;
endif;
! Add feasibility cut to the Master problem.
NumberOfFeasibilityCuts += 1;
GMP::Benders::AddFeasibilityCut( gmpM, gmpF, 1, NumberOfFeasibilityCuts );
```

The procedure `SeparationOptimalityAndFeasibility`

The procedure `SeparationOptimalityAndFeasibility`

is called by the
Benders’ decomposition algorithm in case the primal of the Benders’
subproblem is used (parameter `UseDual`

equals 0) and if both
optimality and feasibility cuts can be generated by the algorithm
(parameter `FeasibilityOnly`

equals 0). This procedure updates the
primal subproblem and solves it. If the primal subproblem is infeasible
then this procedure creates a feasibility problem for the subproblem if
it does not exist yet. The feasibility problem is updated and solved,
and its dual solution is used to created a feasibility cut which is
added to the master problem. If the primal 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 dual solution of the primal subproblem.

```
return when ( BendersAlgorithmFinished );
! Update Subproblem and solve it.
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
return AlgorithmTerminate( 'Unbounded' );
endif;
if ( ProgramStatus = 'Infeasible' ) then
! Create (if it does not exist yet) and update feasibility problem corresponding to
! Subproblem, and solve it to create feasibility cut for the Master problem.
if ( not FeasibilityProblemCreated ) then
gmpF := GMP::Instance::CreateFeasibility( gmpS, "FeasProb",
useMinMax : UseMinMaxForFeasibilityProblem );
solsesF := GMP::Instance::CreateSolverSession( gmpF ) ;
FeasibilityProblemCreated := 1;
endif;
GMP::Benders::UpdateSubProblem( gmpF, gmpM, 1, round : 1 );
GMP::SolverSession::Execute( solsesF ) ;
GMP::Solution::RetrieveFromSolverSession( solsesF, 1 ) ;
! Add feasibility cut to the Master problem.
NumberOfFeasibilityCuts += 1;
GMP::Benders::AddFeasibilityCut( gmpM, gmpF, 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;
```

The procedure `SeparationFeasibilityOnlyDual`

The procedure `SeparationFeasibilityOnlyDual`

is called by the
Benders’ decomposition algorithm in case the dual of the Benders’
subproblem is used (parameter `UseDual`

equals 1) and if only
feasibility cuts can be generated by the algorithm (parameter
`FeasibilityOnly`

equals 1). This procedure updates the dual
subproblem and solves it. If its optimal objective value equals 0 (or is
negative) then we have found an optimal solution for the original
problem and the algorithm terminates. If the optimal objective value is
larger than 0 then we create a feasibility cut using the level values of
the variables in the solution of the dual subproblem. This feasibility
cut is added to the master problem.

```
return when ( BendersAlgorithmFinished );
! Update Subproblem and solve it.
GMP::Benders::UpdateSubProblem( gmpS, gmpM, 1, round : 1 );
GMP::SolverSession::Execute( solsesS ) ;
GMP::Solution::RetrieveFromSolverSession( solsesS, 1 ) ;
! Check whether objective is 0 in which case optimality condition is satisfied.
ObjectiveSubproblem := GMP::SolverSession::GetObjective( solsesS );
if ( ObjectiveSubproblem <= BendersOptimalityTolerance ) then
if ( MasterHasBeenSolved ) then
return AlgorithmTerminate( 'Optimal' );
endif;
else
! Add feasibility cut to the Master problem.
NumberOfFeasibilityCuts += 1;
GMP::Benders::AddFeasibilityCut( gmpM, gmpS, 1, NumberOfFeasibilityCuts );
endif;
```