The Decomposition Algorithm

DECOMP_MASTER_IP Statement

  • DECOMP_MASTER_IP <decomp-master-ip-options>;

  • MASTER_IP <decomp-master-ip-options>;

For mixed integer linear programming problems, the DECOMP_MASTER_IP statement controls the (restricted) master problem, which is solved as a MILP with the current set of columns in an effort to obtain an integer-feasible solution.

Table 15.14 summarizes the options available in the DECOMP_MASTER_IP statement. These options control the MILP solver that is used to solve the integer version of the master problem. For descriptions of these options, see the section MILP Solver Options in Chapter 8: The Mixed Integer Linear Programming Solver and the section PROC OPTMILP Statement in Chapter 13: The OPTMILP Procedure. Some options have different defaults when you use the decomposition algorithm, as shown in Table 15.14.

Table 15.14: Options in the DECOMP_MASTER_IP Statement

Description

decomp-master-ip-option

Different

   

Default

Presolve Option

   

Specifies the type of presolve

PRESOLVER=

 

Control Options

   

Specifies the stopping criterion based on an absolute objective gap

ABSOBJGAP=

 

Specifies the cutoff value for node removal

CUTOFF=

 

Emphasizes feasibility or optimality

EMPHASIS=

 

Specifies the maximum violation on variables and constraints

FEASTOL=

1E–7

Specifies the maximum allowed difference between an integer variable’s value and an integer

INTTOL=

 

Specifies how frequently to print the node log

LOGFREQ=

 

Specifies the level of detail of solution progress to print in the log

LOGLEVEL=

 

Specifies the maximum number of nodes to be processed

MAXNODES=

 

Specifies the maximum number of solutions to be found

MAXSOLS=

 

Specifies the time limit for the optimization process

MAXTIME=

 

Specifies the number of threads to use in the master integer solver

NTHREADS=

Specifies the tolerance used when deciding on the optimality of nodes in the branch-and-bound tree

OPTTOL=

1E–7

Specifies whether to use the previous best primal solution as a warm start

PRIMALIN=

 

Specifies the probing level

PROBE=

 

Specifies the stopping criterion based on a relative objective gap

RELOBJGAP=

0.01

Specifies the scale of the problem matrix

SCALE=

 

Specifies the stopping criterion based on the target objective value

TARGET=

 

Specifies whether time units are CPU time or real time

TIMETYPE=

 

Heuristics Option

   

Specifies the primal heuristics level

HEURISTICS=

 

Search Options

   

Specifies the level of conflict search

CONFLICTSEARCH=

 

Specifies the node selection strategy

NODESEL=

 

Specifies the restarting strategy

RESTARTS=

Specifies the initial seed for the random number generator

SEED=

 

Specifies the number of simplex iterations performed on each variable in strong branching strategy

STRONGITER=

 

Specifies the number of candidates for strong branching

STRONGLEN=

 

Specifies the level of symmetry detection

SYMMETRY=

 

Specifies the rule for selecting branching variable

VARSEL=

 

Cut Options

   

Specifies the cut level for all cuts

ALLCUTS=

 

Specifies the clique cut level

CUTCLIQUE=

 

Specifies the flow cover cut level

CUTFLOWCOVER=

 

Specifies the flow path cut level

CUTFLOWPATH=

 

Specifies the Gomory cut level

CUTGOMORY=

 

Specifies the generalized upper bound (GUB) cover cut level

CUTGUB=

 

Specifies the implied bounds cut level

CUTIMPLIED=

 

Specifies the knapsack cover cut level

CUTKNAPSACK=

 

Specifies the lift-and-project cut level

CUTLAP=

 

Specifies the mixed lifted 0-1 cut level

CUTMILIFTED=

 

Specifies the mixed integer rounding (MIR) cut level

CUTMIR=

 

Specifies the row multiplier factor for cuts

CUTSFACTOR=

 

Specifies the overall cut aggressiveness

CUTSTRATEGY=

 

Specifies the zero-half cut level

CUTZEROHALF=

 


† MAXNODES=100000 in the root node, and MAXNODES=10000 in nodes that are not the root.

The following options are listed in Table 15.14 but are not described in the MILP solver sections. These options are specific to the DECOMP_MASTER_IP statement.

NTHREADS=number

specifies the number of threads to use in the master integer solver (if the chosen solver method supports multithreading). By default, the number of threads is the same as the setting that is used for the NTHREADS= option in the DECOMP statement.

PRIMALIN=number | string
PIN=number | string

specifies whether the MILP solver is to use the previous best solution’s variables values as a starting solution (warm start). If the MILP solver finds that the input solution is feasible, then the input solution provides an incumbent solution and a bound for the branch-and-bound algorithm. If the solution is not feasible, the MILP solver tries to repair it. When it is difficult to find a good integer-feasible solution for a problem, warm start can reduce solution time significantly. Table 15.15 describes the valid values of the PRIMALIN= option.

Table 15.15: Values for PRIMALIN= Option

number

string

Description

0

OFF

Ignores the previous solution.

1

ON

Starts from the previous solution.


The default is ON.