The NEOS Server offers SBB for the solution of mixed integer nonlinearly
constrained optimization problems in GAMS
SBB is based on a combination of the standard branch and bound method known
from mixed integer linear programming and nonlinear programming solvers
supported by GAMS.
Initially, the Relaxed Mixed Integer Nonlinear Programming (RMINLP)
model is solved using the initial values provided by the modeler. SBB
will stop immediately if the RMINLP model is unbounded or infeasible
or fails. 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 the current non-integer
solutions off. 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 each of these NLP
submodel are 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 indeed 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 then 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 there may exist better solutions in other
unexplored parts of the search space.
SBB was developed by
ARKI Consulting and Development
Bagsvaerdvej 246 A
DK-2880 Bagsvaerd, Denmark
Using the NEOS Server for SBB
The user must submit a model in GAMS
format to solve an optimization problem. For security purposes, the model
submitted must adhere to the following conventions:
If you are unfamiliar with GAMS, the
gives a quick introduction to the essentials of a GAMS model and the
output provided when the model is solved. Examples of models in GAMS
format can be found in the
GAMS model library and an
is also available.
- The model must be self contained, i.e. no $include or $batinclude
- No execution of external programs is allowed, i.e. no $call or execute
- No file creation, i.e. no put files or $echo
An option file can be used to specify SBB options. Currently, the NEOS
Server can only use optfile=1 with GAMS input. Therefore, any model
that specifies a different options file will not work as intended.
The NEOS Server initially limits the amount of output generated in the
listing file by turning off the symbol and unique element list, symbol
cross references, and restricting the rows and columns listed to zero.
This behavior can be changed by specifying the appropriate options
in the model file. See the
documentation on the
modeling language for further information.