Benders strategy

This parameter specifies whether CPLEX should apply Benders algorithm as a strategy to solve a model.

Purpose

Benders decomposition algorithm as a strategy

API	Parameter Name
C	CPXPARAM_Benders_Strategy
C++	IloCplex::Param::Benders::Strategy
Java	IloCplex.Param.Benders.Strategy
.NET	Cplex.Param.Benders.Strategy
OPL	bendersstrategy
Python	parameters.benders.strategy
MATLAB	Cplex.Param.benders.strategy
Interactive	benders strategy value
Identifier	1501

Description

Given a formulation of a problem, CPLEX can decompose the model into a single master and (possibly multiple) subproblems. To do so, CPLEX can make use of annotations that you supply for your model. The strategy can be applied to mixed-integer linear programs (MILP). For certain types of problems, this approach offers significant performance improvements as subproblems can be solved in parallel.

For mixed integer programs (MIP), under certain conditions, CPLEX can apply Benders algorithm to improve the search to find more feasible solutions more quickly.

Tolerances for Benders

These other CPLEX parameters allow you to specify cut tolerances particular to Benders:

Strategies

By default, if you did not annotate your model to specify a decomposition, CPLEX executes conventional branch and bound. If you annotated your model, CPLEX attempts to apply your annotations and to refine your decomposition before it solves the model. With this parameter, you can direct CPLEX to decompose your model and to apply its implementation of Benders algorithm in one of these alternative ways:

1 USER: CPLEX attempts to decompose your model strictly according to your annotations.
2 WORKERS: CPLEX decomposes your model by using your annotations as hints and refining the decomposition where it can.
- CPLEX initially decomposes your model according to your annotations.
- Cplex then attempts to refine that decomposition by further decomposing the specified subproblems.
This approach can be useful if you annotate certain variables to go into master, and all others to go into a single subproblem, which CPLEX can then decompose further for you.
3 FULL: CPLEX automatically decomposes your model, ignoring any annotations you may have supplied.
- CPLEX puts all integer variables into the master.
- CPLEX puts all continuous variables into a subproblem.
- CPLEX further decomposes that subproblem, if possible.

Annotations for decomposition

If you want to specify a decomposition to CPLEX, you use annotations. First, create a new annotation cpxBendersPartition of type long. Next, use cpxBendersPartition to annotate some or all of the variables in your model. These annotations specify to CPLEX whether certain variables belong to the master or to one of the subproblems assigned to workers (where the subproblems are numbered from 1 (one) to N, the number of subproblems).

If you annotate a given variable with the value 0 (zero), CPLEX assigns that variable to the master.
If you do not annotate a given variable, CPLEX assumes the default value annotation.
If you annotate a given variable with the value i, where i is greater than or equal to 1 (one), CPLEX assigns that variable to subproblem i.
If you annotate a given variable with a value strictly less than zero, CPLEX raises an error CPXERR_NO_DECOMPOSITION.

CPLEX produces an error CPXERR_BAD_DECOMPOSITION if the annotated decomposition does not yield disjoint subproblems. For example, if your annotations specify that two (or more) variables belong in different subproblems, yet your model specifies that these variables participate in the same constraint, then these variables are linked. Consequently, the subproblems where these variables appear according to your annotations are not disjoint with respect to the partition.

Tip: It is a good idea to verify that the N subproblems plus master actually define a complete decomposition of the original model into disjoint subproblems. That is, make sure you have a complete partition for your decomposition into disjoint subproblems.

Benders without annotations

If you want CPLEX to apply a Benders strategy as it solves your problem, but you do not specify cpxBendersPartition annotations yourself, CPLEX puts all integer variables in master and continuous linear variables into subproblems.

Errors in automatic decomposition

When you specify a Benders strategy, but you do not annotate your model, CPLEX attempts to partition the variables into a Benders decomposition. In such a case, if there are no integer variables in your model, or if there are no continuous variables in your model, CPLEX raises an error (CPXERR_BAD_DECOMPOSITION or CPXERR_NO_DECOMPOSITION) stating that it cannot automatically decompose the model to apply a Benders strategy.

Table 1. Values
Value	Name	Meaning
-1	OFF	Execute conventional branch and bound; ignore any Benders annotations. That is, do not use Benders algorithm even if a Benders partition of the current model is present
0	AUTO	default Let CPLEX decide. case 1: If the user supplies no annotations with the model, CPLEX executes conventional branch and bound. case 2: If annotations specifying a Benders partition of the current model are available, CPLEX attempts to decompose the model. CPLEX uses the master as given by the annotations, and attempts to partition the subproblems further, if possible, before applying Benders algorithm to solve the model. If the user supplied annotations, but the annotations supplied do not lead to a complete decomposition into master and disjoint subproblems (that is, if the annotations are wrong in that sense), CPLEX produces the error CPXERR_BAD_DECOMPOSITION.
1	USER	CPLEX applies Benders algorithm to a decomposition based on annotations supplied by the user. If no annotations to decompose the model are available, this setting produces the error CPXERR_NO_DECOMPOSITION. If the user supplies annotations, but the supplied annotations do not lead to a complete partition of the original model into disjoint master and subproblems, then this setting produces the error CPXERR_BAD_DECOMPOSITION.
2	WORKERS	CPLEX accepts the master as given and attempts to decompose the remaining elements into disjoint subproblems to assign to workers. It then solves the Benders decomposition of the model. If no annotations to decompose the model are available, this setting produces the error CPXERR_NO_DECOMPOSITION. If the user supplies annotations, but the supplied annotations do not lead to a complete partition of the original model into disjoint master and subproblems, then this setting produces the error CPXERR_BAD_DECOMPOSITION.
3	FULL	CPLEX ignores any annotation file supplied with the model; CPLEX applies presolve; CPLEX then automatically generates a Benders partition, putting integer variables in master and continuous linear variables into disjoint subproblems. CPLEX then solves the Benders decomposition of the model. If the problem is a strictly linear program (LP), that is, there are no integer-constrained variables to put into master, then CPLEX reports the error CPXERR_PARAM_INCOMPATIBLE. If the problem is a mixed integer linear program (MILP) where all variables are integer-constrained, (that is, there are no continuous linear variables to decompose into disjoint subproblems) then CPLEX reports the error CPXERR_NO_DECOMPOSITION. If the problem is a mixed integer linear program (MILP) where all variables are continuous, (that is, there are no integer-constrained variables to decompose into master) then CPLEX reports the error CPXERR_NO_DECOMPOSITION.