Procedure GMP::Benders::AddFeasibilityCut(GMP1, GMP2, solution, cutNo, tighten)

GMP::Benders::AddFeasibilityCut

The procedure GMP::Benders::AddFeasibilityCut generates a feasibility cut for a Benders’ master problem using the solution of a Benders’ subproblem (or the corresponding feasibility problem). This procedure is typically used in a Benders’ decomposition algorithm.

GMP::Benders::AddFeasibilityCut(
     GMP1,             ! (input) a generated mathematical program
     GMP2,             ! (input) a generated mathematical program
     solution,         ! (input) a solution
     cutNo,            ! (input) a scalar reference
     [tighten]         ! (optional, default 0) a scalar binary expression
)

Arguments

GMP1

An element in the set AllGeneratedMathematicalPrograms representing a Benders’ master problem.

GMP2

An element in the set AllGeneratedMathematicalPrograms representing a Benders’ subproblem (or the corresponding feasibility problem).

solution

An integer scalar reference to a solution of GMP2.

cutNo

An integer scalar reference to a cut number.

tighten

A scalar binary value to indicate whether the feasibility cut should be tightened. If the value is 1, tightening is attempted.

Return Value

The procedure returns 1 on success, or 0 otherwise.

Note

• The GMP1 should have been created using the function GMP::Benders::CreateMasterProblem.

• The GMP2 should have been created using the function GMP::Benders::CreateSubProblem or the function GMP::Instance::CreateFeasibility.

• If the GMP that was created by GMP::Benders::CreateSubProblem represents the dual of the Benders’ subproblem then this GMP should be used as argument GMP2. If it represents the primal of the Benders’ subproblem then first the feasibility problem should be created which then should be used as argument GMP2.

• The solution of the Benders’ subproblem or feasibility problem (represented by GMP2) is used to generate an optimality cut for the Benders’ master problem (represented by GMP1).

• A feasibility cut \(a^T x \geq b\) can be tightened to \(1^T x \geq 1\) if \(x\) is a vector of binary variables and \(a_i \geq b > 0\) for all \(i\).

Example

In the examples below we assume that the Benders’ subproblem is infeasible. The way GMP::Benders::AddFeasibilityCut is called depends on whether the primal or dual of the Benders’ subproblem was generated. In the first example we use the dual. In that case an unbounded extreme ray is used to create a feasibility cut. See Benders’ Decomposition - Textbook Algorithm of the Language Reference.

! Initialization.
myGMP := GMP::Instance::Generated( MP );

gmpM := GMP::Benders::CreateMasterProblem( myGMP, AllIntegerVariables,
                                           'BendersMasterProblem', 0, 0 );

gmpS := GMP::Benders::CreateSubProblem( myGMP, masterGMP, 'BendersSubProblem',
                                        useDual : 1, normalizationType : 0 );

NumberOfFeasibilityCuts := 1;

! Switch on solver option for calculating unbounded extreme ray.
GMP::Instance::SetOptionValue( gmpS, 'unbounded ray', 1 );

! First iteration of Benders' decomposition algorithm (simplified).
GMP::Instance::Solve( gmpM );

GMP::Benders::UpdateSubProblem( gmpS, gmpM, 1, round : 1 );

GMP::Instance::Solve( gmpS );

ProgramStatus := GMP::Solution::GetProgramStatus( gmpS, 1 ) ;
if ( ProgramStatus = 'Unbounded' ) then
    GMP::Benders::AddFeasibilityCut( gmpM, gmpS, 1, NumberOfFeasibilityCuts );
    NumberOfFeasibilityCuts += 1;
endif;

In the second example we use the primal of the Benders’ subproblem. If that problem turns out to be infeasible then we solve a feasibility problem to get a solution of minimum infeasibility (according to some measurement). The shadow prices of the constraints and the reduced costs of the variables in that solution are used to create a feasibility cut. See Benders’ Decomposition - Textbook Algorithm of the Language Reference.

! Initialization.
myGMP := GMP::Instance::Generated( MP );

gmpM := GMP::Benders::CreateMasterProblem( myGMP, AllIntegerVariables,
                                           'BendersMasterProblem', 0, 0 );

gmpS := GMP::Benders::CreateSubProblem( myGMP, masterGMP, 'BendersSubProblem',
                                        useDual : 0, normalizationType : 0 );

NumberOfFeasibilityCuts := 1;

! First iteration of Benders' decomposition algorithm (simplified).
GMP::Instance::Solve( gmpM );

GMP::Benders::UpdateSubProblem( gmpS, gmpM, 1, round : 1 );

GMP::Instance::Solve( gmpS );

ProgramStatus := GMP::Solution::GetProgramStatus( gmpS, 1 ) ;
if ( ProgramStatus = 'Infeasible' ) then
    gmpF := GMP::Instance::CreateFeasibility( gmpS, "FeasProb", useMinMax : 1 );

    GMP::Instance::Solve( gmpF );

    GMP::Benders::AddFeasibilityCut( gmpM, gmpF, 1, NumberOfFeasibilityCuts );
    NumberOfFeasibilityCuts += 1;
endif;

See also

The routines GMP::Benders::CreateMasterProblem, GMP::Benders::CreateSubProblem, GMP::Benders::AddOptimalityCut, GMP::Instance::CreateFeasibility, GMP::SolverSession::AddBendersFeasibilityCut and GMP::SolverSession::AddBendersOptimalityCut.