Table of Contents
Introduction
SBB is a GAMS solver for Mixed Integer Nonlinear Programming (MINLP) models. It is based on a combination of the standard Branch and Bound (B&B) method known from Mixed Integer Linear Programming and some of the standard NLP solvers already supported by GAMS. SBB can use all GAMS NLP solvers as subsolvers but it works best with NLP solvers that can utilize a near optimal point as a starting point like Conopt, Minos, and Snopt.
SBB supports all types of discrete variables supported by GAMS, including Binary, Integer, Semicont, Semiint, Sos1, and Sos2.
The Branch and Bound Algorithm
The Relaxed Mixed Integer Nonlinear Programming (RMINLP) model is initially solved using the starting point provided by the modeler. SBB will stop immediately if the RMINLP model is unbounded or infeasible, or if it fails (see option infeasseq
and failseq
below for an exception). If all discrete variables in the RMINLP model are integer, SBB will return this solution as the optimal integer solution. Otherwise, the current solution is stored and the Branch and Bound procedure will start.
During the Branch and Bound process, the feasible region for the discrete variables is subdivided, and bounds on discrete variables are tightened to new integer values to cut off the current non-integer solutions. Each time a bound is tightened, a new, tighter NLP submodel is solved starting from the optimal solution to the previous looser submodel. The objective function values from the NLP submodel is assumed to be lower bounds on the objective in the restricted feasible space (assuming minimization), even though the local optimum found by the NLP solver may not be a global optimum. If the NLP solver returns a Locally Infeasible status for a submodel, it is usually assumed that there is no feasible solution to the submodel, even though the infeasibility only has been determined locally (see option infeasseq
below for an exception). If the model is convex, these assumptions will be satisfied and SBB will provide correct bounds. If the model is not convex, the objective bounds may not be correct and better solutions may exist in other, unexplored parts of the search space.
SBB with Pseudo Costs
Over the last decades quite a number of search strategies have been successfully introduced for mixed integer linear programming (for details see e.g. J.T. Linderoth and M.W.P. Savelsbergh, A Computational Study of Search Strategies for Mixed Integer Programming, INFORMS Journal on Computing, 11(2), 1999). Pseudo costs are key elements of sophisticated search strategies. Using pseudo costs, we can estimate the degradation of the objective function if we move a fractional variable to a close integer value. Naturally, the variable selection can be based on pseudo costs (see SBB option varsel
). Node selection can also make use of pseudo cost: If we can estimate the change of the objective for moving one fractional variable to the closed integer value, we can then aggregate this change for all fractional variables, to estimate the objective of the best integer solution reachable from a particular node (see SBB option nodesel
).
Unfortunately, the computation of pseudo cost can be a substantial part of the overall computation. Models with a large number of fractional variables in the root node are not good candidates for search strategies which require pseudo costs (varsel 3, nodesel 3,5,6
). The impact (positive or negative) of using pseudo cost depends significantly on the particular model. At this stage, general statements are difficult to make.
Selecting pseudo cost related search strategies (varsel 3, nodesel 3,5,6
) may use computation time which sometimes does not pay off. However, we encourage the user to try these options for difficult models which require a large number of branch-and-bound nodes to solve.
The SBB Options
SBB works like other GAMS solvers, and many options can be set in the GAMS model. The most relevant GAMS options are IterLim, ResLim, NodLim, OptCA, OptCR, OptfFile, Cheat, and CutOff. A description of all available GAMS options can be found in the GAMS User's Guide Solver related options. GAMS options PriorOpt and TryInt are also accepted by SBB.
SBB uses the var.prior
information to select the fractional variable with the smallest priority during the variable selection process. SBB uses the TryInt information to set the branching direction in the B&B algorithm. At the beginning, SBB looks at the levels of the discrete variables provided by the user and if Abs(Round(x.l)-x.l) < m.TryInt, SBB will branch on that variable in the direction of Round(x.l). For example, x.l=0.9 and m.TryInt=0.2. We have Abs(Round(0.9)-0.9)=0.1 < 0.2, so when SBB decides to branch on this variable (because it is fractional, lets say with value 0.5), the node explored next will have the additional constraint x \(\geq\) 1 (the node with x \(\leq\) 0 will be explored later). If everything goes well (there is the chance that we end up in a different local optima in the subsolves for non-convex problems), SBB should reproduce a preset incumbent solution in a couple of nodes.
If you specify <modelname>.OptFile = 1;
before the Solve statement in your GAMS model, SBB will then look for and read an option file with the name sbb.opt
(see The Solver Option File for general use of solver option files). Unless explicitly specified in the SBB option file, the NLP subsolvers will not read an option file. The syntax for the SBB option file is
optname value
with one option on each line.
For example,
rootsolver conopt.1 subsolver snopt loginterval 10
The first two lines determine the NLP subsolvers for the Branch and Bound procedure. CONOPT with the option file conopt.opt
will be used for solving the root node. SNOPT with no option file will be used for the remaining nodes. The last option determines the frequency for log line printing. Every 10th node, and each node with a new integer solution, causes a log line to be printed. The following options are implemented:
Option | Description | Default |
---|---|---|
acceptnonopt | accepts feasible solution from subsolver | 0 |
avgresmult | average resource multiplicator | 5 |
dfsstay | keeps DFS node selection after solution has been found | 0 |
epint | integer feasibility tolerance | 1.0e-5 |
failseq | solver sequence for failed nodes | |
infeasseq | solver sequence for infeasible nodes | |
intsollim | maximum number of integer solutions | 2100000000 |
loginterval | progress display interval | 1 |
loglevel | level of solver display | 1 |
memnodes | maximum number of nodes in memory | 10000 |
miptrace | filename of MIP trace file | |
miptracenode | node interval when a trace record is written | 100 |
miptracetime | time interval when a trace record is written | 5.0 |
nodesel | node selection strategy | 0 |
printbbinfo | prints additional node info | 0 |
rootsolver | solver for the root node | GAMS NLP solver |
solvelink | Solvelink for GAMS NLP solver | 5 |
subiter | iteration limit for the subsolve | GAMS iterlim |
subres | resource limit for the subsolve | GAMS reslim |
subsolver | solver for the subproblems | GAMS NLP solver |
usercallparmfile | Command-line parameter include file used in GAMS command-line calls triggered by BCH | |
usergdxname | the name of the GDX file exported from the solver with the solution at the node | bchout.gdx |
usergdxnameinc | the name of the GDX file exported from the solver with the incumbent solution | bchout_i.gdx |
userheurcall | the GAMS command line to call the heuristic | |
userheurfirst | calls the cut generator for the first n nodes | 10 |
userheurfreq | determines the frequency of the cut generator model calls | 10 |
userheurinterval | determines the interval when to apply the multiplier for the frequency of the cut generator model calls | 100 |
userheurmult | determines the multiplier for the frequency of the cut generator model calls | 2 |
userheurnewint | calls the heuristic if the solver found a new integer feasible solution | 0 |
userheurobjfirst | Similar to UserHeurFirst but only calls the heuristic if the relaxed objective promises an improvement | 50 |
varsel | variable selection strategy at each node | 0 |
acceptnonopt (boolean): accepts feasible solution from subsolver ↵
If this option is set to 1 and the subsolver terminates with solver status Terminated by Solver and model status Intermediate Nonoptimal SBB takes this as a good solution and keeps on going. In default mode such a return is treated as a subsolver failure and the failseq is consulted.
Default:
0
avgresmult (integer): average resource multiplicator ↵
Similar to subres, this option allows the user to control the time limit spend in a node. SBB keeps track of how much time is spent in the nodes, and builds an average over time. This average multiplied by the factor
avgresmult
is set as a time limit for solving a node in the B&B tree. If the NLP solver exceeds this limit it is handled like a failure: the node is ignored or the solvers in the failseq are called. The default multiplieravgresmult
is 5. Settingavgresmult
to 0 will disable the automatic time limit feature. A multiplier is not very useful for very small node solution times; therefore, independent of each node, SBB grants the solver at least 5 seconds to solve the node. The competing option subres overwrites the automatically generated resource limit.Default:
5
dfsstay (integer): keeps DFS node selection after solution has been found ↵
If the node selection is a B*⁄DFS mix, SBB switches frequently to DFS node selection mode. It switches back into B* node selection mode, if no subnodes were created (new int, pruned, infeasible, fail). It can be advantageous to search the neighborhood of the last node also in a DFS manner. Setting
dfsstay
to n instructs SBB to stay in DFS mode for another n nodes.Default:
0
epint (real): integer feasibility tolerance ↵
The integer infeasibility tolerance.
Range: [
1e-9
,1
]Default:
1.0e-5
failseq (string): solver sequence for failed nodes ↵
solver1[.n1] solver2[.n2] ...
wheresolver1
is the name of a GAMS NLP solver to be used if the default solver fails, i.e., if it was not stopped by an iteration, resource, or domain limit and does not return a locally optimal or locally infeasible solution.n1
is the value of optfile passed to the alternative NLP solver. If.n1
is left blank it is interpreted as zero. Similarly,solver2
is the name of a GAMS NLP solver that is used ifsolver1
fails, andn2
is the value of optfile passed to the second NLP solver. If you have a difficult model where solver failures are not unlikely, you may add moresolver.n
pairs. You can use the same solver several times with different options files.failseq conopt conopt.2 conopt.3
means to try CONOPT with no options file. If this approach also fails, try CONOPT with options fileconopt.op2
, and if it again fails, try CONOPT with options fileconopt.op3
. If all solver and options file combinations fail the node will be labeled ignored and the node will not be explored further. The default is to try only one solver (therootsolver
orsubsolver
) and to ignore nodes with a solver failure.
infeasseq (string): solver sequence for infeasible nodes ↵
level solver1[.n1] solver2[.n2] ...
The purpose ofinfeasseq
is to avoid cutting parts of the search tree that appear to be infeasible but really are feasible. If the NLP solver labels a node Locally Infeasible and the model is not convex a feasible solution may actually exist. If SBB is high in the search tree it can be very drastic to prune the node immediately. SBB is therefore directed to try the solver/option combinations in the list as long as the depth in the search tree is less than the integer valuelevel
. If the list is exhausted without finding a feasible solution, the node is assumed to be infeasible. The default is to trust that Locally Infeasible nodes are indeed infeasible and to remove them from further consideration.
intsollim (integer): maximum number of integer solutions ↵
Maximum number of integer solutions. If this number is exceeded, SBB will terminate and return the best solution found so far.
Default:
2100000000
loginterval (integer): progress display interval ↵
The interval (number of nodes) for which log lines are written.
Default:
1
loglevel (integer): level of solver display ↵
The level of log output.
Default:
1
value meaning 0
only SBB log lines with one line every loginterval nodes 1
NLP solver log for the root node plus SBB loglines as 0 2
NLP solver log for all nodes plus SBB log lines as 0
memnodes (integer): maximum number of nodes in memory ↵
The maximum number of nodes SBB can have in memory. If this number is exceeded, SBB will terminate and return the best solution found so far.
Default:
10000
miptrace (string): filename of MIP trace file ↵
More info is available in chapter Solve trace
miptracenode (integer): node interval when a trace record is written ↵
More info is available in chapter Solve trace
Default:
100
miptracetime (real): time interval when a trace record is written ↵
More info is available in chapter Solve trace
Default:
5.0
nodesel (integer): node selection strategy ↵
Node selection scheme.
Default:
0
value meaning 0
automatic 1
Depth First Search (DFS) 2
Best Bound (BB) 3
Best Estimate (BE) 4
DFS/BB mix 5
DFS/BE mix 6
DFS/BB/BE mix
printbbinfo (integer): prints additional node info ↵
Additional info of log output.
Default:
0
value meaning 0
print no additional info 1
print variable selection letter
The node and variable selection for the current node are indicated by a two letter code at the end of the log line. The first letter represents the node selection: D for DFS, B for Best Bound, and E for Best Estimate. The second letter represents the variable selection: X for maximum infeasibility, N for minimum infeasibility, and P for pseudo cost.2
print best estimate
rootsolver (string): solver for the root node ↵
solver[.n]
Solver is the name of the GAMS NLP solver that should be used in the root node, andn
is the integer corresponding to optfile for the root node. If.n
is missing, the optfile treated as zero i.e. the NLP solver will not look for an options file. This SBB option can be used to overwrite the default that uses the NLP solver specified with anOption NLP = solver;
statement or the default GAMS solver for NLP.Default:
GAMS NLP solver
solvelink (integer): Solvelink for GAMS NLP solver ↵
Default:
5
value meaning 1
Call GAMS NLP solver via script 2
Call GAMS NLP solver via module 5
Call GAMS NLP solver in memory
subiter (integer): iteration limit for the subsolve ↵
The default for
subiter
passed on throughiterlim
. Similar to subres but sets the iteration limit for solving a node in the B&B tree.Default:
GAMS iterlim
subres (real): resource limit for the subsolve ↵
The default for
subres
passed on throughreslim
. Sets the time limit in seconds for solving a node in the B&B tree. If the NLP solver exceeds this limit it is handled like a failure and the node is ignored, or the solvers in the failseq are called.Default:
GAMS reslim
subsolver (string): solver for the subproblems ↵
solver[.n]
Similar to rootsolver but applied to the subnodes.Default:
GAMS NLP solver
usercallparmfile (string): Command-line parameter include file used in GAMS command-line calls triggered by BCH ↵
usergdxname (string): the name of the GDX file exported from the solver with the solution at the node ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
bchout.gdx
usergdxnameinc (string): the name of the GDX file exported from the solver with the incumbent solution ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
bchout_i.gdx
userheurcall (string): the GAMS command line to call the heuristic ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
userheurfirst (integer): calls the cut generator for the first n nodes ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
10
userheurfreq (integer): determines the frequency of the cut generator model calls ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
10
userheurinterval (integer): determines the interval when to apply the multiplier for the frequency of the cut generator model calls ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
100
userheurmult (integer): determines the multiplier for the frequency of the cut generator model calls ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
2
userheurnewint (boolean): calls the heuristic if the solver found a new integer feasible solution ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
0
userheurobjfirst (integer): Similar to UserHeurFirst but only calls the heuristic if the relaxed objective promises an improvement ↵
More info is available in chapter The GAMS Branch-and-Cut-and-Heuristic Facility.
Default:
50
varsel (integer): variable selection strategy at each node ↵
Variable selection scheme.
Default:
0
value meaning 0
automatic 1
maximum integer infeasibility 2
minimum integer infeasibility 3
pseudo costs
The SBB Log File
The SBB Log file (usually directed to the screen) can be controlled with the loginterval
and loglevel
options in SBB. It will by default first show the iteration output from the NLP solver that solves the root node. This is followed by output from SBB describing the search tree. An example of this search tree output follows:
Root node solved locally optimal. Node Act. Lev. Objective IInf Best Int. Best Bound Gap (2 secs) 0 0 0 8457.6878 3 - 8457.6878 - 1 1 1 8491.2869 2 - 8457.6878 - 2 2 2 8518.1779 1 - 8457.6878 - * 3 3 3 9338.1020 0 9338.1020 8457.6878 0.1041 4 2 1 pruned - 9338.1020 8491.2869 0.0997 Solution satisfies optcr Statistics: Iterations : 90 NLP Seconds : 0.110000 B&B nodes : 3 MIP solution : 9338.101979 found in node 3 Best possible : 8491.286941 Absolute gap : 846.815039 optca : 0.000000 Relative gap : 0.099728 optcr : 0.100000 Model Status : 8 Solver Status : 1 NLP Solver Statistics Total Number of NLP solves : 7 Total Number of NLP failures: 0 Details: conopt # execs 7 # failures 0 Terminating.
The fields in the log are:
Field | Description |
---|---|
Node | The number of the current node. The root node is node 0. |
Act | The number of active nodes defined as the number of subnodes that have not yet been solved. |
Lev | The level in the search tree, i.e., the number of branches needed to reach this node. |
Objective | The objective function value for the node. A numerical value indicates that the node was solved and the objective was good enough for the node to not be ignored. "pruned" indicates that the objective value was worse than the Best Integer value, "infeasible" indicates that the node was Infeasible or Locally Infeasible, and "ignored" indicates that the node could not be solved (see under failseq above). |
IInf | The number of integer infeasibilities, i.e. the number of variables that are supposed to be binary or integer that do not satisfy the integrality requirement. Semi continuous variables and SOS variables may also contribute to IInf . |
Best Int | The value of the best integer solution found so far. A dash (-) indicates that an integer solution has not yet been found. A star (*) in column one indicates that the node is integer and that the solution is better than the best yet found. |
Best Bound | The minimum value of "Objective" for the subnodes that have not been solved yet (maximum for maximization models). For convex models, Best Bound will increase monotonically. For nonconvex models, Best Bound may decrease, indicating that the Objective value for a node was not a valid lower bound for that node. |
Gap | The relative gap between the Best Integer solution and the Best Bound. |
The remaining part of the Log file displays various solution statistics similar to those provided by the MIP solvers. This information can also be found in the Solver Status area of the GAMS listing file.
The following Log file shows cases where the NLP solver fails to solve a subnode. The text "ignored" in the Objective field shows the failure, and the values in parenthesis following the Gap field are the Solve and Model status returned by the NLP solver:
Root node solved locally optimal. Node Act. Lev. Objective IInf Best Int. Best Bound Gap (2 secs) 0 0 0 6046.0186 12 - 6046.0186 - 1 1 1 infeasible - - 6046.0186 - 2 0 1 6042.0995 10 - 6042.0995 - 3 1 2 ignored - - 6042.0995 - (4,6) 4 0 2 5804.5856 8 - 5804.5856 - 5 1 3 ignored - - 5804.5856 - (4,7)
The next Log file shows the effect of the infeasseq
and failseq
options on the model above. CONOPT with options file conopt.opt (the default solver and options file pair for this model) considers the first subnode to be locally infeasible. CONOPT, MINOS, and SNOPT, all with no options file, are therefore tried in sequence. In this case, they all declare the node infeasible and it is considered to be infeasible.
In node 3, CONOPT with option file fails but CONOPT without option file finds a Locally Optimal solution, and this solution is then used for further search. The SBB option file for the following run would be:
rootsolver conopt.1 subsolver conopt.1 failseq conopt infeasseq 100 conopt minos snopt
The log looks as follows:
Root node solved locally optimal. Node Act. Lev. Objective IInf Best Int. Best Bound Gap (2 secs) 0 0 0 6046.0186 12 - 6046.0186 - conopt.1 reports locally infeasible Executing conopt conopt reports locally infeasible Executing minos minos reports locally infeasible Executing snopt 1 1 1 infeasible - - 6046.0186 - 2 0 1 6042.0995 10 - 6042.0995 - conopt.1 failed. 4 TERMINATED BY SOLVER, 7 FEASIBLE SOLUTION Executing conopt 3 1 2 4790.2373 8 - 6042.0995 - 4 2 3 4481.4156 6 - 6042.0995 - conopt.1 reports locally infeasible Executing conopt conopt reports locally infeasible Executing minos minos failed. 4 TERMINATED BY SOLVER, 6 INTERMEDIATE INFEASIBLE Executing snopt 5 3 4 infeasible - - 6042.0995 - 6 2 4 4480.3778 4 - 6042.0995 -
The Log file shows a solver statistic at the end, summarizing how many times an NLP was executed and how often it failed:
NLP Solver Statistics Total Number of NLP solves : 45 Total Number of NLP failures: 13 Details: conopt minos snopt # execs 34 3 8 # failures 4 3 6
The solutions found by the NLP solver to the subproblems in the Branch and Bound may not be the global optima. Therefore, the objective can improve even though we restrict the problem by tightening some bounds. These jumps of the objective in the wrong direction which might also have an impact on the best bound/possible are reported in a separate statistic:
Non convex model! # jumps in best bound : 2 Maximum jump in best bound : 20.626587 in node 13 # jumps to better objective : 2 Maximum jump in objective : 20.626587 in node 13
Comparison of SBB and other MINLP Solvers
GAMS offers a variety of MINLP solvers including local and global MINLP solver. They implement different algorithms and it is usually unclear which solver performs best. Here we give a brief comparison between SBB and the well known solver DICOPT.
DICOPT is based on the outer approximation method. Initially, the RMINLP model is solved just as in SBB. The model is then linearized around this point and a linear MIP model is solved. The discrete variables are then fixed at the optimal values from the MIP model, and the resulting NLP model is solved. If the NLP model is feasible, we have an integer feasible solution.
The model is linearized again and a new MIP model with both the old and new linearized constraints is solved. The discrete variables are again fixed at the optimal values, and a new NLP model is solved.
The process stops when the MIP model becomes infeasible, when the NLP solution becomes worse, or, in some cases, when bounds derived from the MIP model indicate that it is safe to stop.
DICOPT is based on the assumption that MIP models can be solved efficiently while NLP models can be expensive and difficult to solve. The MIP models try to approximate the NLP model over a large area and solve it using much cheaper linear technology. Ideally, only a few NLPs must be solved.
DICOPT can experience difficulties solving models, if many or all the NLP submodels are infeasible. DICOPT can also have problems if the linearizations used for the MIP model create ill-conditioned models. The MIP models may become very difficult to solve, and the results from the MIP models may be poor as initial values for the NLP models. The linearized constraint used by DICOPT may also exclude certain areas of the feasible space from consideration.
SBB uses different assumptions and works very differently. Most of the work in SBB involves solving NLP models. Since the NLP submodels differ only in one or a few bounds, the assumption is that the NLP models can be solved quickly using a good restart procedure. Since the NLP models differ very little and good initial values are available, the solution process will be fairly reliable compared to the solution process in DICOPT, where initial values of good quality seldom are available. Because search space is reduced based on very different grounds than in DICOPT, other solutions may therefore be explored.
Overall, DICOPT should perform better on models that have a significant and difficult combinatorial part, while SBB may perform better on models that have fewer discrete variables but more difficult nonlinearities (and possibly also on models that are fairly non convex).