MinlpSolve
Purpose
Branch & Bound algorithm for Mixed-Integer Nonlinear Programming (MINLP) with convex or nonconvex sub problems using NLP relaxation (Formulated as minlp-IP).
The parameter Convex (see below) determines if to assume the NLP subproblems are convex or not.
minlpSolve depends on a suitable NLP solver.
minlpSolve solves problems of the form
Failed to parse (unknown function "\multicolumn"): {\displaystyle \begin{array}{cccccc} \min\limits_{x} & f(x) \\s/t & x_{L} & \leq & x & \leq & x_{U} \\& b_{L} & \leq & Ax & \leq & b_{U} \\& c_{L} & \leq & c(x) & \leq & c_{U} \\& & & \multicolumn{3}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \in $I$} \\ \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle x,x_{L},x_{U}\in \MATHSET{R}^{n}}
, Failed to parse (unknown function "\MATHSET"): {\displaystyle c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}}
, Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\in \MATHSET{R}^{m_{2}\times n}}
and
Failed to parse (unknown function "\MATHSET"): {\displaystyle b_{L},b_{U}\in \MATHSET{R}^{m_{2}}}
. The variables , the
index subset of are restricted to be integers.
Calling Syntax
Result = tomRun('minlpSolve',Prob,...)
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
x_L | Lower bounds on x. | |
x_U | Upper bounds on x. | |
A | The linear constraint matrix. | |
b_L | Lower bounds on linear constraints. | |
b_U | Upper bounds on linear constraints. | |
c_L | Lower bounds on nonlinear constraints. | |
c_U | Upper bounds on nonlinear constraints. | |
x_0 | Starting point. | |
Convex | If Convex==1, assume NLP problems are convex, and only one local NLP solver call is used at each node. If Convex==0 (Default), multiMin is used to do many calls to a local solver to determine the global minima at each node. The global minimum with most components integer valued is chosen. | |
MaxCPU | Maximal CPU Time (in seconds) to be used by minlpSolve, stops with best point found | |
PriLev | Print level in minlpSolve (default 1). Also see optParam.IterPrint | |
PriLevOpt | Print level in sub solvers (SNOPT and other NLP solvers): | |
=0 No output; >0 Convergence results | ||
>1 Output every iteration, >2 Output each step in the NLP alg | ||
For other NLP solvers, see the documentation for the solver | ||
WarmStart | If true, >0, minlpSolve reads the output from the last run from Prob.minlpSolve, if it exists. If it doesn't exist, minlpSolve attempts to open and read warm start data from mat-file minlpSolveSave.mat. minlpSolve uses the warm start information to continue from the last run. The mat-file minlp- SolveSave.mat is saved every Prob.MIP.SaveFreq iteration. | |
SolverNLP | Name of the solver used for NLP subproblems. If empty, the default solver is found calling GetSolver('con',1); If TOMLAB /SOL installed, SNOPT is the default solver. If SolverNLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used: See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters | |
RandState | If Convex == 0, RandState is sent to multiMin to initialize the random gen- erator. RandState is used as follows: | |
If > 0, rand('state',RandState) is set to initialize the pseudo-random generator | ||
if < 0, rand('state',sum(100\*clock)) is set to give a new set of random values each run | ||
if RandState == 0, rand('state',) is not called. Default RandState = -1 | ||
MIP | Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used: | |
IntVars | If empty, all variables are assumed non-integer. If islogical(IntVars) (=all el- ements are 0/1), then 1 = integer variable, 0 = continuous variable. If any element >1, IntVars is the indices for integer variables. | |
VarWeight | Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight might improve convergence. | |
DualGap | minlpSolve stops if the duality gap is less than DualGap. DualGap = 1, stop at first integer solution e.g. DualGap = 0.01, stop if solution < 1% from optimal solution. | |
fIP | An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. Used even if xIP not given. | |
xIP | The x-values giving the fIP value, if a solution (xIP,fIP) is known. | |
NodeSel | Node selection method in branch and bound | |
= 0 Depth First. Priority on nodes with more integer components | ||
= 1 Breadth First. Priority on nodes with more integer components | ||
= 2 Depth First. When integer solution found, use NodeSel = 1 (default) | ||
= 3 Pure LIFO (Last in, first out) Depth First | ||
= 4 Pure FIFO (First in, first out) Breadth First | ||
= 5 Pure LIFO Depth First. When integer solution found, use NodeSel 4 | ||
VarSel | Variable selection method in branch and bound: | |
= 1 Use variable with most fractional value | ||
= 2 Use gradient and distance to nearest integer value | ||
KNAPSACK | If = 1, use a knapsack heuristic. Default 0. | |
ROUNDH | If = 1, use a rounding heuristic. Default 0. | |
SaveFreq | Warm start info saved on minlpSolveSave.mat every SaveFreq iteration (default -1, i.e. no warm start info is saved) | |
optParam | Structure in Prob. Fields used in Prob.optParam, also in sub solvers: | |
MaxIter | Maximal number of iterations, default 10000 | |
IterPrint | Print short information each iteration (PriLev > 0 ==> IterPrint = 1). Iter- ation number: Depth in tree (symbol L\[\] - empty list, symbol Gap - Dual Gap convergence), fNLP (Optimal f(x) current node), fIPMin (Best integer feasi- ble f(x) found), LowBnd (Lower bound on optimal integer feasible f(x)), Dual Gap in absolut value and percent, The length of the node list L, -L-, The Inform and ExitFlag the solver returned at the current node, FuEv (Number of function evaluations used by solver at current node), date/time stamp. | |
bTol | Linear constraint violation convergence tolerance. | |
cTol | Constraint violation convergence tolerance. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
Iter | Number of iterations. | |
ExitFlag | 0: Global optimal solution found, or integer solution with duality gap less than user tolerance. | |
1: Maximal number of iterations reached. | ||
2: Empty feasible set, no integer solution found. | ||
4: No feasible point found running NLP relaxation. | ||
5: Illegal x 0 found in NLP relaxation. | ||
99: Maximal CPU Time used (cputime > Prob.MaxCPU). | ||
Inform | Code telling type of convergence, returned from subsolver. | |
ExitText | Text string giving ExitFlag and Inform information. | |
DualGap | Relative duality gap, max(0,fIPMin-fLB)/-fIPMin-, if fIPMin =0; max(0,fIPMin-fLB) if fIPMin == 0. If fIPMin =0: Scale with 100, 100\*Dual- Gap, to get the percentage duality gap. For absolute value duality gap: scale with fIPMin, fIPMin \* DualGap | |
x_k | Solution. | |
v_k | Lagrange multipliers. Bounds, Linear and Nonlinear Constraints, n + mLin + mNonLin. | |
f_k | Function value at optimum. | |
g_k | Gradient vector at optimum. | |
x_0 | Starting point x 0. | |
f_0 | Function value at start. | |
c_k | Constraint values at optimum. | |
cJac | Constraint derivative values at optimum. | |
xState | State of each variable, described in Table 150. | |
bState | State of each constraint, described in Table 151. | |
cState | State of each general constraint, described in Table 152. | |
Solver | Solver used ('mipSolve'). | |
SolverAlgorithm | Text description of solver algorithm used. | |
Prob | Problem structure used. | |
minlpSolve | A structure with warm start information. Use with WarmDefGLOBAL, see example below. |
Description
To make a restart (warm start), just set the warm start flag, and call minlpSolve once again:
Prob.WarmStart = 1;
Result = tomRun('minlpSolve', Prob, 2);
minlpSolve will read warm start information from the minlpSolveSave.mat file. Another warm start (with same MaxFunc) is made by just calling tomRun again:
Result = tomRun('minlpSolve', Prob, 2);
To make a restart from the warm start information in the Result structure, make a call to WarmDefGLOBAL before calling minlpSolve. WarmDefGLOBAL moves information from the Result structure to the Prob structure and sets the warm start flag, Prob.WarmStart = 1;
Prob = WarmDefGLOBAL('minlpSolve', Prob, Result);
where Result is the result structure returned by the previous run. A warm start (with same MaxIter) is done by just calling tomRun again:
Result = tomRun('minlpSolve', Prob, 2);
To make another warm start with new MaxIter 100, say, redefine MaxIter as:
Prob.optParam.MaxIter = 100;
Then repeat the two lines:
Prob = WarmDefGLOBAL('minlpSolve', Prob, Result);
Result = tomRun('minlpSolve', Prob, 2);