Quick Start to Using Benders’ Decomposition

System module

The system module with the name GMP Benders Decomposition implements the Benders’ decomposition algorithm. You can add this module to your project using the Install System Module command in the AIMMS Settings menu. This module contains three procedures that can be called, each implementing a different algorithm.

Classic algorithm

The procedure DoBendersDecompositionClassic inside this module implements the classic version of the Benders’ decomposition algorithm, in which the master problem and the subproblem are solved in an alternating sequence.

Modern algorithm

The procedure DoBendersDecompositionSingleMIP inside the module implements the modern approach for MIP problems which solves only a single MIP problem; the subproblem is solved whenever the MIP solver finds a solution for the master problem (using callbacks).

Two phase algorithm

The procedure DoBendersDecompositionTwoPhase inside the module implements a two phase algorithm for MIP problems. In the first phase it solves the relaxed problem (in which the integer variables become continuous) using the classic Benders decomposition algorithm. The Benders’ cuts found in the first phase are then added to the master problem in the second phase after which the MIP problem is solved using either the classic or modern approach of the Benders decomposition algorithm.

The procedure DoBendersDecompositionClassic

The procedure DoBendersDecompositionClassic has two input arguments:

1. MyGMP, an element parameter with range AllGeneratedMathematicalPrograms, and

2. MyMasterVariables, a subset of the predefined set AllVariables defining the variables in the master problem.

For a MIP problem, the integer variables typically become the variables of the master problem, although it is possible to also include continuous variables in the set of master problem variables. The DoBendersDecompositionClassic procedure is called as follows:

generatedMP := GMP::Instance::Generate( SymbolicMP );

GMPBenders::DoBendersDecompositionClassic( generatedMP, AllIntegerVariables );

Here SymbolicMP is the symbolic mathematical program containing the MIP model, and generatedMP is an element parameter in the predefined set AllGeneratedMathematicalPrograms. GMPBenders is the prefix of the Benders’ module. The implementation of this procedure will be discussed in Benders’ Decomposition - Textbook Algorithm.

The procedure DoBendersDecompositionSingleMIP

The procedure DoBendersDecompositionSingleMIP has the same input arguments as the procedure DoBendersDecompositionClassic. The DoBendersDecompositionSingleMIP procedure is called as follows:

generatedMP := GMP::Instance::Generate( SymbolicMP );

GMPBenders::DoBendersDecompositionSingleMIP( generatedMP, AllIntegerVariables );

This procedure can only be used if the original problem contains some integer variables. The implementation of this procedure will be discussed in Implementation of the Modern Algorithm.

The procedure DoBendersDecompositionTwoPhase

The procedure DoBendersDecompositionTwoPhase has one additional argument compared to the procedure DoBendersDecompositionClassic. Namely, the third argument UseSingleMIP is used to indicate whether the second phase should use the classic algorithm (value 0) or the modern algorithm (value 1). The procedure is called as follows if the modern algorithm should be used:

generatedMP := GMP::Instance::Generate( SymbolicMP );

GMPBenders::DoBendersDecompositionTwoPhase( generatedMP, AllIntegerVariables, 1 );

This procedure should only be used if the original problem contains some integer variables. The implementation of this procedure will be discussed in Implementation of the Two Phase Algorithm.

Combining procedure

To make it easier for you to switch between the three algorithms, the module also implements the procedure DoBendersDecomposition that calls one of the three procedures above based on the Benders’ mode. The first two arguments of this procedure are the same as before, namely MyGMP and MyMasterVariables. The third argument, BendersMode, is an element parameter that defines the Benders’ mode and can take value 'Classic', 'Modern', 'TwoPhaseClassic' or 'TwoPhaseModern'. The procedure is called as follows if the two phase algorithm should be used with the modern algorithm for the second phase:

generatedMP := GMP::Instance::Generate( SymbolicMP );

GMPBenders::DoBendersDecomposition( generatedMP, AllIntegerVariables,
                                    'TwoPhaseModern' );

If the problem contains no integer variables then only mode 'Classic' can be used.

Control parameters

The Benders’ module defines several parameters that influence the Benders’ decomposition algorithm. These parameters have a similar functionality as options of a solver, e.g., CPLEX. The most important parameters, with their default setting, are shown in this table.

Table 55 Control parameters in the Benders’ module

Parameter	Default	Range	Subsection
BendersOptimalityTolerance	1e-6	[0,1]
IterationLimit	1e7	{1,maxint}
TimeLimit	1e9	[0,inf)
CreateStatusFile	0	{0,1}
UseDual	0	{0,1}	Primal Versus Dual Subproblem
FeasibilityOnly	1	{0,1}	Subproblem as Pure Feasibility Problem
NormalizationType	1	{0,1}	Normalization of Feasibility Problem
UseMinMaxForFeasibilityProblem	1	{0,1}	Feasibility Problem Mode
AddTighteningConstraints	1	{0,1}	Tightening Constraints
UseStartingPointForMaster	0	{0,1}	Using a Starting Point
UsePresolver	0	{0,1}	Using the AIMMS Presolver

The parameters that are not self-explanatory are explained in Control Parameters That Influence the Algorithm; the last column in the table refers to the subsection that discusses the corresponding parameter.

Optimality tolerance

The optimality tolerance, as controlled by the parameter BendersOptimalityTolerance, guarantees that a solution returned by the Benders’ decomposition algorithm lies within a certain percentage of the optimal solution.

Solver options

The parameters BendersOptimalityTolerance, IterationLimit and TimeLimit are used by the classic algorithm (and the first phase of the two phase algorithm). For the modern algorithm, the corresponding general solver options, MIP_relative_optimality_tolerance, iteration_limit and time_limit respectively, are used.