MinlpSolve: Difference between revisions
m (→Outputs) |
m (→Inputs) |
||
(4 intermediate revisions by the same user not shown) | |||
Line 95: | Line 95: | ||
|||''x_0''||Starting point. | |||''x_0''||Starting point. | ||
|-valign="top" | |-valign="top" | ||
|||''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. | |||''Convex''||If Convex==1, assume NLP problems are convex, and only one local NLP solver call is used at each node. <br>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. | ||
|- | |-valign="top" | ||
|||''MaxCPU''||Maximal CPU Time (in seconds) to be used by minlpSolve, stops with best point found | |||''MaxCPU''||Maximal CPU Time (in seconds) to be used by minlpSolve, stops with best point found | ||
|- | |-valign="top" | ||
|||''PriLev''||Print level in minlpSolve (default 1). Also see optParam.IterPrint | |||''PriLev''||Print level in minlpSolve (default 1). Also see optParam.IterPrint | ||
|-valign="top" | |-valign="top" | ||
|||''PriLevOpt''||Print level in sub solvers (SNOPT and other NLP solvers): | |||''PriLevOpt''||Print level in sub-solvers (SNOPT and other NLP solvers):<br>=0 No output; ''>''0 Convergence results.<br>''>''1 Output every iteration, <br>''>''2 Output each step in the NLP alg<br>For other NLP solvers, see the documentation for the solver | ||
=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 | |||
|-valign="top" | |-valign="top" | ||
|||''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. | |||''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. | ||
|-valign="top" | |-valign="top" | ||
|||''RandState''||If Convex == 0, RandState is sent to multiMin to initialize the random | |||''SolverNLP''||Name of the solver used for NLP subproblems. If empty, the default solver is found calling GetSolver('con',1); <br>If TOMLAB /SOL installed, SNOPT is the default solver.<br>If SolverNLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used:<br>See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters | ||
|-valign="top" | |||
If ''> ''0, rand('state',RandState) is set to initialize the pseudo-random generator | |||''RandState''||If Convex == 0, RandState is sent to multiMin to initialize the random generator. RandState is used as follows: <br>If ''> ''0, rand('state',RandState) is set to initialize the pseudo-random generator.<br> If ''< ''0, rand('state',sum(100*clock)) is set to give a new set of random values each run. <br>If RandState == 0, rand('state',) is not called. <br>Default is RandState = -1 | ||
|-valign="top" | |||
|- | |||
|||''MIP''||Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used: | |||''MIP''||Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used: | ||
|-valign="top" | |-valign="top" | ||
|||''IntVars''||If empty, all variables are assumed non-integer. If islogical(IntVars) (=all | |||''MIP.IntVars''||If empty, all variables are assumed non-integer. <br>If islogical(IntVars) (=all elements are 0/1), then 1 = integer variable, 0 = continuous variable. <br>If any element ''>''1, IntVars is the indices for integer variables. | ||
|-valign="top" | |||
|||''MIP.VarWeight''||Weight for each variable in the variable selection phase. <br> A lower value gives higher priority. Setting Prob.MIP.VarWeight might improve convergence. | |||
|-valign="top" | |||
|||''MIP.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. | |||
|-valign="top" | |||
|||''MIP.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. | |||
|-valign="top" | |||
|||''MIP.xIP''||The x-values giving the fIP value, if a solution (xIP,fIP) is known. | |||
|-valign="top" | |-valign="top" | ||
|||'' | |||''MIP.NodeSel''||Node selection method in branch and bound. <br>= 0 Depth First. Priority on nodes with more integer components. <br>= 1 Breadth First. Priority on nodes with more integer components. <br>= 2 Depth First. When integer solution found, use NodeSel = 1 (default). <br>= 3 Pure LIFO (Last in, first out) Depth First. <br>= 4 Pure FIFO (First in, first out) Breadth First. <br>= 5 Pure LIFO Depth First. When integer solution found, use NodeSel 4 | ||
|-valign="top" | |-valign="top" | ||
|||'' | |||''MIP.VarSel''||Variable selection method in branch and bound: <br>= 1 Use variable with most fractional value <br>= 2 Use gradient and distance to nearest integer value | ||
|-valign="top" | |-valign="top" | ||
|||'' | |||''MIP.KNAPSACK''||If = 1, use a knapsack heuristic. Default 0. | ||
|- | |-valign="top" | ||
|||'' | |||''MIP.ROUNDH''||If = 1, use a rounding heuristic. Default 0. | ||
|-valign="top" | |||
|||''MIP.SaveFreq''||Warm start info saved on minlpSolveSave.mat every SaveFreq iteration (default -1, i.e. no warm start info is saved) | |||
|-valign="top" | |||
|||''optParam''||Structure in Prob. Fields used in Prob.optParam, also in sub-solvers: | |||
|-valign="top" | |-valign="top" | ||
|||'' | |||''optParam.MaxIter''||Maximal number of iterations, default 10000 | ||
|-valign="top" | |-valign="top" | ||
|||'' | |||''optParam.IterPrint''||Print short information each iteration (PriLev ''> ''0 ==''> ''IterPrint = 1). <br>Print one line each iteration with: | ||
Iteration number:<br> | |||
Depth in tree (symbol L[] - empty list, symbol Gap - Dual Gap convergence), <br>fNLP (Optimal f(x) current node), <br>fIPMin (Best integer feasible f(x) found), <br>LowBnd (Lower bound on optimal integer feasible f(x)), <br>Dual Gap in absolut value and percent, <br>The length of the node list L, -L-, <br>The Inform and ExitFlag the solver returned at the current node, <br>FuEv (Number of function evaluations used by solver at current node), <br>date/time stamp. | |||
|-valign="top" | |-valign="top" | ||
|||'' | |||''optParam.bTol''||Linear constraint violation convergence tolerance. | ||
|-valign="top" | |-valign="top" | ||
|||'' | |||''optParam.cTol''||Constraint violation convergence tolerance. | ||
|} | |} | ||
Line 177: | Line 152: | ||
|||''Iter ''||Number of iterations. | |||''Iter ''||Number of iterations. | ||
|-valign="top" | |-valign="top" | ||
|||''ExitFlag ''||0: Global optimal solution found, or integer solution with duality gap less than user tolerance. | |||''ExitFlag ''||Exit flag. <br>0: Global optimal solution found, or integer solution with duality gap less than user tolerance. <br>1: Maximal number of iterations reached. <br>2: Empty feasible set, no integer solution found. <br>4: No feasible point found running NLP relaxation.<br>5: Illegal x_0 found in NLP relaxation. <br>99: Maximal CPU Time used (cputime ''> ''Prob.MaxCPU). | ||
1: Maximal number of iterations reached. | |||
2: Empty feasible set, no integer solution found. | |||
4: No feasible point found running NLP relaxation. | |||
5: Illegal | |||
99: Maximal CPU Time used (cputime ''> ''Prob.MaxCPU). | |||
|- | |- | ||
|||''Inform''||Code telling type of convergence, returned from subsolver. | |||''Inform''||Code telling type of convergence, returned from subsolver. | ||
|- | |- | ||
|||''ExitText''||Text string giving ExitFlag and Inform information. | |||''ExitText''||Text string giving ''ExitFlag'' and ''Inform'' information. | ||
|-valign="top" | |-valign="top" | ||
|||''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 | |||''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. | |||''x_k''||Solution. | ||
|- | |-valign="top" | ||
|||''v_k''||Lagrange multipliers. Bounds, Linear and Nonlinear Constraints, n + mLin + mNonLin. | |||''v_k''||Lagrange multipliers. Bounds, Linear and Nonlinear Constraints, size n + mLin + mNonLin. | ||
|- | |- | ||
|||''f_k''||Function value at optimum. | |||''f_k''||Function value at optimum. | ||
Line 217: | Line 182: | ||
|||''cState''||State of each general constraint, described in [[TOMLAB_Appendix_B#Table:_The_state_variable_cState_for_each_nonlinear_constraint.|TOMLAB Appendix B]]. | |||''cState''||State of each general constraint, described in [[TOMLAB_Appendix_B#Table:_The_state_variable_cState_for_each_nonlinear_constraint.|TOMLAB Appendix B]]. | ||
|- | |- | ||
|||''Solver''||Solver used (' | |||''Solver''||Solver used ('minlpSolve'). | ||
|- | |- | ||
|||''SolverAlgorithm''||Text description of solver algorithm used. | |||''SolverAlgorithm''||Text description of solver algorithm used. |
Latest revision as of 11:24, 19 August 2013
Purpose
Solve mixed-integer nonlinear programming problems (MINLP).
minlpSolve 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('minlpSolve',Prob,2);
Direct solver call:
Result = minlpSolve(Prob);
PrintResult(Result);
Result = tomRun('minlpSolve',Prob,...)
Warm Start
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);
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 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 | |
MIP | Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used: | |
MIP.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. | |
MIP.VarWeight | Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight might improve convergence. | |
MIP.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. | |
MIP.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. | |
MIP.xIP | The x-values giving the fIP value, if a solution (xIP,fIP) is known. | |
MIP.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 | |
MIP.VarSel | Variable selection method in branch and bound: = 1 Use variable with most fractional value = 2 Use gradient and distance to nearest integer value | |
MIP.KNAPSACK | If = 1, use a knapsack heuristic. Default 0. | |
MIP.ROUNDH | If = 1, use a rounding heuristic. Default 0. | |
MIP.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: | |
optParam.MaxIter | Maximal number of iterations, default 10000 | |
optParam.IterPrint | Print short information each iteration (PriLev > 0 ==> IterPrint = 1). Print one line each iteration with: Iteration number: | |
optParam.bTol | Linear constraint violation convergence tolerance. | |
optParam.cTol | Constraint violation convergence 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 ('minlpSolve'). | |
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
minlpSolve implements a 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 above) determines if to assume the NLP subproblems are convex or not.
minlpSolve depends on a suitable NLP solver.