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;