# Control Parameters That Influence the Algorithm

This section

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

Parameter `UseDual`

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.

Dual solution

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.

Feasibility problem

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
parameter `UseMinMaxForFeasibilityProblem`

which we discuss in
Feasibility Problem Mode. Also the parameter `NormalizationType`

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 `FeasibilityOnly`

In the next subsection we discuss the parameter `FeasibilityOnly`

.
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

Until now

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.

Reformulation

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 `GMP::Benders::CreateMasterProblem`

is
executed; the user will not notice anything inside his project.) For the
MIP problem of Problem Statement the reformulated
problem becomes:

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).

Parameter `FeasibilityOnly`

The parameter `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.

Primal subproblem

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.

Dual subproblem

We have seen before that if we use the dual of the subproblem and
parameter `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.
If parameter `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 `FeasibilityOnly`

and `UseDual`

equal
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.

Disadvantage

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

Normalization

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\).

Parameter `NormalizationType`

The parameter `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 `FeasibilityOnly`

.

Exception

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

Parameter `UseMinMaxForFeasibilityProblem`

The parameter `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 `NormalizationType`

. This
parameter is ignored if the parameter `UseDual`

equals 1.

## Tightening Constraints

Illustrative example

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
MIP example.

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.

Parameter `AddTighteningConstraints`

Adding tightening constraints to the master problem is controlled by the
parameter `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
constraints.

## Using a Starting Point

Parameter `UseStartingPointForMaster`

The parameter `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

Parameter `UsePresolver`

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 `UsePresolver`

can
be used to switch on the preprocessing step.