Control Parameters That Influence the Algorithm
Some of the control parameters of this table can be used to influence the behavior of the Benders’ decomposition algorithm. We discuss these parameters in this section.
Primal Versus Dual Subproblem
In the textbook algorithm the dual of the subproblem is used. It is also
possible to use the primal of the subproblem instead. This is controlled
by the parameter
UseDual. By default the Benders’ decomposition
algorithm uses the primal subproblem.
If the primal subproblem is solved and it appears to be feasible then the dual solution is used to construct an optimality cut. By the dual solution we mean the shadow prices of the constraints and the reduced costs of the variables in the primal subproblem.
If the primal subproblem is infeasible then another problem is solved to find a solution of minimum infeasibility (according to some measurement). The feasibility problem of \(PS(x^*)\) (see Benders’ Decomposition - Textbook Algorithm) is denoted by \(PFS(x^*)\) and defined by:
Here \(z\) is a scalar variable. The dual solution of this feasibility problem is used to create a feasibility cut which is added to the master problem.
Alternative feasibility problem
The feasibility problem above minimizes the maximum infeasibility among
all constraints. It is also possible to minimize the sum of
infeasibilities over all constraints; this is controlled by the
UseMinMaxForFeasibilityProblem which we discuss in
Feasibility Problem Mode. Also the parameter
influences the formulation of the feasibility problem; see
Normalization of Feasibility Problem. Note that the feasibility problem is
always feasible and bounded. Note further that if the optimal objective
value of the feasibility problem is 0 or negative then the corresponding
subproblem is feasible.
Relationship with parameter
In the next subsection we discuss the parameter
This parameter has a big influence on how the subproblem is created, for
both the primal and dual subproblem. In some cases the subproblem can
become a pure feasibility problem.
Subproblem as Pure Feasibility Problem
By so far we assumed that the Benders’ decomposition algorithm first tries to solve the subproblem to optimality to either conclude that the combined solution of the master problem and subproblem forms an optimal solution for the original problem, or to create an optimality cut that is added to the master problem. If the primal or dual subproblem appears to be infeasible or unbounded respectively, then a feasibility problem is solved (if we used the primal subproblem) or an unbounded extreme ray is calculated (if we used the dual subproblem) to create a feasibility cut.
Benders’ subproblem always infeasible
For some problems the Benders’ subproblem will (almost) always be infeasible unless an optimal solution of the original problem is found. For example, assume that the variables that become part of the subproblem have no objective coefficients. (In the MIP problem of Problem Statement this is equivalent to the vector \(d\) being equal to 0.) In that case the Benders’ decomposition algorithm tries to find a solution for the master problem that remains feasible if we also consider the part of the model that became the subproblem. The algorithm is finished if such a solution is found. Until then all subproblems will be infeasible. In that case it is useless to try to solve the subproblem to optimality (which will always fail) but instead directly solve a feasibility problem for the subproblem.
It is possible to let the AIMMS automatically reformulate the original
problem such that the variables that become part of the subproblem have
no longer objective coefficients. (This reformulation exists only
temporary while the function
executed; the user will not notice anything inside his project.) For the
MIP problem of Problem Statement the reformulated
If we assign the new continuous variable \(\eta\), together with the integer variable \(x\), to the master problem then the subproblem variables no longer have objective coefficients. As a consequence, the subproblem will always be infeasible (unless an optimal solution is found).
FeasibilityOnly can be used to control whether AIMMS
should reformulate the original problem as explained above. AIMMS will
do so if the value of this parameter equals 1, which is the default
value. Also, if parameter
FeasibilityOnly equals 1 then the Benders’
decomposition algorithm will no longer solve the primal subproblem
before solving the feasibility problem. Instead it will directly solve
the feasibility problem.
After reformulating the original problem, the primal of the subproblem will be different from \(PS(x^*)\) of Benders’ Decomposition - Textbook Algorithm, namely:
We denote this primal subproblem by \(PS'(x^*,\eta^*)\). The feasibility problem will also become slightly different, as compared to \(PFS(x^*)\) of Primal Versus Dual Subproblem, namely:
We denote this feasibility problem by \(PFS'(x^*,\eta^*)\). If the optimal objective value of this feasibility problem is 0 or negative then we have found an optimal solution for the original problem, and the Benders’ decomposition algorithm terminates. Otherwise the dual solution of the feasibility problem is used to add a feasibility cut to the master problem, and the algorithm continues by solving the master problem.
We have seen before that if we use the dual of the subproblem and
FeasibilityOnly equals 0 then the Benders’ decomposition
algorithm will first solve the dual subproblem and, if that subproblem
is infeasible, use an unbounded extreme ray to create a feasibility cut.
FeasibilityOnly equals 1 then the algorithm follows a
different route. Consider the dual formulation of the above problem, the
feasibility problem for \(PS'(x^*,\eta^*)\):
Here \(1^T\) denotes a vector of all 1’s. We denote this problem by
\(DS'(x^*,\eta^*)\). This problem is always feasible and bounded.
The Benders’ decomposition algorithm uses this problem as the (dual)
subproblem if the parameters
1. If the optimal objective value of this problem is 0 or negative then
we have found an optimal solution for the original problem, and the
Benders’ decomposition algorithm terminates. Otherwise the solution of
this problem is used to add a feasibility cut to the master problem, and
the algorithm continues by solving the master problem.
A serious disadvantage of reformulating the problem, as done in this section, is that a first feasible solution (which will be optimal) for the original problem will be found just before the Benders’ decomposition algorithm terminates. This means that the “gap” between the lower and upper bound on the objective value is meaningless, and therefore this measurement of progress toward finding and proving optimality by the algorithm is not available. However, this disadvantage only occurs when using the classic Benders’ decomposition algorithm. For the modern approach in which only a single MIP problem is solved, see Implementation of the Modern Algorithm, the algorithm finds feasible solutions for the original problem during the solution process and therefore the “gap” exists.
Normalization of Feasibility Problem
In the previous subsection we introduced the dual subproblem \(DS'(x^*,\eta^*)\) which contains the normalization condition
In order to obtain better feasibility cuts, Fischetti et al. (in [FSZ10]) proposed another normalization condition. The matrix \(T\) often contains null constraints which correspond to constraints that do not depend on \(x\). These are “static” conditions in the subproblem that are always active. According to Fischetti et al. there is no reason to penalize the corresponding dual multiplier \(\pi_i\). The new normalization condition then becomes
where \(I(T)\) indexes the nonzero constraints of matrix \(T\).
NormalizationType controls which normalization
condition is used. If it equals 0 then normalization condition
(10) is used, else (11).
The Benders’ decomposition algorithm uses (11) by
default because various computational experiments showed a better
performance with this normalization condition.
Translation to primal subproblem
We can apply the normalization rule of Fischetti et al. also if we use the primal subproblem. In the corresponding feasibility problem, we then only add variable \(z\) for the nonzero rows of \(T\). The relevant constraints in \(PFS'(x^*,\eta^*)\) then become:
The feasibility problem can be normalized in this way regardless of the
setting of parameter
In case the parameter
UseDual equals 1 and the parameter
FeasibilityOnly equals 0 then no feasibility problem is solved to
derive a feasibility cut. Instead an unbounded extreme ray for the
unbounded dual subproblem is used. Therefore, in that case the parameter
NormalizationType is ignored.
Feasibility Problem Mode
UseMinMaxForFeasibilityProblem determines what kind of
infeasibility is minimized: the maximum infeasibility among all
constraints (value 1, the default) or the sum of infeasibilities over
all constraints (value 0). If the sum of the infeasibilities over all
constraints is used then also the normalization rule of Fischetti et al.
can be used, as controlled by the parameter
parameter is ignored if the parameter
UseDual equals 1.
If the Benders’ master problem is created, using the function
GMP::Benders::CreateMasterProblem, then AIMMS can try to
automatically add valid constraints to the master problem that will cut
off some infeasible solutions. This is best illustrated by the following
We assume that \(u\) and \(b\) are strictly positive parameters. The binary variable \(x\) is assigned to the master problem and the continuous variable \(y\) to the subproblem. For this example, the initial master problem has no constraints (besides the integrality restriction on \(x\)) and therefore \(x=0\) is the optimal solution of the initial master problem. Clearly, for \(x=0\) our MIP example has no solution. Adding the constraint
to the master problem cuts off the \(x=0\) solution. Note that this constraint is redundant in the original MIP example. By adding these kind of master-problem-tightening constraints we hope that the Benders’ decomposition algorithm requires less iterations to find an optimal solution.
Adding tightening constraints to the master problem is controlled by the
AddTighteningConstraints. If this parameter equals 1, its
default, then AIMMS will try to find and add tightening constraints.
Computational experiments indicate that in general the Benders’
decomposition algorithm benefits from adding these tightening
Using a Starting Point
UseStartingPointForMaster can be used to let the
classic Benders’ decomposition algorithm start from a “good” solution.
This solution can be obtained from a heuristic and must be a feasible
solution for the master problem. The solution should be copied into the
level suffix of the problem variables before the Benders’ decomposition
algorithm is called. If this parameter is set to 1 then the algorithm
will skip the solve of the first master problem. Instead, the master
problem variable \(x^*\) will be fixed in the subproblem
\(PS(x^*)\) according to the starting point, and the algorithm will
continue by solving the subproblem.
Using the AIMMS Presolver
The Benders’ decomposition algorithm can use the AIMMS Presolver at the
start. In that case the algorithm will use the preprocessed model
instead of the original model. By preprocessing the model it might
become smaller and easier to solve. The parameter
be used to switch on the preprocessing step.