MIPNLP stoaMINLP

From TomWiki
Revision as of 05:41, 14 July 2014 by Bjorn (talk | contribs) (Created page with "{{Part Of Manual|title=the MIPNLP Manual|link=MIPNLP Manual}} ==Purpose== stoaMINLP solves convex mixed-integer nonlinear programming problems (MINLP). ''stoaMINLP '...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Notice.png

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

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 \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} \\& & & {x_{j} \in \mathbb{N} \ \ \forall j \in I} \\ \end{array} }


where 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 x,x_{L},x_{U}\in \mathbb{R}^{n}} , 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 c(x),c_{L},c_{U}\in \mathbb{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 \mathbb{R}^{m_{2}\times n}} and 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 b_{L},b_{U}\in \mathbb{R}^{m_{2}}} . The variables 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 x \in I} , the index subset of 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 1,...,n} 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
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.
SolverNLP0 Name of the solver used for the initial NLP-problem. If empty, SolverNLP is used.
SolverUC Solver used for the unconstrained feasibility problem, NLPF. NLPF is solved in case the NLP problem is infeasible.
If empty, the default solver is found calling GetSolver('uc',LargeScale,0).
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 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:
Iteration number:
Depth in tree (symbol L[] - empty list, symbol Gap - Dual Gap convergence),
fNLP (Optimal f(x) current node),
fIPMin (Best integer feasible 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.
Outer approximation linearizations, number of cuts in active/inactive pool (|C| #A #I).

> 1 A line at each evaluated node with the information described above.
Moreover, with IterPrint enabled a notice is printed whenever the algorithm switches node selection methods.
Setting a higher value of IterPrint gives more detailed information.

>2 Depth, number of integer components and lower bound on objective for each node in L.
>3 Sets LINPRINT = 1, print info about linearizations added (if used).
>4 Sets POOLPRINT = 1, print info about cut-pool management (if used).

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.
Retrieved from "http://tomwiki.com/index.php?title=MIPNLP_stoaMINLP&oldid=3049"