MIPNLP stoaMINLP
This page is part of the MIPNLP Manual. See MIPNLP Manual. |
Purpose
stoaMINLP solves convex mixed-integer nonlinear programming problems (MINLP).
stoaMINLP solves problems of the form
where , , and
. The variables , the
index subset of are restricted to be integers.
Calling Syntax
Recommended is to first set IterPrint, to get information each iteration
Prob.optParam.IterPrint = 1;
Driver call, including printing with level 2:
Result = tomRun('stoaMINLP',Prob,2);
Direct solver call:
Result = stoaMINLP(Prob);
PrintResult(Result);
Result = tomRun('stoaMINLP',Prob,...)
Warm Start
To make a restart (warm start), just set the warm start flag, and call stoaMINLP once again:
Prob.WarmStart = 1;
Result = tomRun('stoaMINLP', Prob, 2);
stoaMINLP will read warm start information from the stoaMINLPSave.mat file. Another warm start (with same MaxFunc) is made by just calling tomRun again:
Result = tomRun('stoaMINLP', Prob, 2);
To make a restart from the warm start information in the Result structure, make a call to WarmDefGLOBAL before calling stoaMINLP. WarmDefGLOBAL moves information from the Result structure to the Prob structure and sets the warm start flag, Prob.WarmStart = 1;
Prob = WarmDefGLOBAL('stoaMINLP', 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('stoaMINLP', 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('stoaMINLP', Prob, Result);
Result = tomRun('stoaMINLP', Prob, 2);
Inputs
Prob structure
The TOMLAB problem structure
The following fields are used in Prob: | |
---|---|
Field | Description |
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 stoaMINLP, stops with best point found |
PriLev | Print level in stoaMINLP (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, stoaMINLP reads the output from the last run from Prob.stoaMINLP, if it exists. If it doesn't exist, stoaMINLP attempts to open and read warm start data from mat-file stoaMINLPSave.mat. stoaMINLP 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 |
SolverNLP0 | Name of the solver used for the initial NLP-problem. If empty, SolverNLP is used. |
SolverLP | Name of the solver used for LP subproblems. If empty, the default solver is found calling GetSolver('lp',1). If TOMLAB /SOL or /SNOPT or /NPSOL installed, MINOS is the default solver. If SolverLP is a SOL solver (MINOS, SNOPT 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 generator. 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 is RandState = -1 |
xInit | Parameter sent to the solver multiMin which is used to solve relaxed sub-problems for nonconvex problems (with Prob.Convex set to false). xInit determines the way initial points are generated and is set as follows:
|
xInit0 | Parameter sent to the solver multiMin when solving the initial relaxed NLP problem at the root node. Default value for xInit0 is min(3000,max(100,N*10)) |
MIP | Structure defining integer optimization parameters. See the table below for a description of each field used in Prob.MIP. |
STOAMINLP | Structure with solver-specific options. See the table below with descriptions of the fields used in Prob.STOAMINLP. |
optParam | Structure with general optimization parameters. See the table below with descriptions of the fields used in Prob.optParam. |
MIP structure
Substructure in Prob with parameters related to mixed integer programming.
fields used in Prob.MIP | |
---|---|
Field | Description |
IntVars | If empty, all variables are assumed non-integer. If islogical(IntVars) (=all elements 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 | stoaMINLP 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: = 1 Depth First. Priority on nodes with more integer components. Default = 2 Breadth First. Priority on nodes with more integer components. = 3 Pure LIFO (Last in, first out) Depth First. = 4 Pure FIFO (First in, first out) Breadth First. = 5 Maximize integer components. = 6 Best bound. = 7 Best estimate using pseudo-costs. = 8 Best projection. |
Backtrack | Node selection method to use after an integer solution has been found. Available choices are the same as for NodeSel. Default is 2, Breadth First. |
VarSel | Variable selection method in branch and bound. = 1 Use variable with most fractional value. = 2 Use gradient and distance to nearest integer value. = 3 Pseudo-cost-based branching. |
KNAPSACK | If = 1, use a knapsack heuristic. Default 0. |
ROUNDH | If = 1, use a rounding heuristic. Default 0. |
SaveFreq | Warm start info saved on stoaMINLPSave.mat every SaveFreq iteration (default -1, i.e. no warm start info is saved) |
STOAMINLP structure
Substructure in Prob with solver-specific options
fields used in Prob.STOAMINLP | |
---|---|
Field | Description |
USECUTS | Flag to use cutting plane algorithm described in StoaMINLP#Algorithm. Using cuts is not recommended for nonconvex problems. Set nonzero to enable, zero to disable. By default, USECUTS = Prob.Convex. |
B_ecp | Parameter regulating likelihood of linearization using extended cutting plane. See StoaMINLP#Algorithm for more information. Default 10. |
K_ecp | Parameter regulating "tailing off" detection for extended cutting plane linearizations. See StoaMINLP#Algorithm for more information. Default 0.001. |
M_ecp | Parameter regulating the balance between branching the search tree and adding linearizations using extended cutting plane. See StoaMINLP#Algorithm for more information. Default 10. |
B_ff | Parameter regulating likelihood of linearization using fixed fractional integer decision variables. See StoaMINLP#Algorithm for more information. Default 10. |
K_ff | Parameter regulating "tailing off" detection for linearizations using fixed fractional integer decision variables. See StoaMINLP#Algorithm for more information. Default 0.001. |
M_ff | Parameter regulating the balance between branching the search tree and adding linearizations using fixed fractional integer decision variables. See StoaMINLP#Algorithm for more information. Default 10. |
B_nlpr | Parameter regulating likelihood of linearization using the solution of the relaxed NLP problem. See StoaMINLP#Algorithm for more information. Default 10. |
K_nlpr | Parameter regulating "tailing off" detection for linearizations using the solution of the relaxed NLP problem. See StoaMINLP#Algorithm for more information. Default 0.001. |
M_nlpr | Parameter regulating the balance between branching the search tree and adding linearizations using the solution of the relaxed NLP problem. See StoaMINLP#Algorithm for more information. Default 10. |
rTYPE | = 0 r is fixed to the value in rVALUE. = 1 r is a uniformly distributed random number in the interval [0,1]. Default. |
rVALUE | Defines the value of r when rTYPE is set to zero. Default is 0.5. |
CUTPOOL | = 0 All linearizations constraints are kept in the master problem. = 1 Manage a pool with inactive linearization constraints. If an inactive constraint gets violated, it is brought back from the pool. Default. |
CUTDELBND | The number of consecutive times a linearization can be inactive before it gets removed and put into the inactive pool. Default 15. |
CUTLIMDEL | = 0 No extra deletion of cuts. Default when Prob.Convex == 1. = 1 Delete any cuts limiting the true feasible region when detected. Such cuts will appear if the problem has nonlinear constraints. Default when Prob.Convex == 0. |
PCITL | Limit on time spent per node calculating initial pseudo costs when VarSel == 3. Default is 120 (s). |
LINPRINT | Set nonzero to print short information about the type of linearization added. Default 0. enabled when IterPrint > 3. |
POOLPRINT | Set nonzero to print information about the cutpool management. Default 0. Enabled when IterPrint > 4. |
optParam structure
Substructure in Prob with general optimization parameters.
fields used in Prob.optParam: | |
---|---|
Field | Description |
MaxIter | Maximal number of iterations, default 10000 |
IterPrint | Print short information each iteration. Setting PriLev > 1 also enables IterPrint, setting it to 1. The information printed for different levels is as follows: >0 A line at each evaluated node with the following: > 1 A line at each evaluated node with the information described above. >2 Depth, number of integer components and lower bound on objective for each node in L. |
bTol | Linear constraint violation convergence tolerance. |
cTol | Constraint violation convergence tolerance. |
fTol | Optimality tolerance. |
Outputs
Result | Structure with result from optimization. The following fields are changed: | |
---|---|---|
Iter | Number of iterations. | |
ExitFlag | Exit flag. 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, size 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 TOMLAB Appendix B. | |
bState | State of each constraint, described in TOMLAB Appendix B. | |
cState | State of each general constraint, described in TOMLAB Appendix B. | |
Solver | Solver used ('stoaMINLP'). | |
SolverAlgorithm | Description of method used. | |
Prob | Problem structure used. | |
stoaMINLP | A structure with warm start information. Use with WarmDefGLOBAL, see example here. |