TOMLAB Solver Reference: Difference between revisions

From TomWiki
Jump to navigationJump to search
No edit summary
No edit summary
 
(66 intermediate revisions by the same user not shown)
Line 1: Line 1:
==TOMLAB Solver Reference==
{{Part Of Manual|title=the TOMLAB Manual|link=[[TOMLAB|TOMLAB Manual]]}}
 
[[Category:Manuals]]
Detailed descriptions of the TOMLAB  solvers, driver routines and some utilities are given in the following sections. Also see the M-file help for each solver. All solvers except for the TOMLAB  Base Module are described in separate manuals.
Detailed descriptions of the TOMLAB  solvers, driver routines and some utilities are given in the following sections. Also see the M-file help for each solver. All solvers except for the TOMLAB  Base Module are described in separate manuals.
===TOMLAB Base Module===


For a description of solvers called using the MEX-file  interface, see the M-file help, e.g. for the MINOS solver ''minosTL.m''. For more details, see the User's Guide for the particular solver.
For a description of solvers called using the MEX-file  interface, see the M-file help, e.g. for the MINOS solver ''minosTL.m''. For more details, see the User's Guide for the particular solver.


====clsSolve====
==clsSolve==
 
'''Purpose'''


Solves dense and sparse nonlinear least squares optimization problems with  linear inequality and equality con- straints and simple bounds on the variables.
Solves dense and sparse nonlinear least squares optimization problems with  linear inequality and equality con- straints and simple bounds on the variables.


''clsSolve ''solves problems of the form
*[[clsSolve]]


 
==conSolve==
<math>
\begin{array}{cccccc}
\min\limits_{x} & f(x) & = & \frac{1}{2}r(x)^{T}r(x) &  &  \\
s/t & x_{L} & \leq  & x  & \leq  & x_{U} \\& b_{L} & \leq  & Ax & \leq  & b_{U} \\
\end{array}
</math>
 
where <math>$x,x_{L},x_{U}\in \MATHSET{R} ^{n}$</math>, <math>$r(x)\in \MATHSET{R} ^{N}$</math>, <math>$A\in \MATHSET{R}^{m_{1}\times n}$</math> and <math>$b_{L},b_{U}\in \MATHSET{R}^{m_{1}}$</math>.
 
 
'''Calling  Syntax'''
 
Result = clsSolve(Prob, varargin)
 
Result = tomRun('clsSolve', Prob);
 
'''Description  of Inputs'''
 
{|
|''Prob''|| colspan="2" | Problem description structure. The following fields are used:
|-
|||''Solver.Alg''||Solver algorithm to be run:
|-
|||||0: Gives default, the Fletcher - Xu hybrid method;
|-
|||||1: Fletcher - Xu hybrid method; Gauss-Newton/BFGS.
|-
|||||2: Al-Baali - Fletcher hybrid method; Gauss-Newton/BFGS.
|-
|||||3: Huschens method. SIAM J. Optimization.  Vol 4, No 1, pp 108-129 jan 1994.
|-
|||||4: The Gauss-Newton method.
|-
|||||5: Wang, Li, Qi Structured MBFGS method.
|-
|||||6: Li-Fukushima MBFGS method.
|-
|||||7: Broydens method.
|-
|||||Recommendations: Alg=5  is theoretically best, and seems best in practice as well. Alg=1  and Alg=2  behave very similar, and are robust methods. Alg=4 may be good for ill-conditioned problems. Alg=3  and Alg=6  may sometimes fail. Alg=7 tries to minimize Jacobian evaluations, but might need more resid- ual evaluations. Also fails more often that  other algorithms.  Suitable when analytic Jacobian is missing and evaluations of the Jacobian is costly.  The problem should not be too ill-conditioned.
|-
|
|-
|||''Solver.Method''||Method to solve linear system:
|-
|||||0: QR with pivoting (both sparse and dense).
|-
|||||1: SVD (dense).
|-
|||||2: The inversion routine (inv) in Matlab (Uses QR).
|-
|||||3: Explicit  computation of pseudoinverse, using pinv(''Jk '').
|-
|||||Search method technique (if Prob.LargeScale = 1, then Method = 0 always): Prob.Solver.Method = 0 Sparse iterative QR using Tlsqr.
|-
|||''LargeScale''||If = 1, then sparse iterative QR using Tlsqr is used to find search directions
|-
|||''x_0''||Starting point.
|-
|||''x_L''||Lower bounds on the variables.
|-
|||''x U''||Upper bounds on the variables.
|-
|||''b_L''||Lower bounds on the linear constraints. ''b
|-
|||''b_U''||Upper bounds on the linear constraints. ''A'' Constraint matrix for linear constraints.
|-
|||''c_L''||Lower bounds on the nonlinear constraints.
|-
|||''c_U''||Upper bounds on the nonlinear constraints.
|-
|||''f_Low''||A lower bound on the optimal function value, see LineParam.fLowBnd below.
|-valign="top"
||||''SolverQP''||Name of the solver used for QP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m.
|-
|||''PriLevOpt''||Print Level.
|- valign="top"
||||''optParam''||Structure with special fields for optimization parameters, see Table 141. Fields used are:  ''bTol'', ''eps absf'', ''eps g'', ''eps Rank'', ''eps x'', ''IterPrint'', ''MaxIter'', ''PreSolve'', ''size f'', ''size x'', ''xTol'', ''wait'', and
''QN InitMatrix ''(Initial  Quasi-Newton matrix,  if not empty, otherwise  use identity matrix).
|-
|||''LineParam''||Structure with line search parameters. Special fields used:
|-
|||''LineAlg''||If ''Alg'' = 7
|-
|||||0 = Fletcher quadratic interpolation line search
|-
|||||3 = Fletcher cubic interpolation line search
|-
|||||otherwise Armijo-Goldstein line search (LineAlg == 2)
|-
|||||If ''Alg''! = 7
|-
|||||0 = Fletcher quadratic interpolation line search
|-
|||||1 = Fletcher cubic interpolation line search
|-
|||||2 = Armijo-Goldstein line search
|-
|||||otherwise Fletcher quadratic interpolation line search (LineAlg == 0)
|-
|||||If  Fletcher, see  help LineSearch for the LineParam parameters used.  Most important  is the accuracy in the line search: sigma - Line search accuracy tolerance, default 0.9.
|-
||| colspan="2" | If LineAlg == 2, then the following parameters are used
|-
|||''agFac''||Armijo Goldsten reduction factor, default 0.1
|-
|||''sigma''||Line search accuracy tolerance, default 0.9
|- valign="top"
|||''fLowBnd''||A  lower bound on the  global optimum  of  f(x). NLLS  problems always have  f(x)  values ''>''= 0 The user might  also give  lower bound estimate in Prob.f Low clsSolve computes LineParam.fLowBnd as: LineParam.fLowBnd = max(0,Prob.f Low,Prob.LineParam.fLowBnd) fLow = LineParam.fLowBnd is used in convergence tests.
|-
|''varargin''|| colspan="2" | Other parameters directly sent to low level routines.
|}
 
'''Description  of Outputs'''
{|
|''Result''|| colspan="2" | Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Optimal point.
|-
|||''v_k''||Lagrange multipliers (not used).
|-
|||''f_k''||Function value at optimum.
|-
|||''g_k''||Gradient value at optimum.
|-
|||''x_0''||Starting point.
|-
|||''f_0''||Function value at start.
|-
|||''r_k''||Residual at optimum.
|-
|||''J_k''||Jacobian matrix at optimum.
|-
|||''xState''||State of each variable, described in Table 150.
|-
|||''bState''||State of each linear constraint, described in Table 151.
|-
|||''Iter''||Number of iterations.
|-
|||''ExitFlag''||Flag giving exit status. 0 if convergence, otherwise error. See ''Inform''.
|-
|||''Inform''||Binary code telling type of convergence:
|-
|||||1: Iteration points are close.
|-
|||||2: Projected gradient small.
|-
|||||3: Iteration points are close and projected gradient small.
|-
|||||4: Function value close to 0.
|-
|||||5: Iteration points are close and function value close to 0.
|-
|||||6: Projected gradient small and function value close to 0.
|-
|||||7: Iteration points are close, projected gradient small and function value close to 0.
|-
|||||8: Relative function value reduction low for ''LowI ts ''= 10 iterations.
|-
|||||11: Relative f(x) reduction low for LowIts iter. Close Iters.
|-
|||||16: Small Relative f(x) reduction.
|-
|||||17: Close iteration points, Small relative f(x) reduction.
|-
|||||18: Small gradient, Small relative f(x) reduction.
|-
|||||32: Local minimum with all variables on bounds.
|-
|||||99: The residual is independent of x. The Jacobian is 0.
|-
|||||101: Maximum number of iterations reached.
|-
|||||102: Function value below given estimate.
|-
|||||104: ''x_k '' not feasible, constraint violated.
|-
|||||105: The residual is empty, no NLLS problem.
|-
|||''Solver''||Solver used.
|-
|||''SolverAlgorithm''||Solver algorithm used.
|-
|||''Prob''||Problem structure used.
|}
 
'''Description'''
 
The solver ''clsSolve'' includes seven optimization methods for nonlinear least squares problems: the Gauss-Newton method, the Al-Baali-Fletcher \[3\] and the Fletcher-Xu \[19\] hybrid method, the Huschens TSSM method \[50\] and three more. If rank problem occur, the solver is using subspace minimization.  The line search is performed using the routine ''LineSearch ''which is a modified version of an algorithm by Fletcher \[20\]. Bound constraints are partly treated as described in Gill,  Murray  and Wright \[28\].  ''clsSolve ''treats linear equality and inequality constraints using an active set strategy and a null space method.
 
'''M-files Used'''
 
''ResultDef.m'', ''preSolve.m'', ''qpSolve.m'', ''tomSolve.m'', ''LineSearch.m'',  ''ProbCheck.m'', ''secUpdat.m'', ''iniSolve.m'',  ''endSolve.m''
 
'''See Also'''
 
''conSolve'', ''nlpSolve'', ''sTrustr''
 
'''Limitations'''
 
When using the ''LargeScale ''option, the number of residuals may not be less than 10 since the sqr2 algorithm may run into problems if used on problems that are not really large-scale.
 
'''Warnings'''
 
Since no second order derivative information is used, ''clsSolve ''may not be able to determine the type of stationary point converged to.
 
====conSolve====
 
'''Purpose'''


Solve general constrained nonlinear optimization problems.
Solve general constrained nonlinear optimization problems.


''conSolve ''solves problems of the form
*[[conSolve]]
 
 
<math>
\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} \\
\end{array}
</math>
 
where <math>x,x_{L}</math>, <math>x_{U}\in \MATHSET{R}^{n}</math>,
<math>c(x)</math>, <math>c_{L}</math>, <math>c_{U}\in \MATHSET{R}^{m_{1}}</math>,
<math>A \in \MATHSET{R}^{m_{2}\times n}</math> and <math>b_{L},b_{U}\in \MATHSET{R}^{m_{2}}</math>.
 


'''Calling  Syntax'''
==cutPlane==
 
Result = conSolve(Prob, varargin)
 
Result = tomRun('conSolve', Prob);
 
'''Description  of Inputs'''
 
{|
 
|''Prob''|| colspan="2" | Problem description structure. The following fields are used:
|-
|||''Solver.Alg''||Choice of algorithm. Also affects how derivatives are obtained.
|-
|||||See following fields and the table on page 92.
|-
|||||0,1,2: Schittkowski SQP.
|-
|||||3,4: Han-Powell SQP.
|-
|||''x_0''||Starting point.
|-
|||''x_L''||Lower bounds on the variables.
|-
|||''x_U''||Upper bounds on the variables.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''c_L''||Lower bounds on the general constraints.
|-
|||''c_U''||Upper bounds on the general constraints.
|-
|||''NumDiff''||How to obtain derivatives (gradient, Hessian).
|-
|||''ConsDiff''||How to obtain the constraint derivative matrix.
|-
|||''SolverQP''||Name of the solver used for QP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m.
|-
|||''f_Low''||A lower bound on the optimal function value, see LineParam.fLowBnd below.
|-
||||||Used in convergence tests, f k(x k) ''<''= f Low.  Only a feasible point  x k is accepted.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|-
|||''FUNCS.g''||Name of m-file computing the gradient vector ''g''(''x'').
|-
|||''FUNCS.H''||Name of m-file computing the Hessian matrix ''H ''(''x'').
|-
|||''FUNCS.c''||Name of m-file computing the vector of constraint functions ''c''(''x'').
|-
|||''FUNCS.dc''||Name of m-file computing the matrix of constraint normals ''?c''(''x'')''/dx''.
|-
|||''PriLevOpt''||Print level.
|- valign="top"
||||''optParam''||Structure with optimization parameters, see Table 141. Fields that are used: ''bTol'', ''cTol'', ''eps absf'', ''eps g'', ''eps x'', ''eps Rank'', ''IterPrint'', ''MaxIter'', ''QN InitMatrix'', ''size f'', ''size x'', ''xTol ''and ''wait''.
|-
|||''LineParam''||Structure with line search parameters. See Table 140.
|-
|||''fLowBnd''||A lower bound on the global optimum  of f(x). The user might also give lower bound estimate in Prob.f Low conSolve computes LineParam.fLowBnd as: LineParam.fLowBnd = max(Prob.f Low,Prob.LineParam.fLowBnd).
|-
|''varargin''|| colspan="2" | Other parameters directly sent to low level routines.
|}
 
'''Description of Outputs'''
{|
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed:
|-
|||''x_k''||Optimal point.
|-
|||''v_k''||Lagrange multipliers.
|-
|||''f_k''||Function value at optimum.
|-
|||''g_k''||Gradient value at optimum.
|-
|||''H_k''||Hessian value at optimum.
|-
|||''x_0''||Starting point.
|-
|||''f_0''||Function value at start.
|-
|||''c_k''||Value of constraints at optimum.
|-
|||''cJac''||Constraint Jacobian at optimum.
|-
|||''xState''||State of each variable, described in Table 150 .
|-
|||''bState''||State of each linear constraint, described in Table 151.
|-
|||''cState''||State of each nonlinear constraint.
|-
|||''Iter''||Number of iterations.
|-
|||''ExitFlag''||Flag giving exit status.
|-
|||''ExitText'||'Text string giving ''ExitFlag ''and ''Inform ''information.
|-
|||''Inform''||Code telling type of convergence:
|-
|||||1: Iteration points are close. ''Result'' Structure with result from optimization. The following fields are changed:, continued
|-
|||||2: Small search direction.
|-
|||||3: Iteration points are close and Small search direction.
|-
|||||4: Gradient of merit function small.
|-
|||||5: Iteration points are close and gradient of merit function small.
|-
|||||6: Small search direction and gradient of merit function small.
|-
|||||7: Iteration points are close, small search direction and gradient of merit func-tion small.
|-
|||||8: Small search direction ''p ''and constraints satisfied.
|-
|||||101: Maximum number of iterations reached.
|-
|||||102: Function value below given estimate.
|-
|||||103: Iteration points are close, but constraints not fulfilled.  Too large penalty weights to be able to continue. Problem is maybe infeasible.
|-
|||||104: Search direction is zero and infeasible constraints. The problem is very likely infeasible.
|-
|||||105: Merit function is infinity.
|-
|||||106: Penalty weights too high.
|-
|||''Solver''||Solver used.
|-
|||''SolverAlgorithm''||Solver algorithm used.
|-
|||''Prob''||Problem structure used.
|}
'''Description'''
 
The routine ''conSolve ''implements two SQP algorithms for general constrained minimization problems. One imple- mentation, ''Solver.Alg ''= 0'', ''1'', ''2, is based on the SQP algorithm by Schittkowski with Augmented Lagrangian merit function described in \[69\]. The other, ''Solver.Alg ''= 3'', ''4, is an implementation of the Han-Powell SQP method.
 
The Hessian in the QP subproblems are determined in one of several ways, dependent on the input parameters. The following table shows how the algorithm and Hessian method is selected.
 
{|
|'''Solver.Alg'''||'''NumDiff'''||'''AutoDiff'''||'''isempty(FUNCS.H)'''||'''Hessian computation'''||'''Algorithm'''
|-
|0||0||0||0||Analytic Hessian||Schittkowski SQP
|-
|0||any||any||any||BFGS||Schittkowski SQP
|-
|1||0||0||0||Analytic Hessian||Schittkowski SQP
|-
|1||0||0||1||Numerical differences H||Schittkowski SQP
|-
|1||''> ''0||0||any||Numerical differences g,H||Schittkowski SQP
|-
|1||''< ''0||0||any||Numerical differences H||Schittkowski SQP
|-
|1||any||1||any||Automatic differentiation||Schittkowski SQP
|-
|2||0||0||any||BFGS||Schittkowski SQP
|-
|2||= 0||0||any||BFGS, numerical gradient g||Schittkowski SQP
|-
|2||any||1||any||BFGS, automatic diff gradient||Schittkowski SQP
|-
|3||0||0||0||Analytic Hessian||Han-Powell SQP
|-
|3||0||0||1||Numerical differences H||Han-Powell SQP
|-
|3||''> ''0||0||any||Numerical differences g,H||Han-Powell SQP
|-
|3||''< ''0||0||any||Numerical differences H||Han-Powell SQP
|-
|3||any||1||any||Automatic differentiation||Han-Powell SQP
|-
|4||0||0||any||BFGS||Han-Powell SQP
|-
|4||= 0||0||any||BFGS, numerical gradient g||Han-Powell SQP
|-
|4||any||1||any||BFGS, automatic diff gradient||Han-Powell SQP
|}
'''M-files  Used'''
 
''ResultDef.m'', ''tomSolve.m'', ''LineSearch.m'', ''iniSolve.m'', ''endSolve.m'', ''ProbCheck.m''.
 
'''See Also'''
 
''nlpSolve'', ''sTrustr''
 
====cutPlane====
 
'''Purpose'''


Solve mixed integer linear programming problems (MIP).
Solve mixed integer linear programming problems (MIP).


''cutplane ''solves problems of the form
*[[cutPlane]]
 
 
<math>
\begin{array}{ccccccl}
\min\limits_{x}  & f(x) & = & c^{T}x &    & \\\mbox{subject to} & 0    & \leq  & x  & \leq  & x_{U} & \\&      &      & Ax &    =  & b, & ~x_{j} \in \MATHSET{N}\, \forall j \in $I$  \\
\end{array}
</math>
 
 
where <math>$c, x, x_U \in \MATHSET{R}^{n}$</math>, <math>$A\in \MATHSET{R}^{m\times
n}$</math> and <math>$b \in \MATHSET{R}^{m}$</math>. The variables <math>$x \in I$</math>, the index
subset of <math>$1,...,n$</math> are restricted to be integers.
 
 
'''Calling  Syntax'''


Result = cutplane(Prob); or
==DualSolve==
 
Result = tomRun('cutplane', Prob);
 
'''Description  of Inputs'''
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''c''||Constant vector.
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''x_L''||Lower bounds on the variables (assumed to be 0).
|-
|||''x_U''||Upper bounds on the variables.
|-
|||''x_0''||Starting point.
|-
|||''QP.B''||Active set ''B_0 ''at start:
|-
|||||''B''(''i'') = 1: Include variable ''x''(''i'') in basic set.
|-
|||||''B''(''i'') = 0: Variable ''x''(''i'') is set on it's lower bound.
|-
|||||''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on it's upper bound.
|-
|||||''B ''empty: ''lpSimplex  ''solves Phase I LP to find a feasible point.
|-
|||''Solver.Method''||Variable selection rule to be used:
|-
|||||0: Minimum reduced cost. (default)
|-
|||||1: Bland's anti-cycling rule.
|-
|||||2: Minimum reduced cost, Dantzig's rule.
|-
|||''MIP.IntVars''||Which of the ''n ''variables are integers.
|-
|||''SolverLP''||Name of the solver used for initial  LP subproblem.
|-
|||''SolverDLP''||Name of the solver used for dual LP subproblems.
|-
|||''optParam''||Structure with special fields for optimization parameters,  see Table 141.
|-
|||||Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps f'', ''eps Rank'', ''xTol ''and ''bTol''.
|}
 
'''Description  of Outputs'''
{|
|''Result''||colspan="2"|Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Optimal point.
|-
|||''f_k''||Function value at optimum.
|-
|||''g_k ''||Gradient value at optimum, ''c''.
|-
|||''v_k''||Lagrange multipliers.
|-
|||''QP.B ''||Optimal active set. See input variable ''QP.B''.
|-
|||''xState''||State of each variable, described in Table 150 .
|-
|||''x_0''||Starting point.
|-
|||''f_0''||Function value at start.
|-
|||''Iter ''||Number of iterations.
|-
|||''FuncEv''||Number of function evaluations. Equal to ''Iter''.
|-
|||''ConstrEv''||Number of constraint evaluations.  Equal to ''Iter''.
|-
|||''ExitFlag''||0: OK.
|-
|||||1: Maximal number of iterations reached.
|-
|||||4: No feasible point ''x 0 ''found.
|-
|||''Inform''||If ''ExitFlag > ''0, ''Inform ''= ''ExitFlag''.
|-
|||''Solver''||Solver used.
|-
|||''SolverAlgorithm''||Solver algorithm used.
|-
|||''Prob''||Problem structure used.
|}
 
'''Description'''
 
The routine ''cutplane ''is an implementation of a cutting plane algorithm with Gomorov cuts.  ''cutplane ''normally uses the linear programming routines ''lpSimplex ''and ''DualSolve ''to solve relaxed subproblems. By changing the setting of the structure fields ''Prob.Solver.SolverLP ''and ''Prob.Solver.SolverDLP'', different sub-solvers are possible to use.
 
''cutplane ''can interpret ''Prob.MIP.IntVars ''in two different ways:
 
*Vector of length less than dimension of problem:  the elements designate indices of integer variables, e.g. <math>$IntVars = [1\; 3\; 5]$ </math> restricts <math>$x_1,x_3$</math> and <math>$x_5$</math> to take integer values only.
 
*Vector of same length as <math>$c$</math>: non-zero values indicate integer variables, e.g. with five variables (<math>$x\in \MATHSET{R}^5$</math> ), <math>$IntVars=[ 1\; 1\; 0\; 1\; 1 ]$</math> demands all but <math>$x_3$</math> to take integer values.
 
'''M-files Used'''
 
''lpSimplex.m, DualSolve.m''
 
'''See Also'''
 
''mipSolve, balas, lpsimpl,  lpsimp2, lpdual, tomSolve.''
 
====DualSolve====
 
'''Purpose'''


Solve linear programming problems when a dual feasible solution is available.
Solve linear programming problems when a dual feasible solution is available.


''DualSolve ''solves problems of the form
*[[dualSolve]]


 
==expSolve==
<math>
\begin{array}{cccccl}
\min\limits_{x} & f(x) & = & c^{T}x &  &  \\s/t & x_{L} & \leq  & x  & \leq  & x_{U} \\&      &      & Ax  &    =  & b_{U} \\
\end{array}
</math>
 
 
where <math>$x,x_{L},x_{U}\in \MATHSET{R} ^{n}$</math> , <math>$c \in \MATHSET{R}^{n}$</math> , <math>
$A\in \MATHSET{R}^{m\times n}$</math> and <math>$b_{U} \in \MATHSET{R}^{m}$</math>.
 
 
Finite upper bounds on ''x ''are added as extra inequality constraints. Finite nonzero lower bounds on ''x ''are added as extra inequality constraints. Fixed variables are treated explicitly.  Adding slack variables and making necessary sign changes gives the problem in the standard form
 
 
<math>
\begin{array}{ccccl}
\min\limits_{x} & f_{P}(x) & = & c^{T}x &  \\s/t & {\hat A}x  &  =    &  b  &    \\&  x        & \geq  &  0  &
\end{array}
</math>
 
 
and the following dual problem is solved,
 
 
<math>
\begin{array}{ccccl}
\max\limits_{y} & f_{D}(y)  &  =    &  b^{T}y  \\s/t            & {\hat A}^{T}y    &  \leq  &    c      \\ &    y    &  urs  &
\end{array}
</math>
 
 
with <math>$x,c \in \MATHSET{R}^{n}$</math> , <math>
$A\in \MATHSET{R}^{\hat{m}\times n}$</math> and <math>$b,y \in
\MATHSET{R}^{m}$</math>.
 
 
'''Calling  Syntax'''
 
[Result] = DualSolve(Prob)
 
'''Description  of Inputs'''
{|
|''Prob''||colspan="2"|Problem description structure.  The following fields are used:
|-
|||''QP.c''||Constant vector.
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''x_L''||Lower bounds on the variables.
|-
|||''x_U''||Upper bounds on the variables.
|-
|||''x_0''||Starting point, must be dual feasible.
|-
|||''y_0''||Dual parameters (Lagrangian multipliers) at ''x ''_0.
|-
|||''QP.B''||Active set ''B_0 ''at start:
|-
|||||''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set.
|-
|||||''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound.
|-
|||||''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound.
|-
|||''Solver.Alg''||Variable selection rule to be used:
|-
|||||0: Minimum reduced cost (default).
|-
|||||1: Bland's anti-cycling rule.
|-
|||||2: Minimum reduced cost. Dantzig's rule.
|-
|||''PriLevOpt''||Print Level.
|-
|||''optParam''||Structure with special fields for optimization parameters,  see Table 141.
|-
|||||Fields used are: ''MaxIter'', ''wait'', ''eps f'', ''eps Rank ''and ''xTol''.
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Optimal primal solution ''x''.
|-
|||''f_k''||Function value at optimum.
|-
|||''v_k''||Optimal dual parameters. Lagrange multipliers for linear constraints.
|-
|||''x_0''||Starting point.
|-
|||''Iter''||Number of iterations.
|-
|||''QP.B''||Optimal active set.
|-
|||''ExitFlag''||Exit flag:
|-
|||||0: Optimal solution found.
|-
|||||1: Maximal number of iterations reached. No primal feasible solution found.
|-
|||||2: Infeasible Dual problem.
|-
|||||4: Illegal step length due to numerical difficulties. Should not occur.
|-
|||||6: No dual feasible starting point found.
|-
|||||7: Illegal step length due to numerical difficulties.
|-
|||||8: Convergence  because ''fk >''= ''QP.DualLimit''.
|-
|||||9: <math>$x_L(i) > x_U(i) + xTol$</math> for some i. No solution exists.
|-
|''Solver''||Solver used.
|-
|''SolverAlgorithm''||Solver algorithm used.
|-
|||''c''||Constant vector in standard form formulation.
|-
|||''A''||Constraint matrix for linear constraints in standard form.
|-
|||''b''||Right hand side in standard form.
|}
 
'''Description'''
 
When a dual feasible solution is available, the dual simplex method is possible to use. ''DualSolve ''implements this method using the algorithm in \[35, pages 105-106\].  There are three rules available for variable selection. Bland's cycling prevention rule is the choice if fear of cycling exist. The other two are variants of minimum reduced cost variable selection, the original Dantzig's rule and one which sorts the variables in increasing order in each step (the default choice).
 
'''M-files  Used'''
 
''cpTransf.m''
 
'''See Also'''
 
''lpSimplex''
 
====expSolve====
 
'''Purpose'''


Solve exponential fitting  problems for given number of terms p.
Solve exponential fitting  problems for given number of terms p.


'''Calling  Syntax'''
*[[expSolve]]
 
Prob = expAssign( ... );
 
Result = expSolve(Prob, PriLev); or
 
Result = tomRun('expSolve', PriLev);
 
'''Description  of Inputs'''
 
{|
|''Prob''||Problem created with expAssign.
|-
|''PriLev''||Print level in tomRun call.
|-
''Prob.SolverL2''||Name of solver to use. If empty, TOMLAB  selects dependent on license.
|}
 
'''Description  of Outputs'''
 
{|
|Result TOMLAB||Result structure as returned by solver selected by input argument ''Solver''.
|-
|''LS''||Statistical information about the solution. See Table 153, page 239.
|}
 
'''Global  Parameters  Used'''
 
'''Description'''
 
''expSolve ''solves a '''cls '''(constrained least squares) problem for exponential fitting  formulates by expAssign.  The problem is solved with a suitable or given '''cls '''solver.
 
The aim is to provide a quicker interface to exponential fitting,  automating the process of setting up the problem structure and getting statistical data.
 
'''M-files  Used'''
 
''GetSolver'', ''expInit'', ''StatLS ''and ''expAssign''


'''Examples'''
==glbDirect==
 
Assume that the Matlab vectors ''t'', ''y ''contain the following data:
 
<math>
\begin{array}{|r|rrrrrrrrr|}
t_i &      0 &  1.00  &  2.00 &  4.00 &  6.00 &  8.00 & 10.00 & 15.00 & 20.00\\y_i & 905.10 & 620.36  & 270.17 & 154.68 & 106.74 & 80.92 & 69.98 & 62.50 & 56.29\\
\end{array}
</math>
 
To set up and solve the problem of fitting  the data to a two-term exponential model
 
 
<math>f(t) = \alpha_1 e^{-\beta_1 t} + \alpha_2 e^{-\beta_2 t}</math> ,
 
 
give the following commands:
 
<pre>
>> p      = 2;                        % Two terms
>> Name  = 'Simple two-term exp fit'; % Problem name, can be anything
>> wType  = 0;                        % No weighting
>> SepAlg = 0;                        % Separable problem
>> Prob = expAssign(p,Name,t,y,wType,[],SepAlg);
 
>> Result = tomRun('expSolve',Prob,1);
>> x = Result.x_k'
 
x =
          0.01          0.58        72.38        851.68
</pre>
 
The <math>$x$</math> vector contains the parameters  as <math>$x=[\beta_1,\beta_2,\alpha_1,\alpha_2]$</math> so the solution may be visualized  with
 
<pre>
>> plot(t,y,'-*', t,x(3)*exp(-t*x(1)) + x(4)*exp(-t*x(2)) );
</pre>
 
Figure 6: Results of fitting  experimental data to two-term exponential model.  Solid line: final model, dash-dot: data.
 
====glbDirect====
 
'''Purpose'''


Solve box-bounded global optimization problems.
Solve box-bounded global optimization problems.


''glbDirect  ''solves problems of the form
*[[glbDirect]]
 
 
<math>
\begin{array}{cccccc}
\min\limits_{x} & f(x) &  &  &  &  \\
s/t & x_{L} & \leq  & x & \leq  & x_{U} \\
\end{array}
</math>
 
 
where <math>$f \in \MATHSET{R}$</math> and <math>$x,x_{L},x_{U}\in \MATHSET{R} ^{n}$</math>.
 
''glbDirect ''is a Fortran MEX implementation of ''glbSolve''.
 
'''Calling  Syntax'''
 
Result = glbDirectTL(Prob,varargin)
 
Result = tomRun('glbDirect',  Prob);
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''x_L''||Lower bounds for ''x'', must be given to restrict the search space.
|-
|||''x_U''||Upper bounds for ''x'', must be given to restrict the search space.
|-
|||''Name''||Name of the problem. Used for security if doing warm start.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|- valign="top"
|||''PriLevOpt''||Print Level. 0 = Silent. 1 = Errors. 2 = Termination message and warm start info. 3 = Option summary.
|- valign="top"
|||''WarmStart''||If true, ''>'' 0, ''glbDirect'' reads the output from  the  last run from ''Prob.glbDirect.WarmStartInto'' if it exists. If it doesn't exist, ''glbDirect ''attempts to open and read warm start data from mat-file glbDirectSave.mat. ''glbDirect ''uses this warm start information to continue from the last run.
|-
|||''optParam''||Structure in Prob, Prob.optParam.  Defines optimization parameters. Fields used:
|- valign="top"
|||''IterPrint''||Print iteration log every IterPrint iteration. Set to 0 for no iteration log. PriLev must be set to at least 1 to have iteration log to be printed.
|-
|||''MaxIter''||Maximal number of iterations, default 200.
|-
|||''MaxFunc''||Maximal number of function evaluations, default 10000 (roughly).
|-
|||''EpsGlob''||Global/local weight parameter, default 1E-4.
|-
|||''fGoal''||Goal for function value, if empty not used.
|- valign="top"
|||''eps f''||''Relative accuracy for function value, ''f T ol ''== ''epsf ''.  Stop if ''abs''(''f - f Goal'')''<''= ''abs''(''f Goal'') ''* f T ol '', if ''f Goal  ''= 0. Stop if ''abs''(''f - f Goal'')''<''= ''f T ol '', if''f Goal ''== 0.
|- valign="top"
|||''eps x''||Convergence tolerance in x. All possible rectangles are less than this tolerance(scaled to (0,1) ). See the output field maxTri.
|-
|||''glbDirect''||Structure in Prob, Prob.glbDirect.  Solver specific.
|- valign="top"
''options''||Structure with options. These options have precedence over all other options in the Prob struct. Available options are:
|-
|||||PRILEV:  Equivalent to Prob.PrilevOpt.  Default: 0
|-
|||||MAXFUNC:  Eq. to Prob.optParam.MaxFunc. Default: 10000
|-
MAXITER: Eq. to Prob.optParam.MaxIter.  Default: 200
|- valign="top"
|||||PARALLEL: Set to 1 in order to have glbDirect to call Prob.FUNCS.f with a matrix x of points to let the user function compute function values in parallel. Default: 0
|-
|||||WARMSTART: Eq. to Prob.WarmStart.  Default: 0
|-
|||||ITERPRINT: Eq. to Prob.optParam.IterPrint.  Default: 0
|-
|||||FUNTOL:  Eq. to Prob.optParam.eps f. Default: 1e-2
|-
|||||VARTOL:  Eq. to Prob.optParam.eps x. Default: 1e-13
|-
|||||GLWEIGHT: Eq. to Prob.optParam.EpsGlob. Default: 1e-4
|-
|||||Structure with WarmStartInfo.  Use WarmDefDIRECT.m  to define it.
|-
||||''WarmStartInfo''
|}


'''Description  of Outputs'''
==glbSolve==
 
{|
|''Result''|| colspan="2" | Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Matrix  with optimal points as columns.
|-
|||''f_k''||Function value at optimum.
|-
|||''Iter''||Number of iterations.
|-
|||''FuncEv''||Number function evaluations.
|-
|||''ExitText''||Text string giving ExitFlag and Inform information.
|-
|||''ExitFlag''||Exit code.
|-
|||||0 = Normal termination, max number of iterations /func.evals reached.
|-
|||||1 = Some bound, lower or upper is missing.
|-
|||||2 = Some bound is inf, must be finite.
|-
|||||4 = Numerical trouble determining optimal rectangle, empty set and cannot continue.
|-
|||''Inform''||Inform code.
|-
|||||1 = Function value f is less than fGoal.
|-
|||||2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. ''abs''(''f - f Goal'')''/abs''(''f Goal'') ''<''= ''f T ol''.
|-
|||||3 = Maximum number of iterations done.
|-
|||||4 = Maximum number of function evaluations done.
|-
|||||91= Numerical trouble, did not find element in list.
|-
|||||92= Numerical trouble, No rectangle to work on.
|-
|||||99= Other error, see ExitFlag.
|-
|||''glbDirect''||Substructure for glbDirect specific result data.
|- valign="top"
|||''nextIterFunc''||If optimization algorithm was stopped because of maximum number of function evaluations reached, this is the number of function evaluations required to complete the next iteration.
|-
|||''maxTri''||Maximum size of any triangles. Structure containing warm start data. Could be used to continue optimization
|-
|||''WarmStartInfo''||where glbDirect stopped.
|-
|||colspan="2"|To make a warm start possible, glbDirect saves the following information in the structure Result.glbDirect.WarmStartInfo and file glbDirectSave.mat (for internal solver use only):
|-
|||''points''||Matrix  with all rectangle centerpoints, in [0,1]-space.
|-
|||''dRect ''||Vector with distances from centerpoint to the vertices.
|-
|||''fPoints''||Vector with function values.
|-
|||''nIter''||Number of iterations.
|-
|||''lRect''||Matrix  with all rectangle side lengths in each dimension.
|-
|||''Name''||Name of the problem. Used for security if doing warm start.
|-
|||''dMin''||Row vector of minimum function value for each distance.
|-
|||''ds''||Row vector of all different distances, sorted.
|-
|||''glbfMin''||Best function value found at a feasible point.
|-valign="top"
|||''iMin''||The index in D which has lowest function value, i.e. the rectangle which mini- mizes (''F -glbf M in''+''E'')''./D ''where ''E ''= ''max''(''EpsGlob*abs''(''glbf M in'')'', ''1''E -''8).
|-
|||''ign''||Rectangles to be ignored in the rect. selection procedure.
|}
 
'''Description'''
 
The global optimization routine ''glbDirect ''is an implementation of the DIRECT algorithm presented in \[14\]. The algorithm in ''glbDirect ''is a Fortran MEX implementation of the algorithm in ''glbSolve''.  DIRECT is a modification of the standard Lipschitzian  approach that  eliminates  the need to specify a Lipschitz constant. Since no such constant  is used, there is no natural  way of defining convergence  (except when the optimal function value is known).  Therefore ''glbDirect ''runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to '''restart  '''''glbDirect ''with the final status of all parameters from the previous run, a so called ''warm start''. Assume that a run has been made with ''glbDirect ''on a certain problem for 50 iterations.  Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of ''glbDirect ''a flag ''Prob.WarmStart ''should be set to one and ''WarmDefDIRECT ''run. Then ''glbDirect ''is using output previously obtained to make the restart. The m-file ''glbSolve ''also includes the subfunction ''conhull ''(in MEX)  which is an implementation of the algorithm GRAHAMHULL in \[65, page 108\] with the modifications proposed on page 109. ''conhull ''is used to identify all points lying on the convex hull defined by a set of points in the plane.
 
'''M-files  Used'''
 
''iniSolve.m'', ''endSolve.m glbSolve.m''.
 
====glbSolve====
 
'''Purpose'''


Solve box-bounded global optimization problems.
Solve box-bounded global optimization problems.
''glbSolve ''solves problems  of the form


<math>
*[[glbSolve]]
\begin{array}{cccccc}
\min\limits_{x} & f(x) &  &  &  &  \\
s/t & x_{L} & \leq  & x & \leq  & x_{U} \\
\end{array}
</math>


 
==glcCluster==
where <math>$f \in \MATHSET{R}$</math> and <math>$x,x_{L},x_{U}\in \MATHSET{R} ^{n}$</math>.
 
 
'''Calling  Syntax'''
 
Result = glbSolve(Prob,varargin)
 
Result = tomRun('glbSolve', Prob);
 
 
'''Description  of Inputs'''
{|
|''Prob''|| colspan="2" | Problem description structure. The following fields are used:
|-
|||''x_L''||Lower bounds for ''x'', must be given to restrict the search space.
|-
|||''x_U''||Upper bounds for ''x'', must be given to restrict the search space.
|-
|||''Name''||Name of the problem. Used for security if doing warm start.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|-
|||''PriLevOpt''||Print Level. 0 = silent. 1 = some printing.  2 = print each iteration.
|-
|||''WarmStart''||If true, ''> ''0, glbSolve reads the output  from the  last run from the mat-file glbSave.mat, and continues from the last run.
|-
|||''MaxCPU''||Maximal CPU Time (in seconds) to be used.
|-
|||''optParam''||Structure in Prob, Prob.optParam.  Defines optimization parameters. Fields used:
|-
|||''IterPrint''||Print iteration \#, \# of evaluated points and best f(x) each iteration.
|-
|||''MaxIter ''||Maximal number of iterations, default ''max''(5000'', n * ''1000).
|-
|||''MaxFunc''||Maximal number of function evaluations, default ''max''(10000'', n * ''2000).
|-
|||''EpsGlob''||Global/local weight parameter, default 1E-4.
|-
|||''fGoal''||Goal for function value, if empty not used.
|- valign="top"
|||''eps_f''||Relative accuracy for function value, ''f T ol ''== ''epsf ''.  Stop if ''abs''(''f - f Goal'')''<''= ''abs''(''f Goal'') ''* f T ol '', if ''f Goal  ''= 0. Stop if ''abs''(''f - f Goal'') ''<''= ''f T ol '', if ''f Goal ''== 0.
|-
||| colspan="2" | If warm start is chosen, the following fields saved to ''glbSave.mat ''are also used and contains information from the previous run:
|-
|||''C''||Matrix  with all rectangle centerpoints, in [0,1]-space.
|-
|||''D''||Vector with distances from centerpoint to the vertices. ''DMin'' Row vector of minimum function value for each distance. ''DSort ''Row vector of all different distances, sorted.
|-
|||''E''||Computed tolerance in rectangle selection.
|-
|||''F''||Vector with function values.
|-
|||''L''||Matrix  with all rectangle side lengths in each dimension. ''Name ''Name of the problem. Used for security if doing warm start. ''glbfMin ''Best function value found at a feasible point.
|- valign="top"
|||''iMin''||The index in D which has lowest function value, i.e. the rectangle which mini- mizes (''F -glbf M in''+''E'')''./D ''where ''E ''= ''max''(''EpsGlob*abs''(''glbf M in'')'', ''1''E -''8).
|-
|||''varargin''||Other parameters directly sent to low level routines.
|}
 
'''Description  of Outputs'''
{|
|''Result''|| colspan="2" | Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Matrix  with all points giving the function value ''f k''.
|-
|||''f_k''||Function value at optimum.
|-
|||''Iter''||Number of iterations.
|-
|||''FuncEv''||Number function evaluations.
|-
|||''maxTri''||Maximum size of any triangle.
|-
|||''ExitText''||Text string giving ExitFlag and Inform information.
|-
|||''ExitFlag''||Exit code.
|-
|||||0 = Normal termination, max number of iterations /func.evals reached.
|-
|||||1 = Some bound, lower or upper is missing.
|-
|||||2 = Some bound is inf, must be finite.
|-
|||||4 = Numerical trouble determining optimal rectangle, empty set and cannot continue.
|-
|||''Inform''||Inform code.
|-
|||||0 = Normal Exit.
|-
|||||1 = Function value f is less than fGoal.
|-
|||||2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. ''abs''(''f - f Goal'')''/abs''(''f Goal'') ''<''= ''f T ol''.
|-
|||||9 = Max CPU Time reached.
|-
|||''Solver''||Solver used, 'glbSolve'.
|}
 
'''Description'''
 
The global optimization routine ''glbSolve ''is an implementation of the DIRECT algorithm presented in \[14\]. DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore ''glbSolve ''runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to '''restart '''''glbSolve ''with the final status of all parameters from the previous run, a so called ''warm start ''Assume that a run has been made with ''glbSolve ''on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of ''glbSolve ''a flag ''Prob.WarmStart ''should be set to one. Then ''glbSolve ''is using output previously written  to the file ''glbSave.mat ''to make the restart.  The m-file ''glbSolve ''also includes the subfunction ''conhull ''(in MEX)  which is an implementation of the algorithm GRAHAMHULL in \[65, page 108\] with the modifications proposed on page 109. ''conhull ''is used to identify all points lying on the convex hull defined by a set of points in the plane.
 
'''M-files  Used'''
 
''iniSolve.m'', ''endSolve.m''
 
====glcCluster====
 
'''Purpose'''


Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.
Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.


''glcCluster ''solves problems of the form
*[[glcCluster]]


 
==glcDirect==
<math>
\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}{c}{x_i \in \MATHSET{N} \; \forall i \in I} \\
\end{array}
</math>
 
 
where <math>$x,x_{L},x_{U}\in \MATHSET{R}^{n}$</math>,
<math>$c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}$</math>,
<math>$A\in \MATHSET{R}^{m_{2}\times n}$</math> and <math>$b_{L},b_{U}\in \MATHSET{R}^{m_{2}}$</math>.
 
'''Calling  Syntax'''
 
Result = glcCluster(Prob, maxFunc1, maxFunc2, maxFunc3, ProbL)
 
Result = tomRun('glcCluster', Prob, PriLev) (driver call)
 
 
'''Description  of Inputs'''
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''c_L''||Lower bounds on the general constraints.
|-
|||''c_U''||Upper bounds on the general constraints.
|-
|||''x_L''||Lower bounds for ''x'', must be given to restrict the search space.
|-
|||''x_U''||Upper bounds for ''x'', must be given to restrict the search space.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|-
|||''FUNCS.c''||Name of m-file computing the vector of constraint functions ''c''(''x'').
|-valign="top"
|||''PriLevOpt''||Print level. 0=Silent. 1=Some output from each glcCluster phase. 2=More output  from each phase. 3=Further  minor output  from each phase. 6=Use PrintResult(  ,1) to print summary from each global and local run.  7 = Use PrintResult(  ,2) to print summary from each global and local run.  8 = Use PrintResult( ,3) to print summary from each global and local run.
|-valign="top"
|||''WarmStart''||If true, ''> ''0, glcCluster warm starts the DIRECT  solver. The DIRECT  solver will utilize all points sampled in last run, from one or two calls, dependent on the success in last run. Note: The DIRECT solver may not be changed if doing WarmStart mat-file glcFastSave.mat, and continues from the last run.
|-
|||''Name''||Name of the problem. ''glcCluster  ''uses the warmstart capability in ''glcFast ''and needs the name for security reasons.
|-
|||''GO''||Structure in ''Prob'', ''Prob.GO''. Fields used:
|-valign="top"
|||''maxFunc1''||Number of function evaluations in 1st call to glcFast. Should be odd number (automatically corrected). Default 100 ''* dim''(''x'') + 1.
|-
|||''maxFunc2''||Number of function evaluations in 2nd call to glcFast.
|-valign="top"
|||''maxFunc3''||If glcFast is not feasible after maxFunc1 function evaluations, it will be repeat- edly called (warm start) doing maxFunc1 function evaluations until maxFunc3 function evaluations reached.
|-valign="top"
|||''ProbL''||Structure to be used in the local search. By default the same problem structure as in the global search is used, Prob (see below). Using a second structure is important if optimal continuous variables may take values on bounds. glcFast used for the global search only converges to the simple bounds in the limit, and therefore the simple bounds may be relaxed a bit  in the global search. Also, if the  global search has difficulty  fulfilling  equality constraints exactly, the lower and upper bounds may be slightly relaxed. But being exact in the local search. Note that the local search is using derivatives, and can utilize given analytic derivatives.  Otherwise the local solver is using numerical derivatives or automatic differentiation.  If  routines to provide derivatives  are given in ProbL, they are used. If only one structure Prob is given, glcCluster uses the derivative routines given in the this structure.
|-
|||''localSolver''||Optionally change local solver used ('snopt' or 'npsol' etc.).
|-
|||''DIRECT''||DIRECT  subsolver, either glcSolve or glcFast (default).
|-
|||''localTry''||Maximal number  of local searches from cluster points. If ''<''= 0, glcCluster stops after clustering. Default 100.
|-
|||''maxDistmin''||The minimal number used for clustering, default 0.05.
|-valign="top"
|||''optParam''||Structure with special fields for optimization parameters, see Table 141. Fields used are: ''PriLev'', ''cTol'', ''IterPrint'', ''MaxIter'', ''MaxFunc'', ''EpsGlob'', ''fGoal'', ''eps f'', ''eps x''.
|-valign="top"
|||''MIP.IntVars''||Structure in Prob, Prob.MIP. If empty, all variables are assumed non-integer (LP problem).  If ''length''(''I ntV ars'') ''> ''1 ==''> length''(''I ntV ars'') == ''length''(''c'') should hold.  Then ''I ntV ars''(''i'')  == 1 ==''> x''(''i'')  integer.  ''I ntV ars''(''i'')  == 0 ==''> x''(''i'')  real.  If  ''length''(''I ntV ars'')  ''< n'', IntVars  is assumed to be a set of indices.  It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
|-
|''varargin''||colspan="2"|Other parameters directly sent to low level routines.
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Matrix  with all points giving the function value ''f_k''.
|-
|||''f_k''||Function value at optimum.
|-
|||''c_k''||Nonlinear constraints values at ''x_k''.
|-
|||''Iter''||Number of iterations.
|-
|||''FuncEv''||Number function evaluations.
|-
|||''maxTri''||Maximum size of any triangle.
|-
|||''ExitText''||Text string giving ExitFlag and Inform information.
|-
|||''Cluster''||Subfield with clustering information
|-
|||''x_k''||Matrix  with best cluster points.
|-
|||''f_k''||Row vector with f(x) values for each column in Cluster.x_k.
|-
|||''maxDist''||maxDist used for clustering.
|-
|||''minDist''||vector of all minimal distances between points.
|}
 
'''Description'''
 
The routine ''glcCluster ''implements an extended version of DIRECT,  see \[52\], that  handles problems with  both nonlinear and integer constraints.
 
DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore ''glcCluster ''is run for a predefined number of function evaluations and considers the best function value found as the optimal one. It is possible for the user to '''restart  '''''glcCluster ''with the final status of all parameters from the previous run, a so called ''warm start ''Assume that a run has been made with ''glcCluster ''on a certain problem for 500 function evaluations. Then a run of e.g. 200 function evaluations more should give the same result as if the run had been using 700 function evaluations in the first place. To do a warm start of ''glcCluster ''a flag ''Prob.WarmStart ''should be set to one. Then ''glcCluster ''is using output previously written to the file ''glcSave.mat ''to make the restart.
 
DIRECT does not explicitly handle equality constraints. It works best when the integer variables describe an ordered quantity and is less effective  when they are categorical.
 
'''M-files  Used'''
 
''iniSolve.m'', ''endSolve.m'', ''glcFast.m''
 
====glcDirect====
 
'''Purpose'''


Solve global mixed-integer nonlinear programming problems.
Solve global mixed-integer nonlinear programming problems.


''glcDirect ''solves problems of the form
*[[glcDirect]]
 
 
<math>
\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_i \mathrm{\ \ integer} &  & i \in I \\
\end{array}
</math>
 
 
where <math>$x,x_{L},x_{U}\in \MATHSET{R}^{n}$</math>,
<math>$c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}$</math>,
<math>$A\in \MATHSET{R}^{m_{2}\times n}$</math> and <math>$b_{L},b_{U}\in \MATHSET{R}^{m_{2}}$</math>.
The variables <math>$x \in I$, the index subset of $1,...,n$</math> are restricted to be integers. Recommendation: Put the integers as the first variables. Put low range integers before large range integers. Linear constraints are specially treated. Equality constraints are added as penalties to the objective. Weights are computed automatically, assuming f(x) scaled to be roughly 1 at optimum. Otherwise scale f(x).
 
''glcDirect'' is a Fortran MEX implementation of ''glcSolve''.


'''Calling  Syntax'''
==glcSolve==
 
Result = glcDirectTL(Prob,varargin)
 
Result = tomRun('glcDirect', Prob);
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''Name''||Problem name. Used for safety when doing warm starts.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|-
|||''FUNCS.c''||Name of m-file computing the vector of constraint functions ''c''(''x'').
|-
|||''A''||Linear constraints matrix.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''c_L''||Lower bounds on the general constraints.
|-
|||''c U''||Upper bounds on the general constraints.
|-
|||''x_L''||Lower bounds for ''x'', must be finite to restrict the search space.
|-
|||''x_U''||Upper bounds for ''x'', must be finite to restrict the search space.
|-valign="top"
|||''PriLevOpt''||Print Level. This controls both regular printing from glcDirect and the amount of iteration log information to print.
|-
|||||0 = Silent. 
|-valign="top"
|||||1 = Warnings and errors printed. Iteration log on iterations im- proving function value.
|-
|||||2 = Iteration log on all iterations.
|-
|||||3 = Log for each function evaluation.
|-
|||||4 = Print list of parameter settings.
|-valign="top"
|||||See optParam.IterPrint for more information on iteration log printing.
|-valign="top"
|||''WarmStart''||If true, ''>'' 0, glcDirect reads the output from the last run from Prob.glcDirect.WarmStartInfo if it exists. If it doesn't exist, glcDirect attempts to open and read warm start data from mat-file glcDirectSave.mat. glcDirect uses this warm start information to continue from the last run.
|-
|||''MaxCPU''||Maximum CPU Time (in seconds) to be used.
|-
|||''MIP''||Structure in ''Prob'', ''Prob.MIP''.
|-valign="top"
|||''Intvars''||If empty, all variables are assumed non-integer (LP problem) If length(IntVars) ''> ''1 ==''> ''length(IntVars)  == length(c) should hold Then IntVars(i)  == 1 ==''> ''x(i)  integer.  IntVars(i)  == 0 ==''> ''x(i)  real If  length(IntVars)  ''< ''n, IntVars is assumed to be a set of indices. It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
|-
|||''fIP''||An upper bound on the optimal f(x) value. If empty, set as Inf.
|-
|||''xIP''||The x-values  giving the fIP  value.  If fIP  empty and xIP  given, fIP  will  be computed if xIP nonempty, its feasibility is checked
|-
|||''glcDirect''||Structure with DIRECT algorithm specific parameters. Fields used:
|-valign="top"
|||''fcALL''||=0 (Default). If linear constraints cannot be feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point.
|-valign="top"
|||||=1 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Do not update rates of change for the constraints.
|-valign="top"
|||||=2 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Update rates of change constraints.
|-valign="top"
|||''useRoC''||=1 (Default).  Use original Rate of Change (RoC) for constraints to weight the constraint violations in selecting which rectangle divide.
|-valign="top"
|||||=0 Avoid RoC, giving equal weights to all constraint violations. Suggested if difficulty  to find feasible points.  For problems where linear constraints have been added among the nonlinear (NOT  RECOMMENDED;  AVOID!!!),  then option useRoc=0  has been successful, whereas useRoC completely fails.
|-valign="top"
|||||=2  Avoid  RoC for linear constraints, giving weight  one to these constraint violations, whereas the nonlinear constraints use RoC.
|-valign="top"
|||||=3 Use RoC for nonlinear constraints, but linear constraints are not used to determine which rectangle to use.
|-valign="top"
|||''BRANCH''||=0 Divide rectangle by selecting the longest side, if ties use the lowest index. This is the Jones DIRECT  paper strategy.
|-valign="top"
|||||=1  First  branch the integer variables, selecting the variable with  the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0.  DEFAULT! Normally much more efficient than =0 for mixed- integer problems.
|-valign="top"
|||||=2 First branch the integer variables with 1,2 or 3 possible values, e.g \[0,1\],\[0,2\] variables, selecting the variable with least splits. Then branch the other integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables  as in BRANCH=0.
|-valign="top"
|||||=3 Like =2, but  use priorities  on the variables, similar  to  ''mipSolve'', see Prob.MIP.VarWeight.
|-valign="top"
|||''RECTIE''||When minimizing the measure to find which new rectangle to try to get feasible, there are often ties, several rectangles have the same minimum. RECTIE = 0 or 1 seems reasonable choices. Rectangles  with low index are often larger then the rectangles with higher index.  Selecting one of each type could help, but often =0 is fastest.
|-
|||||=0 Use the rectangle with value a, with lowest index (original).
|-
|||||=1 (Default): Use 1 of the smallest and 1 of largest rectangles.
|-
|||||=2 Use the last rectangle with the same value a, not the 1st.
|-
|||||=3 Use one of the smallest rectangles with same value a.
|-
|||||=4 Use all rectangles with the same value a, not just the 1st.
|-valign="top"
|||''EqConFac''||Weight factor for equality constraints when adding to objective function f(x) (Default value 10). The weight is computed as EqConFac/"right or left hand side constant value", e.g. if the constraint is Ax ''<''= b, the weight is EqCon- Fac/b If DIRECT  just is pushing down the f(x) value instead of fulfilling  the equality constraints, increase EqConFac.
|-valign="top"
|||''AxFeas''||Set nonzero to make glcDirect skip f(x) evaluations, when the linear constraints are infeasible, and still no feasible point has been found. The default is 0. Value
|-valign="top"
1 demands''||f cALL ''== 0. This option could save some time if f(x) is a bit costly, however overall performance could on some problems  be dramatically worse.
|-valign="top"
|||''fEqual''||All  points with  function values within  tolerance fEqual are considered to be global minima and returned. Default 1E-10.
|-valign="top"
|||''LinWeight''||''RateOf C hange''= ''LinW eight * \|\|a''(''i, '':)''\|\| ''for linear constraints.  Balance be- tween linear and nonlinear constraints. Default 0.1. The higher value, the less influence from linear constraints.
|-
|||''alpha''||Exponential forgetting factor in RoC computation, default 0.9.
|-valign="top"
|||''AvIter''||How many values to use in startup of RoC computation before switching to exponential smoothing with forgetting factor alpha. Default 50.
|-valign="top"
|||''optParam''||Structure with special fields for optimization parameters, see Table 141 on page 229.
|-valign="top"
|||||Fields used by ''glcDirect ''are: ''IterPrint'', ''bTol'', ''cTol'', ''MaxIter'', ''MaxFunc'', ''EpsGlob'', ''fGoal'', ''eps f'', ''eps x''.
|-
|||''varargin''||Other parameters directly sent to low level routines.
|}
 
'''Description of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Matrix  with all points giving the function value ''f k''.
|-
|||''f_k''||Function value at optimum.
|-
|||''c_k''||Nonlinear constraints values at ''x k''.
|-
|||''Iter''||Number of iterations.
|-
|||''FuncEv''||Number function evaluations.
|-
|||''maxTri''||Maximum size of any triangle.
|-
|||''ExitText''||Text string giving ExitFlag and Inform information.
|-valign="top"
|||''ExitFlag''||0 = Normal termination, max number of iterations func.evals reached.
|-
|||||2 = Some upper bounds below lower bounds.
|-
|||||4 = Numerical trouble, and cannot continue.
|-
|||||7 = Reached maxFunc or maxIter, NOT feasible.
|-
|||||8 = Empty domain for integer variables.
|-
|||||10= Input errors.
|-
|||''Inform''||1 = Function value f is less than fGoal.
|-valign="top"
|||||2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f-fGoal)/abs(fGoal) ''<''= fTol.
|-
|||||3 = Maximum number of iterations done.
|-
|||||4 = Maximum number of function evaluations done.
|-valign="top"
|||||5 = Maximum number of function evaluations would most likely be too many in the next iteration, save warm start info, stop.
|-valign="top"
|||||6 = Maximum number of function evaluations would most likely be too many in the next iteration, because 2 ''* sLen >''= maxFDim - nFunc, save warm start info, stop.
|-
|||||7 = Space is dense.
|-
|||||8 = Either space is dense, or MIP is dense.
|-
|||||10= No progress in this run, return solution from previous one.
|-
|||||91= Infeasible.
|-
|||||92= No rectangles to work on.
|-
|||||93= sLen = 0, no feasible integer solution exists.
|-
|||||94= All variables are fixed.
|-
|||||95= There exist free constraints.
|-
|||''glcDirect''||Substructure for glcDirect specific result data.
|-
|||''convFlag''||Converge status flag from solver.
|-valign="top"
|||||Structure with warm start information. Use WarmDefDIRECT to reuse this
|-
|||''WarmStartInfo''||information in another run.
|-valign="top"
|||''glcDirectSave.mat''||To make a warm start possible, glcDirect saves the following information in the structure Result.glcDirect.WarmStartInfo  and file glcDirectSave.mat (for internal solver use only):
|-
|||''C''||Matrix  with all rectangle centerpoints, in \[0,1\]-space.
|-
|||''D''||Vector with distances from centerpoint to the vertices.
|-
|||''F''||Vector with function values.
|-
|||''G''||Matrix  with constraint values for each point.
|-
|||''Iter''||Number of iterations.
|-
|||''Name''||Name of the problem. Used for security if doing warm start.
|-valign="top"
|||''Split''||''Split''(''i, j'') is the number of splits along dimension ''i ''of rectangle ''j''.
|-
|||''Tr''||''T r''(''i'') is the number of times rectangle ''i ''has been trisected.
|-
|||''fMinIdx''||Indices of the currently best points.
|-
|||''fMinEQ''||sum(abs(infeasibilities)) for minimum points, 0 if no equalities.
|-
|||''glcfMin''||Best function value found at a feasible point.
|-
|||''feasible''||Flag indicating if a feasible point has been found.
|-
|||''ignoreidx ''||Rectangles to be ignored in the rectangle selection procedure.
|-
|||''roc''||Rate of change s, for each constraint.
|-
|||''s0''||Sum of observed rate of change s0 in the objective.
|-
|||''t''||''t''(''i'') is the total number of splits along dimension ''i''.
|}
 
'''Description'''
 
The routine ''glcDirect  ''implements an extended version  of DIRECT,  see  \[52\], that  handles problems with  both nonlinear and integer constraints. The algorithm in ''glcDirect ''is a Fortran MEX implementation of the algorithm in ''glcSolve''.
 
DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore ''glcDirect ''is run for a predefined number of function evaluations and considers the best function value found as the optimal one. It is possible for the user to '''restart  '''''glcDirect ''with the final status of all parameters from the previous run, a so called ''warm start''.  Assume that a run has been made with ''glcDirect ''on a certain problem for 500 function evaluations. Then a run of e.g. 200 function evaluations more should give the same result as if the run had been using 700 function evaluations in the first place. To do a warm start of ''glcDirect ''a flag ''Prob.WarmStart ''should be set to one. Then ''glcDirect ''will use output previously written to the file ''glcDirectSave.mat ''(or the warm start structure) to make the restart.
 
DIRECT does not explicitly  handle equality constraints.  It works best when the integer variables describe an ordered quantity and is less effective  when they are categorical.
 
'''M-files  Used'''
 
''iniSolve.m'', ''endSolve.m ''and ''glcSolve.m''.
 
'''Warnings'''
 
A significant portion of ''glcDirect ''is coded in Fortran MEX format. If the solver is aborted, it may have allocated memory for the computations which is not returned. This may lead to unpredictable behavior if ''glcDirect ''is started again. To reduce the risk of trouble, do "clear mex" if a run has been aborted.
 
====glcSolve====
 
'''Purpose'''


Solve general constrained mixed-integer global optimization problems.
Solve general constrained mixed-integer global optimization problems.


''glcSolve ''solves problems of the form
*[[glcSolve]]
 
 
<math>
\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_i \mathrm{\ \ integer} &  & i \in I \\\end{array}
</math>
 
 
where <math>$x,x_{L},x_{U}\in \MATHSET{R}^{n}$</math> , <math>$c(x),c_{L},c_{U}\in\MATHSET{R}^{m_{1}}$</math> , <math>$A\in \MATHSET{R}^{m_{2}\times n}$</math> and <math>$b_{L},b_{U}\in \MATHSET{R}^{m_{2}}$</math>.
 
The variables <math>$x \in I$</math>, the index subset of <math>$1,...,n$</math> are restricted to be integers. Recommendation: Put the integers as the first variables. Put low range integers before large range integers. Linear constraints are specially treated. Equality constraints are added as penalties to the objective. Weights are computed automatically, assuming f(x) scaled to be roughly 1 at optimum. Otherwise scale f(x).
 
'''Calling  Syntax'''
 
Result = glcSolve(Prob,varargin)
 
Result = tomRun('glcSolve', Prob);


'''Description  of Inputs'''
==infLinSolve==
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''A''||Constraint matrix for linear constraints.
|-
||||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''c_L''||Lower bounds on the general constraints.
|-
|||''c_U''||Upper bounds on the general constraints.
|-
|||''MIP''||Structure in ''Prob'', ''Prob.MIP''.
|-valign="top"
|||''Intvars''||If empty, all variables are assumed non-integer (LP problem) If length(IntVars)''> ''1 ==''> ''length(IntVars)  == length(c) should hold Then IntVars(i)  == 1 ==''> ''x(i)  integer.  IntVars(i)  == 0 ==''> ''x(i)  real If  length(IntVars)  ''< ''n, IntVars is assumed to be a set of indices. It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
|-
|||''fIP''||An upper bound on the optimal f(x) value. If empty, set as Inf.
|-valign="top"
|||''xIP''||The x-values  giving the fIP  value.  If fIP  empty and xIP  given, fIP  will  be computed if xIP nonempty, its feasibility is checked
|-valign="top"
|||''x_L''||Lower bounds for ''x'', must be given to restrict the search space. Any lower bounds that are inf are changed to -10000.
|-valign="top"
|||''x_U''||Upper bounds for ''x'', must be given to restrict the search space. Any upper bounds that are inf are changed to 10000.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|-
|||''FUNCS.c''||Name of m-file computing the vector of constraint functions ''c''(''x'').
|-
|||''Name''||Name of the problem. Used for security if doing warm start.
|-
|||''PriLevOpt''||Print level. 0 = silent. 1 = some printing.  2 = print each iteration.
|-valign="top"
|||''WarmStart''||If true (''> ''0), ''glcSolve ''reads the output  from the last run from the mat-file ''glcSave.mat'', and continues from the last run.  NOTE: All rectangles that are fathomed in the previous run are deleted.  This saves space and computational time and enables solving larger problems and more function evaluations to be done.
|-
|||''MaxCPU''||Maximal CPU Time (in seconds) to be used.
|-
|||''glcDirect''||Structure with DIRECT algorithm specific parameters. Fields used:
|-valign="top"
|||''fcALL''||=0 (Default). If linear constraints cannot be feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point.
|-valign="top"
||||||=1 Always compute f(x)  and c(x), even if linear constraints are not feasible anywhere in rectangle. Do not update rates of change for the constraints.
|-valign="top"
|||||=2 Always compute f(x)  and c(x), even if linear constraints are not feasible anywhere in rectangle. Update rates of change constraints.
|-valign="top"
|||''useRoC''||=1 (Default).  Use original Rate of Change (RoC) for constraints to weight the constraint violations in selecting which rectangle divide.
|-valign="top"
|||||=0 Avoid RoC, giving equal weights to all constraint violations. Suggested if difficulty  to find feasible points.  For problems where linear constraints have been added among the nonlinear (NOT  RECOMMENDED;  AVOID!!!),  then option useRoc=0  has been successful, whereas useRoC completely fails.
|-valign="top"
|||||=2  Avoid  RoC for linear constraints, giving weight  one to these constraint violations, whereas the nonlinear constraints use RoC.
|-valign="top"
|||||=3 Use RoC for nonlinear constraints, but linear constraints are not used to determine which rectangle to use.
|-valign="top"
|||''BRANCH''||=0 Divide rectangle by selecting the longest side, if ties use the lowest index. This is the Jones DIRECT  paper strategy.
|-valign="top"
|||||=1  First  branch the integer variables, selecting the variable with  the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0.  DEFAULT! Normally much more efficient than =0 for mixed- integer problems.
|-valign="top"
|||||=2 First branch the integer variables with 1,2 or 3 possible values, e.g \[0,1\],\[0,2\] variables, selecting the variable with least splits. Then branch the other integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables  as in BRANCH=0.
|-valign="top"
|||||=3  Like  =2,  but  use priorities  on the variables, similar  to  ''mipSolve'', see Prob.MIP.VarWeight.
|-valign="top"
|||''RECTIE''||When minimizing the measure to find which new rectangle to try to get feasible, there are often ties, several rectangles have the same minimum. RECTIE = 0 or 1 seems reasonable choices. Rectangles  with low index are often larger then the rectangles with higher index.  Selecting one of each type could help, but often =0 is fastest.
|-
|||||=0 Use the rectangle with value a, with lowest index (original).
|-
|||||=1 (Default):  Use 1 of the smallest and 1 of largest rectangles.
|-
|||||=2 Use the last rectangle with the same value a, not the 1st.
|-
|||||=3 Use one of the smallest rectangles with same value a.
|-
|||||=4 Use all rectangles with the same value a, not just the 1st.
|-valign="top"
|||''EqConFac''||Weight factor for equality constraints when adding to objective function f(x) (Default value 10). The weight is computed as EqConFac/"right or left hand side constant value", e.g. if the constraint is Ax ''<''= b, the weight is EqCon- Fac/b If DIRECT  just is pushing down the f(x) value instead of fulfilling  the equality constraints, increase EqConFac.
|-valign="top"
|||''AxFeas''||Set nonzero to make glcSolve skip f(x) evaluations, when the linear constraints are infeasible, and still  no feasible point  has been found.  The default  is 0. Value 1 demands ''f cALL  ''== 0. This option could save some time if f(x) is a bit costly, however overall performance could on some problems be dramatically worse.
|-valign="top"
|||''fEqual''||All  points with  function values within  tolerance fEqual are considered to be global minima and returned. Default 1E-10.
|-valign="top"
|||''LinWeight''||''RateOfChange'' = ''LinWeight'' * <nowiki>||a(i, :)||</nowiki> for linear constraints.  Balance be- tween linear and nonlinear constraints. Default 0.1. The higher value, the less influence from linear constraints.
|-
|||''alpha''||Exponential forgetting factor in RoC computation, default 0.9.
|-valign="top"
|||''AvIter''||How many values to use in startup of RoC computation before switching to exponential smoothing with forgetting factor alpha. Default 50.
|-valign="top"
|||colspan="2"|If WarmStart is chosen, the following fields in ''glcSave.mat ''are also used and contains information from the previous run:
|-
|||''C''||Matrix  with all rectangle centerpoints.
|-
|||''D''||Vector with distances from centerpoint to the vertices.
|-
|||''F''||Vector with function values.
|-
|||''G''||Matrix with constraint values for each point.
|-
|||''Name''||''Name of the problem. Used for security if doing warm start.
|-valign="top"
|||''Split''||''Split''(''i, j'') is the number of splits along dimension ''i ''of rectangle ''j''.
|-
|||''T''||''T ''(''i'') is the number of times rectangle ''i ''has been trisected.
|-
|||''fMinEQ''||sum(abs(infeasibilities)) for minimum points, 0 if no equalities.
|-
|||''fMinIdx''||Indices of the currently best points.
|-
|||''feasible''||Flag indicating if a feasible point has been found.
|-
|||''glcfmin''||Best function value found at a feasible point.
|-valign="top"
|||''iL''||''iL''(''i, j'') is the lower bound for rectangle ''j ''in integer dimension ''I ''(''i'').
|-valign="top"
|||''iU''||''iU ''(''i, j'') is the upper bound for rectangle ''j ''in integer dimension ''I ''(''i'').
|-
|||''ignoreidx''||Rectangles to be ignored in the rectangle selection procedure.
|-
|||''s''||''s''(''j'') is the sum of observed rates of change for constraint ''j''.
|-
|||''s_0''||''s_''0 is used as ''s''(0).
|-
|||''t''||''t''(''i'') is the total number of splits along dimension ''i''.
|-
|||''SubRes''||Additional  output from nlp f, if suboptimization done.
|-valign="top"
|||''optParam''||Structure with special fields for optimization parameters, see Table 141 on page 229.
|-valign="top"
|||||Fields  used  by  ''glcSolve ''are: ''IterPrint'', ''bTol'', ''cTol'', ''MaxIter  ''(default''max''(5000'', n * ''1000)), ''MaxFunc ''(default ''max''(10000'', n * ''2000)), ''EpsGlob'', ''fGoal'', ''eps_f'', ''eps_x''.
|-
|''varargin''||colspan="2"|Other parameters directly sent to low level routines.
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Matrix  with all points giving the function value ''f_k''.
|-
|||''f_k''||Function value at optimum.
|-
|||''c_k''||Nonlinear constraints values at ''x_k''.
|-
|||''glcSave.mat''||Special file containing:
|-
|||''C''||Matrix  with all rectangle centerpoints.
|-
|||''D''||Vector with distances from centerpoint to the vertices.
|-
|||''F''||Vector with function values.
|-
|||''G''||Matrix  with constraint values for each point.
|-
|||''Name''||''Name of the problem. Used for security if doing warm start.
|-
|||''Split''||''Split''(''i, j'') is the number of splits along dimension ''i ''of rectangle ''j''.
|-
|||''T''||''T ''(''i'') is the number of times rectangle ''i ''has been trisected.
|-
|||''fMinEQ''||sum(abs(infeasibilities)) for minimum points, 0 if no equalities.
|-
|||''fMinIdx''||Indices of the currently best points.
|-
|||''feasible''||Flag indicating if a feasible point has been found.
|-
|||''glcf min''||Best function value found at a feasible point.
|-
|||''iL''||''iL''(''i, j'') is the lower bound for rectangle ''j ''in integer dimension ''I ''(''i'').
|-
|||''iU''||''iU ''(''i, j'') is the upper bound for rectangle ''j ''in integer dimension ''I ''(''i'').
|-
|||''ignoreidx''|||Rectangles to be ignored in the rectangle selection procedure.
|-
|||''s''||''s''(''j'') is the sum of observed rates of change for constraint ''j''.
|-
|||''s_0''||''s_''0 is used as ''s''(0).
|-
|||''t''||''t''(''i'') is the total number of splits along dimension ''i''.
|-
|||''Iter''||Number of iterations.
|-
|||''FuncEv''||Number function evaluations.
|-
|||''maxTri''||Maximum size of any triangle.
|-
|||''ExitText''||Text string giving ExitFlag and Inform information.
|-
|||''ExitFlag''||0 - Reached maxFunc or maxIter. 
|-
|||||2 - Some upper bounds below lower bounds.
|-
|||||7 - Reached maxFunc or maxIter, NOT feasible.
|-
|||||8 - Empty domain for integer variables.
|-valign="top"
|||''Inform''||1 = Function value f is less than fGoal. 2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f-fGoal)/abs(fGoal) ''<''= fTol. 3 = Maximum number of iterations done. 4 = Maximum number of function evaluations done. 9 = Max CPU Time reached. 91= Infeasible. 99= Input error, see ExitFlag.
|}
 
'''Description'''
 
The routine ''glcSolve ''implements an extended version of DIRECT,  see  \[52\], that handles problems with  both nonlinear and integer constraints.
 
DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore ''glcSolve ''is run for a predefined number of function evaluations and considers the best function value found as the optimal one. It is possible for the user to '''restart '''''glcSolve ''with the final status of all parameters from the previous run, a so called ''warm start ''Assume that a run has been made with ''glcSolve ''on a certain problem for 500 function evaluations. Then a run of e.g. 200 function evaluations more should give the same result as if the run had been using 700 function evaluations in the first place. To do a warm start of ''glcSolve ''a flag ''Prob.WarmStart ''should be set to one. Then ''glcSolve ''is using output previously written to the file ''glcSave.mat ''to make the restart.
 
DIRECT does not explicitly  handle equality constraints.  It works best when the integer variables describe an ordered quantity and is less effective when they are categorical.
 
'''M-files  Used'''
 
''iniSolve.m'', ''endSolve.m''
 
====infLinSolve====
 
'''Purpose'''


Finds a linearly constrained minimax solution of a function of several variables with  the use of any suitable TOMLAB  solver. The decision variables may be binary or integer.
Finds a linearly constrained minimax solution of a function of several variables with  the use of any suitable TOMLAB  solver. The decision variables may be binary or integer.


infLinSolve solves problems of the type:
*[[infLinSolve]]
 
 
<math>
\begin{array}{cccccc}
\min\limits_x & \multicolumn{5}{l}{\max Dx} \\\mbox{subject to} & x_L & \leq &    x  & \leq &  x_U \\& b_L & \leq &  Ax  & \leq &  b_U \\\end{array}
</Math>
 
 
where <Math>$x,x_L,x_U \in \Rdim{n}$</Math> , <Math>$b_L,b_U \in \Rdim{m_1}$</Math> , <Math>$A \in\Rdim{m_1 \times n}$</Math> and <Math>$D \in \Rdim{m_2 \times n}$</Math> . The variables <math>$x \in I$</Math> , the index subset of <Math>$1,...,n$</Math> are restricted to be integers. The different objectives are stored in D row-wise.
 
'''Calling  Syntax'''
 
Result=infLinSolve(Prob,PriLev)
 
'''Description  of Inputs'''
 
{|
|-valign="top"
|''Prob''||colspan="2"|Structure Prob.  Prob must be defined. Best is to use Prob = lp/mipAssign(.....),  if using the TQ format. Prob.QP.D matrix should then be set to the rows (Prob.QP.c ignored).
|-
|||''PriLev''||Print level in ''infLinSolve''.
|-
|||||= 0 Silent except for error messages.
|-
|||||''> ''0 Print summary information about problem transformation.
|-
|||||Calls ''PrintResult ''with specified ''PriLev''.
|-
|||||= 2 Standard output from ''PrintResult ''(default).
|-
|||colspan="2"|Extra fields used in Prob:
|-valign="top"
|||''SolverInf''||Name of the TOMLAB  solver. Valid names are: cplex, minos, snopt, xa and more.  SeeSolverList('lp');  or SolverList('mip');
|-
|||''QP.D''||The rows with the different objectives.
|-
|||''f_Low''||Lower bound on the objective (optional).
|-
|||''f_Upp''||Upper bound on the objective (optional).
|}
 
'''Description  of Outputs'''
 
{|
|-valign="top"
|''Result||colspan="2"|''Structure with results from optimization.  Output depends on the solver used.
|-valign="top"
|||||The fields ''x_k'', ''f_k'', ''x_0'', ''xState'', ''bState'', ''v_k ''are transformed back to match the original problem.
|-valign="top"
|||||The output in Result.Prob is the result after infLinSolve transformed the problem, i.e. the altered Prob structure
|}
 
'''Description'''
 
The linear minimax problem is solved in infLinSolve by rewriting the problem as a linear optimization problem. One additional variable <math>$z\in \MATHSET{R}$</math>, stored as <math>$x_{n+1}$</math> is added and the problem is rewritten as:
 
 
<math>
\begin{array}{cccccc}
\multicolumn{6}{l}{\min\limits_x  z}\\
\\\mbox{subject to} & x_L & \leq & (x_1,x_2,\ldots,x_n)^T & \leq & x_U \\&  -\infty & \leq &  z                    & \leq & \infty \\&  b_L    & \leq & A x                    &\leq & b_U \\&  -\infty & \leq & D x - z e              & \leq & 0 \\
\end{array}
</math>
 
 
where <math>$e \in \Rdim{N},\; e(i)=1 \ \forall i$</math>.
 
To handle  cases where  a row in D\*x is taken the absolute value of: ''minmax\|D * x\|'', expand the problem with extra residuals with the opposite sign: \[''D * x''; ''-D * x''\].
 
'''See Also'''
 
''lpAssign''.


====infSolve====
==infSolve==
 
 
 
'''Purpose'''


Find a constrained minimax solution with the use of any suitable TOMLAB solver.
Find a constrained minimax solution with the use of any suitable TOMLAB solver.


infSolve solves problems of the type:
*[[infSolve]]


 
==linRatSolve==
 
<math>
\begin{array}{cccccc}
\min\limits_x & \multicolumn{5}{l}{\max r(x)} \\\mbox{subject to} & x_L & \leq &    x  & \leq &  x_U \\& b_L & \leq &  Ax  & \leq &  b_U \\& c_L & \leq &  c(x) & \leq &  c_U \\
\end{array}
</math>
 
where <math>$x,x_L,x_U \in \Rdim{n}$</math> , <math>$r(x) \in \Rdim{N}$</math> , <math>$c(x),c_L,c_U \in\Rdim{m_1}$</math> , <math>$b_L,b_U \in \Rdim{m_2}$</math> and <math>$A \in \Rdim{m_2 \times n}$</math>.
 
'''Calling  Syntax'''
 
Result=infSolve(Prob,PriLev)
 
'''Description  of Inputs'''
 
{|
|-valign="top"
||''Prob''||colspan="2"|Problem description structure. Should be created in the '''cls''' format. infSolve uses two special fields in ''Prob'':
|-
|||''SolverInf''||Name of solver used to solve the transformed problem.
|-
|||||Valid choices are ''conSolve'', ''nlpSolve'', ''sTrustr ''and ''clsSolve''.
|-
|||||If TOMLAB /SOL is installed: ''minos'', ''snopt'', ''npopt''.
|-
|||''InfType''||1 - constrained formulation (default).
|-
|||||2 - LS penalty approach (experimental).
|-
|||colspan="2"|The remaining fields of ''Prob ''should be defined  as required by the selected subsolver.
|-
|||''PriLev''||Print level in ''infSolve''.
|-
|||||= 0 Silent except for error messages.
|-
|||||''> ''0 Print summary information about problem transformation.
|-
|||||Calls ''PrintResult'' with specified ''PriLev''.
|-
|||||= 2Standard output from ''PrintResult ''(default).
|}
 
'''Description  of Outputs'''
 
{|
|-valign="top"
|''Result''||colspan="2"|Structure with results from optimization.  Output depends on the solver used.
|-valign="top"
|||colspan="2"|The fields ''x_k'', ''r_k'', ''J_k'', ''c_k'', ''cJac'', ''x_0'', ''xState'', ''cState'', ''v_k ''are transformed back to match the original problem.
|-
|||colspan="2"|''g_k ''is calculated as <math>\VAR{J\_k</math><math>$^T$</math><math>}</math> <math>$\cdot$</math> <math>\VAR{r\_k}</math>.
|-valign="top"
|||colspan="2"|The output  in Result.Prob is the result after infSolve  transformed the problem, i.e. the altered Prob structure
|}
 
'''Description'''
 
The minimax problem is solved in infSolve by rewriting the problem as a general constrained optimization problem. One additional variable <math>$z\in \MATHSET{R}$</math>, stored as <math>$x_{n+1}$</math> is added and the problem is rewritten as:
 
<math>
\begin{array}{cccccc}
\multicolumn{6}{l}{\min\limits_x  z}\\\\\mbox{subject to} & x_L & \leq & (x_1,x_2,\ldots,x_n)^T & \leq & x_U \\&  -\infty & \leq &  z                    & \leq & \infty \\&  b_L    & \leq & A x                    & \leq & b_U \\&  c_L    & \leq & c(x)                  & \leq & c_U \\&  -\infty & \leq & r(x) - z e            & \leq & 0 \\\end{array}
</math>
 
 
where <math>$e \in \Rdim{N},\; e(i)=1 \ \forall i$</math>.
 
To handle cases where an element <math>$r_i(x)$</math> in <math>$r(x)$</math> appears in absolute value:  <math>$\min \max |r_i(x)|$</math>, expand the problem with extra residuals with the opposite sign: <math>$ [ r_i(x); -r_i(x) ] $</math>
 
'''Examples'''
 
''minimaxDemo.m''.
 
'''See Also'''
 
''clsAssign''.
 
====linRatSolve====
 
'''Purpose'''


Finds a linearly constrained solution of a function of the ratio of two linear functions with the use of any suitable TOMLAB  solver. Binary and integer variables are not supported.
Finds a linearly constrained solution of a function of the ratio of two linear functions with the use of any suitable TOMLAB  solver. Binary and integer variables are not supported.


linRatSolve solves problems of the type:
*[[linRatSolve]]
 


<math>
==lpSimplex==
\begin{array}{cccccc}
\min\limits_x & \multicolumn{5}{l}{ \Large (c1 x) \over (c2 x)  } \\\mbox{subject to} & x_L & \leq &    x  & \leq &  x_U \\& b_L & \leq &  Ax  & \leq &  b_U \\
\end{array}
</math>
 
where <math>$c1,c2,x,x_L,x_U \in \Rdim{n}$</math> , <math>$b_L,b_U \in \Rdim{m_1}$</math> and <math>$A \in \Rdim{m_1 \times n}$</math>.
 
'''Calling  Syntax'''
 
Result=linRatSolve(Prob,PriLev)
 
'''Description  of Inputs'''
 
{|
|-valign="top"
|''Prob''||colspan="2"|Structure Prob.  Prob must be defined. Best is to use Prob = lpAssign(.....), if using the TQ format. Prob.QP.c1/c2 matrices should then be set (Prob.QP.c ignored).
|-
|''PriLev''||Print level in ''linRatSolve''.
|-
|||= 0Silent except for error messages.
|-
|||''> ''0 Print summary information about problem transformation.
|-
|||Calls ''PrintResult ''with specified ''PriLev''.
|-
|||= 2 Standard output from ''PrintResult ''(default).
|-
|colspan="2"|Extra fields used in Prob:
|-valign="top"
|''SolverRat''||Name of the TOMLAB  solver. Valid names are: cplex, minos, snopt, xa and more.  See SolverList('lp');
|-
|''QP.c1''||The numerator in the objective.
|-
|''QP.c2''||The denominator in the objective.
|-
|''z1_L ''||Lower bound for z1 (default 1e-5). See description below
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||Structure with results from optimization. Output depends on the solver used.
|-valign="top"
|||The fields ''x_k'', ''f_k'', ''x_0'', ''xState'', ''bState'', ''v_k ''are transformed back to match the original problem.
|-
|||The output in Result.Prob is the result after linRatSolve transformed the problem, i.e. the altered Prob structure
|}
 
'''Description'''
 
The linear ratio problem is solved by linRatSolve by rewriting the problem as a linear constrained optimization problem. n+1 variables z1 and z2(2:n+1) are needed, stored as x(1:n+1).  The n original variables are removed so one more variable exists in the final problem.
 
 
<math>
\begin{array}{ccc}
\\
z1  &  = & 1 / (c2 x)  \\
z2  &  = & x  z1  \\
z1 (c1  x) & = &  (c1  z1  x) = c1  z2\\
\end{array}
</math>
 
 
The problem then becomes:
 
 
<math>
\begin{array}{cccccc}
\multicolumn{6}{l}{\min\limits_x  c1 z2}\\\\\mbox{subject to} & z1_L      & \leq & z1              & \leq & \infty \\&  1        & \leq & c2 z2          & \leq & 1 \\&  0        & \leq & A z2 - z1 beq  & \leq & 0 \\&  -\infty  & \leq & A z2 - z1 b_U  & \leq & 0 \\&  -\infty  & \leq & - A z2 + z1 b_L & \leq & 0 \\\\&  0        & \leq & A1 z2 - z1 xeq  & \leq & 0 \\&  -\infty  & \leq & A1 z2 - z1 x_U  & \leq & 0 \\&  -\infty  & \leq & - A1 z2 + z1 x_L & \leq & 0 \\
\end{array}
</math>
 
where <math>$A1 \in \Rdim{N},\; A1=speye(N)$</math>.
 
OBSERVE the denominator ''c''2''x ''must always be positive. It is normally a good a idea to run the problem with both signs (multiply  each side by -1).
 
'''See Also'''
 
''lpAssign''.
 
====lpSimplex====
 
'''Purpose'''


Solve general linear programming problems.
Solve general linear programming problems.


''lpSimplex ''solves problems of the form
*[[lpSimplex]]


 
==L1Solve==
<math>
\begin{array}{cccccl}
\min\limits_{x} & f(x) & = & c^{T}x &  &  \\s/t & x_{L} & \leq  & x  & \leq  & x_{U} \\& b_{L} & \leq  & Ax  & \leq  & b_{U} \\
\end{array}
</math>
 
 
where <math>$x,x_{L},x_{U}\in \MATHSET{R} ^{n}$</math> , <math>$c \in \MATHSET{R}^{n}$</math> , <math>$A\in \MATHSET{R}^{m\times n}$</math> and <math>$b_{L},b_{U} \in \MATHSET{R}^{m}$</math>.
 
'''Calling  Syntax'''
 
Result = lpSimplex(Prob) or
 
Result = tomRun('lpSimplex', Prob, 1);
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''QP.c''||Constant vector.
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''x_L''||Lower bounds on the variables.
|-
|||''x_U''||Upper bounds on the variables.
|-
|||''x_0''||Starting point.
|-
|||''Solver.Alg''||Variable selection rule to be used:
|-
|||||0: Minimum reduced cost.
|-
|||||1: Bland's rule (default).
|-
|||||2: Minimum reduced cost. Dantzig's rule.
|-
|||''QP.B''||Active set ''B 0 ''at start:
|-
|||||''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set.
|-
|||||''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound.
|-
|||||''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound.
|-
|||''optParam''||Structure with special fields for optimization parameters,  see Table 141.
|-valign="top"
|||||Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps_f'', ''eps_Rank'', ''xTol ''and ''bTol''.
|}
 
 
'''Description  of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization.  The following fields are changed:
|-
|||''x_k''||Optimal point.
|-
|||''f_k''||Function value at optimum.
|-
|||''g_k''||Gradient value at optimum, ''c''.
|-
|||''v_k''||Lagrange multipliers.
|-
|||''x_0''||Starting point.
|-
|||''f_0''||Function value at start.
|-
|||''xState''||State of each variable, described in Table 150.
|-
|||''ExitFlag''||0: Optimal solution found.
|-
|||||1: Maximal number of iterations reached.
|-
|||||2: Unbounded feasible region.
|-
|||||5: Too many active variables in given initial  point.
|-
|||||6: No feasible point found with Phase 1.
|-
|||||10: Errors in input parameters.
|-
|||||11: Illegal initial  x as input.
|-
|||''Inform''||If ''ExitF lag > ''0, ''I nf orm ''= ''ExitF lag''.
|-
|||''QP.B''||Optimal active set. See input variable ''QP.B''.
|-
|||''Solver''||Solver used.
|-
|||''SolverAlgorithm ''||Solver algorithm used.
|-
|||''Iter''||Number of iterations.
|-valign="top"
|||''FuncEv''||Number of function evaluations. Equal to ''Iter''. ''ConstrEv ''Number of constraint evaluations.  Equal to ''Iter''.
|-
|||''Prob''||Problem structure used.
|}
 
'''Description'''
 
The routine ''lpSimplex ''implements an active  set strategy (Simplex method) for Linear Programming using an additional set of slack variables for the linear constraints. If the given starting point is not feasible then a Phase I objective is used until a feasible point is found.
 
'''M-files  Used'''
 
''ResultDef.m''
 
'''See Also'''
 
''qpSolve''
 
====L1Solve====
 
'''Purpose'''


Find a constrained L1 solution of a function of several variables with the use of any suitable nonlinear TOMLAB solver.
Find a constrained L1 solution of a function of several variables with the use of any suitable nonlinear TOMLAB solver.


''L1Solve ''solves problems of the type:
*[[L1Solve]]
 
 
<math>
\begin{array}{cccccc}
\min\limits_x & \multicolumn{5}{l}{\sum_i |r_i(x)|} \\\mbox{subject to} & x_L & \leq &  x  & \leq & x_U \\{}                & b_L & \leq &  Ax  & \leq & b_U \\{}                & c_L & \leq & c(x) & \leq & c_U \\
\end{array}
</math>
 
 
where <math>$x,x_L,x_U \in \Rdim{n}$</math> , <math>$r(x) \in \Rdim{N}$</math> , <math>$c(x),c_L,c_U\in \Rdim{m_1}$</math> , <math>$b_L,b_U \in \Rdim{m_2}$</math> and <math>$A\in \Rdim{m_2 \times n}$</math>.


 
==MilpSolve==
'''Calling  Syntax'''
 
Result = L1Solve(Prob,PriLev)
 
'''Description  of Inputs'''
 
{|
|-valign="top"
|''Prob ''||colspan="2"|Problem description structure. ''Prob ''should be created in the '''cls '''constrained nonlinear format.
|-
|||colspan="2"|''L1Solve'' uses one special field in ''Prob'':
|-valign="top"
|||''SolverL1''||Name of the TOMLAB  solver used to solve the augmented general nonlinear problem generated by ''L1Solve''.
|-valign="top"
|||colspan="2"|Any other fields are passed along to the solver specified by ''Prob.SolverL1''. In particular:
|-
|||''A''||Linear constraint matrix.
|-
|||''b_L''||Lower bounds on variables.
|-
|||''b_U''||Upper bounds on variables.
|-
|||''c_L''||Lower bounds for nonlinear constraints.
|-
|||''c_U''||Upper bounds for nonlinear constraints..
|-
|||''x_L''||Lower bounds on variables.
|-
|||''x_U''||Upper bounds on variables.
|-
|||''x_0''||Starting point.
|-
|||''ConsPattern''||Nonzero patterns of constraint and residual Jacobians.
|-valign="top"
|||''JacPattern''||Prob.LS.y must have the correct residual length if ''JacPattern ''is empty  but ''ConsPattern ''is not.
|-valign="top"
|||||''L1Solve ''will create the new patterns for the sub-solver using the information supplied in these two fields.
|-
|||''PriLev''||Print level in ''L1Solve''.
|-
|||= 0||silent except for error messages.
|-
|||''> ''0||print summary information about problem transformation.
|-
|||||Calls ''PrintResult ''with specified ''PriLev''.
|-
|||= 2||standard output from ''PrintResult''.
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||Structure with results from optimization. Fields changed depends on which solver was used for the extended problem.
|-
|||The fields ''x_k'', ''r_k'', ''J_k'', ''c_k'', ''cJac'', ''x_0'', ''xState'', ''cState'', ''v_k'', are transformed back to the format of the original L1 problem. ''g k ''is calculated as <math>{J\_k</math><math>$^T$</math><math>}</math> · ''r k''.  The returned problem structure ''Result.Prob ''is the result after ''L1Solve ''transformed the problem, i.e. the altered ''Prob ''structure.
 
'''Description'''
 
L1Solve solves the L1 problem by reformulating it as the
 
general constrained optimization problem
 
 
<math>
\begin{array}{cccccc}
\min\limits_x & \multicolumn{5}{l}{\sum_i (y_i+z_i) }  \\
\mbox{subject to} & x_L & \leq & x        & \leq & x_U    \\
{}                & 0  & \leq & y        & \leq & \infty \\
{}                & 0  & \leq & z        & \leq & \infty \\
{}                & b_L & \leq & Ax      & \leq & b_U      \\
{}                & c_L & \leq & c(x)    & \leq & c_U    \\
{}                & 0  & \leq & r(x)+y-z & \leq & 0    \\
\end{array}
</math>
 
 
A problem with ''N ''residuals is extended with 2''N ''nonnegative variables <math>$y,z \in \Rdim{N}$</math> along with ''N'' equality constraints <math>$r_i(x) + y_i - z_i = 0$</math>.
 
'''See Also'''
 
''infSolve''
 
 
 
====MILPSOLVE====
 
'''Purpose'''


Solve mixed integer linear programming problems (MILP).
Solve mixed integer linear programming problems (MILP).


''MILPSOLVE  ''solves problems of the form
*[[MilpSolve]]
 
 
<math>
\begin{array}{cccccc}
\min\limits_{x} & f(x) & = & c^{T}x &  \\s/t & x_{L} & \leq  & x  & \leq & x_{U} \\& b_{L} & \leq  & Ax & \leq & b_{U} \\&      &      & \multicolumn{3}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \in $I$}  \\
\end{array}
</math>
 
 
where <math>c, x, x_L, x_U \in \MATHSET{R}^{n}</math> , <math>A\in\MATHSET{R}^{m\times n}</math> and <math>b_L, b_U \in MATHSET{R}^{m}</math>. The variables <math>x \in I</math> , the index subset of <math>1,...,n</math> are restricted to
be integers.
 
'''Calling  Syntax'''
 
Result = tomRun('MILPSOLVE',Prob, 1); or


Prob = ProbCheck(Prob, 'MILPSOLVE');
==minlpSolve==
 
Result = milpsolveTL(Prob);
 
PrintResult(Result,1);
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''x_L, x_U''||Lower and upper bounds on variables. (Must be dense).
|-
|||''b_L, b_U''||Lower and upper bounds on linear constraints. (Must be dense).
|-
|||''A''||Linear constraint matrix. (Sparse or dense).
|-
|||''QP.c''||Linear objective function coefficients,  size ''nx''1.
|-
|||''BIG''||Definition of infinity.  Default is 1e30.
|-valign="top"
|||''LargeScale''||Defines if milpsolveTL will convert the A matrix to a sparse matrix or not.
|-
|||||Largescale ! = 0 - sparse
|-
|||||LargeScale = 0 - dense
|-
|||||Default is to use the A matrix just as it is defined.
|-
|||''PriLevOpt''||Specifies the printlevel that will be used by MILPSOLVE.
|-
|||||0 (NONE) No outputs
|-
|||||1 (NEUTRAL) Only some specific debug messages in debug print rou- tines are reported.
|-valign="top"
|||||2 (CRITICAL) Only critical  messages are  reported.  Hard errors like instability,  out of memory.
|-
|||||3 (SEVERE) Only severe messages are reported. Errors.
|-
|||||4 (IMPORTANT) Only important messages are reported. Warnings and Errors.
|-
|||||5 (NORMAL) Normal messages are reported.
|-valign="top"
|||||6 (DETAILED) Detailed messages are reported. Like model size, con- tinuing B&B improvements.
|-
|||||7 (FULL)  All messages are reported. Useful for debugging purposes and small models.
|-valign="top"
|||||Default print level is 0, no outputs. PriLevOpt ''< ''0 is interpreted as 0, and larger than 7 is interpreted as 7.
|-valign="top"
|||''MaxCPU''||Maximal CPU Time (in seconds) to be used by MILPSOLVE, stops with best point found.
|-valign="top"
|colspan="3"|Fields used in '''Prob.MILPSOLVE '''(Structure with MILPSOLVE specific parameters)
|-valign="top"
|||''ANTI_DEGEN''||Binary vector. If empty, no anti-degeneracy handling is applied. If the length (i) of the vector is less than 8 elements,only the i first modes are considered. Also if i is longer than 8 elements, the elements after element8 are ignored.
|-
|||||ANTI_DEGEN specifies if special handling must be done to reduce de- generacy/cycling while solving. Setting this flag can avoid cycling, but can also increase numerical instability.
|-
|||||ANTIDEGEN FIXEDVARS  ! = 0 Check if  there are equality slacks in the basis and try  to drive  them out in order to reduce chance of degeneracy in Phase 1.
|-
|||||ANTIDEGEN COLUMNCHECK  != 0
|-
|||||ANTIDEGEN STALLING  != 0
|-
|||||ANTIDEGEN NUMFAILURE != 0
|-
|||||ANTIDEGEN LOSTFEAS != 0
|-
|||||ANTIDEGEN INFEASIBLE  != 0
|-
|||||ANTIDEGEN DYNAMIC != 0
|-
|||||ANTIDEGEN DURINGBB != 0
|-valign="top"
|||''basis''||If empty or erroneous, default basis is used. Default start base is the all slack basis (the default simplex starting basis).
|-
|||||Prob.MILPSOLVE.basis stores the basic variables. If an element is less then zero then it means on lower bound, else on upper bound. Element 0 of the array is unused. The default initial basis is bascolumn\[x\] = -x. By MILPSOLVE  convention, a basic variable is always on its lower bound, meaning that basic variables is always represented with a minus sign.
|-
|||||When a restart is done, the basis vector must be assigned  a correct starting basis.
|-valign="top"
|||''BASIS_CRASH''||The set basiscrash  function  specifies  which basis crash mode  MILP- SOLVE will used.
|-
|||||When no base crash is done (the default), the initial  basis from which MILPSOLVE starts to solve the model is the basis containing all slack or artificial variables that is automatically associates with each constraint.
|-
|||||When base crash is enabled, a heuristic "crash procedure" is executed before the first simplex iteration to quickly choose a basis matrix that has fewer artificial  variables. This procedure tends to reduce the num- ber of iterations to optimality  since a number of iterations are skipped. MILPSOLVE  starts iterating from this basis until optimality.
|-
|||||BASIS_CRASH ! = 2 - No basis crash
|-
|||||BASIS_CRASH = 2 - Most feasible basis
|-
|||||Default is no basis crash.
|-valign="top"
|||''BB_DEPTH_LIMIT''||Sets the maximum branch-and-bound depth.  This value makes  sense only if there are integer, semi-continuous or SOS variables in the model so that the branch-and-bound algorithm is used to solve the model. The branch-and-bound algorithm will not go deeper than this level. When BB DEPTH LIMIT i set to 0 then there is no limit  to the depth. The default value is -50. A positive value means that the depth is absolute. A negative value means a relative B&B  depth.  The "order"  of a MIP problem is defined to be 2 times the number of binary variables plus the number of SC and SOS variables. A relative value of -x results in a maximum depth of x times the order of the MIP problem.
|-
|||''BB_FLOOR_FIRST''||Specifies which branch to take first in branch-and-bound algorithm. Default value is 1.
|-
|||||BB_FLOOR_FIRST = 0 (BRANCH CEILING) Take ceiling branch first
|-
|||||BB_FLOOR_FIRST = 1 (BRANCH FLOOR) Take floor branch first
|-
|||||BB_FLOOR_FIRST = 2 (BRANCH AUTOMATIC) MILPSOLVE decides which branch being taken first
|-
|||''BB_RULE''||Specifies the branch-and-bound rule. Default value is 0.
|-
|||||BB_RULE  = 0 (NODE FIRSTSELECT)  Select lowest  indexed non- integer column
|-
|||||BB_RULE = 1 (NODE GAPSELECT) Selection based on distance from the current bounds
|-
|||||BB_RULE = 2 (NODE RANGESELECT) Selection based on the largest current bound
|-
|||||BB_RULE = 3 (NODE FRACTIONSELECT) Selection based on largest fractional value
|-
|||||BB_RULE = 4 (NODE PSEUDOCOSTSELECT4) Simple, unweighted pseudo-cost of a variable
|-
|||||BB_RULE = 5 (NODE PSEUDONONINTSELECT)  This is an ex- tended pseudo-costing strategy based on minimizing the number of in- teger infeasibilities.
|-
|||||BB RULE = 6 (NODE PSEUDORATIOSELECT)  This is an extended pseudo-costing strategy based on maximizing the normal pseudo-cost divided by the number of infeasibilities. Effectively, it is similar to (the reciprocal of ) a cost/benefit ratio.
|-
|||||BB_RULE = 7 (NODE USERSELECT)
|-valign="top"
|||''BB_RULE_ADD''||Additional values for the BB RULE. BB RULE is a vector. If the length i of the vector is less than 10 elements, only the i first modes are considered. Also if i is longer than 10 elements, the elements after element 10 is ignored.
|-
|||||BB_RULE ADD(1) ! = 0 (NODE WEIGHTREVERSEMODE)
|-
|||||BB_RULE ADD(2)  ! = 0 (NODE BRANCHREVERSEMODE) In case when get bb floorfirst is BRANCH AUTOMATIC, select the opposite direction (lower/upper branch) that BRANCH AUTOMATIC had cho- sen.
|-
|||||BB_RULE_ADD(3) ! = 0 (NODE GREEDYMODE)
|-
|||||BB_RULE_ADD(4) ! = 0 (NODE PSEUDOCOSTMODE)
|-
|||||BB_RULE_ADD(5) ! = 0 (NODE DEPTHFIRSTMODE) Select  the node that has already been selected before the number of times
|-
|||||BB_RULE_ADD(6) ! = 0 (NODE RANDOMIZEMODE)
|-
|||||BB_RULE_ADD(7) !  = 0 (NODE DYNAMICMODE)    When NODE DEPTHFIRSTMODE is selected, switch off this mode when a first solution is found.
|-
|||||BB_RULE_ADD(8) ! = 0 (NODE RESTARTMODE)
|-
|||||BB_RULE_ADD(9) ! = 0 (NODE BREADTHFIRSTMODE) Select the node that has been selected before the fewest number of times or not at all BB RULE ADD(10) ! = 0 (NODE AUTOORDER)
|-
|||''BFP''||Defines which Basis Factorization Package that will be used by MILP- SOLVE.
|-
|||||BFP = 0 : LUSOL
|-
|||||BFP = 1 : built in etaPHI from MILPSOLVE  v3.2
|-
|||||BFP = 2 : Additional  etaPHI BFP = 3 : GLPK
|-
|||||Default BFP is LUSOL.
|-valign="top"
|||''BREAK_AT_FIRST''||Specifies if the branch-and-bound algorithm stops at the first found so- lution (BREAK_AT_FIRST != 0) or not (BREAK_AT_FIRST = 0). De- fault is not to stop at the first found solution.
|-valign="top"
|||''BREAK_AT_VALUE'||Specifies if the branch-and-bound algorithm stops when the object value is better than a given value. The default value is (-) infinity.
|-valign="top"
|||''EPAGAP''||Specifies the absolute MIP gap tolerance for the branch and bound algo- rithm.  This tolerance is the difference between the best-found solution yet and the current solution. If the difference is smaller than this toler- ance then the solution (and all the sub-solutions) is rejected. The default value is 1e-9.
|-valign="top"
|||''EPGAP''||Specifies the relative MIP gap tolerance for the branch and bound algo- rithm.  The default value is 1e-9.
|-valign="top"
|||''EPSB''||Specifies the value that is used as a tolerance for the Right Hand Side (RHS) to determine whether  a value should be considered  as 0.  The default epsb value is 1.0e-10
|-valign="top"
|||''EPSD''||Specifies the value that is used as a tolerance for reduced costs to deter- mine whether a value should be considered as 0. The default epsd value is 1e-9. If EPSD is empty, EPSD is read from ''Prob.optParam.eps f''.
|-valign="top"
|||''EPSEL''||Specifies the value that is used as a tolerance for rounding values to zero. The default epsel value is 1e-12.
|-valign="top"
|||''EPSINT''||Specifies  the  tolerance that  is used  to determine whether a floating- point number is in fact an integer. The default value for epsint is 1e-7. Changing this tolerance value can result in faster solving times, but the solution is less integer.
|-valign="top"
|||''EPSPERTURB''||Specifies the value that is used as perturbation scalar for degenerative problems. The default epsperturb value is 1e-5.
|-valign="top"
|||''EPSPIVOT''||Specifies the value that is used as a tolerance pivot element to determine whether a value should be considered as 0. The default epspivot value is 2e-7
|-
|||''IMPROVEMENT_LEVEL''||Specifies the iterative improvement level.
|-
|||||IMPROVEMENT LEVEL = 0 (IMPROVE  NONE) improve none
|-
|||||IMPROVEMENT LEVEL = 1 (IMPROVE  FTRAN)  improve FTRAN
|-
|||||IMPROVEMENT LEVEL = 2 (IMPROVE  BTRAN)  improve BTRAN
|-
|||||IMPROVEMENT LEVEL  = 3 (IMPROVE  SOLVE) improve FTRAN + BTRAN.
|-
|||||IMPROVEMENT LEVEL  = 4 (IMPROVE  INVERSE)  triggers automatic inverse accuracy control in the dual simplex, and when an error gap is exceeded the basis is reinverted
|-
|||||Choice 1,2,3 should not be used with MILPSOLVE  5.1.1.3,  because of problems with the solver. Default is 0.
|-valign="top"
|||''LoadFile''||File that  contains the  model. If LoadFile is a nonempty string which corresponds to actual file, then the model is read from this file rather than from the Prob struct.
|-
|||''LoadMode''||1 - LP - MILPSOLVE  LP format
|-
|||||2 - MPS - MPS format
|-
|||||3 - FMPS - Free MPS format
|-
|||||A default value for this field does not exist. Both LoadFile and Load- Mode must be set if a problem will be loaded.
|-
|||||If there is something wrong with LoadMode or LoadFile, an error mes- sage will be printed and MILPSOLVE  will be terminated. Leave Load- Mode and LoadFile empty if the problem not will be loaded from file.
|-
|||''LogFile''||Name of file to print MILPSOLVE  log on.
|-
|||''MAXIMIZE ''||If  MAXIMIZE ! = 0, MILPSOLVE  is set to maximize the objective function, default is to minimize.
|-
|||''MAX_PIVOT''||Sets the maximum number of pivots between a re-inversion of the matrix. Default is 42.
|-
|||''NEG_RANGE''||Specifies the negative value below which variables are split into a negative and a positive part.  This value must always be zero or negative. If a positive value is specified, then 0 is taken. The default value is -1e6.
|-
|||''PRESOLVE''||Vector containing possible presolve options. If the length i of the vector is less than 7 elements, only the i first modes are considered. Also if i is longer than 7 elements, the elements after element 7 is ignored.
|-
|||||PRESOLVE(1) ! = 0 (PRESOLVE ROWS) Presolve rows
|-
|||||PRESOLVE(2) ! = 0 (PRESOLVE COLS) Presolve columns
|-
|||||PRESOLVE(3) ! = 0 (PRESOLVE LINDEP)  Eliminate linearly depen- dent rows
|-
|||||PRESOLVE(4) ! = 0 (PRESOLVE SOS) Convert constraints to SOSes (only SOS1 handled)
|-
|||||PRESOLVE(5) ! = 0 (PRESOLVE REDUCEMIP)  If the phase 1 solu- tion process finds that a constraint is redundant then this constraint is deleted.
|-
|||||PRESOLVE(6) ! = 0 (PRESOLVE DUALS) Calculate duals PRESOLVE(7) ! = 0 (PRESOLVE SENSDUALS) Calculate sensitivity if there are integer variables
|-
|||||Default is not to do any presolve.
|-
|||''PRICING_RULE''||The pricing rule can be one of the following rules.
|-
|||||PRICING_RULE = 0 Select first (PRICER_FIRSTINDEX)
|-
|||||PRICING_RULE = 1 Select according to Dantzig (PRICER_DANTZIG)
|-
|||||PRICING_RULE = 2 Devex pricing from Paula Harris (PRICER_DEVEX)
|-
|||||PRICING_RULE = 3 Steepest Edge (PRICER STEEPESTEDGE)
|-valign="top"
|||''PRICING_MODE''||Additional pricing settings, any combination of the modes below. This is a binary vector. If the length i of the vector is less than 7 elements, only the i first modes are considered. Also if i is longer than 7 elements, the elements after element 7 is ignored.
|-
|||||PRICE_PRIMALFALLBACK ! = 0 In case of Steepest Edge, fall back to DEVEX in primal.
|-
|||||PRICE_MULTIPLE ! = 0 Preliminary implementation of the multiple pricing scheme.  This means that attractive candidate entering columns from one iteration may be used in the subsequent iteration, avoiding full updating of reduced costs. In the current implementation, MILPSOLVE only reuses the 2nd best entering column alternative.
|-
|||||PRICE_PARTIAL ! = 0 Enable partial pricing
|-
|||||PRICE_ADAPTIVE ! = 0 Temporarily use First Index if cycling is detected
|-
|||||PRICE_RANDOMIZE  ! = 0 Adds a small randomization effect to the selected pricer
|-
|||||PRICE_LOOPLEFT  ! = 0 Scan entering/leaving columns left rather than right
|-
|||||PRICE_LOOPALTERNATE ! = 0 Scan entering/leaving columns alternatingly left/right
|-
|||||Default basis is PRICER DEVEX combined with PRICE ADAPTIVE.
|-
|||''sa''||Struct  containing information  of the sensitivity analysis (SA) MILPSOLVE will perform.
|-
|||||sa.obj =! 0 Perform sensitivity analysis on the objective function
|-
|||||sa.obj = 0 Do not perform sensitivity analysis on the objective function
|-
|||||sa.rhs =! 0 Perform sensitivity analysis on the right hand sides.
|-
|||||sa.rhs = 0 Do not perform sensitivity analysis on the right hand sides.
|-valign="top"
|||''SaveFileAfter''||Name  of a file to save the MILPSOLVE object after presolve.The name must be of type string (char), Example: Prob.MILPSOLVE.SaveFileAfter = 'save2' If the type is not char SaveFileBefore is set to save2.\[file extension\].
|-valign="top"
|||''SaveFileBefore''||Name of a file to save the MILPSOLVE object before presolve. The name must be  of type string (char), Example: Prob.MILPSOLVE.SaveFileBefore = 'save1'. If the type  is not char SaveFileBefore is set to save1.\[file extension\].
|-
|||''SaveMode''||1 - LP - MILPSOLVE  LP format
|-
|||||2 - MPS - MPS format
|-
|||||3 - FMPS - Free MPS format
|-
|||||If empty, the default format LP is used.
|-valign="top"
|||''SCALE_LIMIT''||Sets the relative  scaling convergence  criterion  to  the  absolute value of SCALE_LIMIT for the active scaling mode. The integer part of SCALE_LIMIT specifies the maximum number of iterations. Default is 5.
|-
|||''SCALING_ALG''||Specifies which scaling algorithm will be used by MILPSOLVE.
|-
|||||0 No scaling algorithm
|-
|||||1 (SCALE EXTREME) Scale to convergence using largest absolute value
|-
|||||2 (SCALE RANGE) Scale based on the simple numerical range
|-
|||||3 (SCALE MEAN) Numerical range-based scaling
|-
|||||4 (SCALE GEOMETRIC) Geometric scaling
|-
|||||7 (SCALE CURTISREID) Curtis-reid scaling
|-
|||||Default is 0, no scaling algorithm.
|-valign="top"
|||''SCALING_ADD''||Vector containing possible additional scaling parameters. If the length (i) of the vector is less than 7 elements, only the i first modes are considered. Also if i is longer than 7 elements, the elements after element 7 is ignored. SCALING ADD ! = 0 (SCALE_QUADRATIC)
|-
|||||SCALING ADD ! = 0 (SCALE_LOGARITHMIC) Scale to convergence using logarithmic mean of all values
|-
|||||SCALING_ADD  !  = 0  (SCALE_USERWEIGHT) User can specify scalars
|-
|||||SCALING_ADD ! = 0 (SCALE_POWER2) also do Power scaling
|-
|||||SCALING_ADD  ! = 0 (SCALE_EQUILIBRATE) Make  sure that  no scaled number is above 1
|-
|||||SCALING_ADD ! = 0 (SCALE_INTEGERS) Also scaling integer vari- ables
|-
|||||SCALING_ADD ! = 0 (SCALE_DYNUPDATE) Dynamic update
|-
|||||Default is 0, no additional mode.
|-
|||||Settings SCALE_DYNUPDATE is a way to make sure that scaling factors are recomputed. In that case, the scaling factors are recomputed also when a restart is done.
|-
|||''SIMPLEX_TYPE''||Sets the desired combination of primal and dual simplex algorithms.
|-
|||||5 (SIMPLEX_PRIMAL_PRIMAL) Phase1 Primal, Phase2 Primal
|-
|||||6 (SIMPLEX_DUAL_PRIMAL) Phase1 Dual, Phase2 Primal
|-
|||||9 (SIMPLEX_PRIMAL_DUAL) Phase1 Primal, Phase2 Dual
|-
|||||10 (SIMPLEX_DUAL_DUAL) Phase1 Dual, Phase2 Dual
|-
|||||Default is SIMPLEX DUAL PRIMAL (6).
|-valign="top"
|||''SOLUTION_LIMIT''||Sets the solution number that will be returned. This value is only consid- ered if there are integer, semi-continuous or SOS variables in the model so that the branch-and-bound algorithm is used. If there are more solutions with the same objective value, then this number specifies which solution must be returned. Default is 1.
|-
|||''sos''||List of structs containing data about Special Ordered Sets (SOS). See below for further description.
|-
|colspan="3"|Fields used in '''Prob.MIP '''(Structure with MIP specific parameters)
|-
|||''IntVars''||Defines which variables are integers, of general type I or binary type B Variable indices should be in the range \[1,...,n\].
|-
|||||IntVars is a logical vector ==''> x''(''f ind''(''I ntV ars > ''0)) are integers
|-
|||||IntVars is a vector of indices ==''> x''(''I ntV ars'') are integers (if \[\], then no integers of type I or B are defined) variables with x L=0 and x U=1, is are set to binary. It is possible to combine integer and semi-continuous type to obtain the semi-integer type.
|-valign="top"
|||''fIP''||This parameter specifies the initial "at least better than" guess for objective function. This is only used in the branch-and-bound algorithm when integer variables exist in the model. All solutions with a worse objective value than this value are immediately rejected. The default is infinity.
|-valign=top"
|||''SC''||A vector with indices for variables of type semi-continuous (SC), a logical vector or a scalar (see MIP.IntVars). A semi-continuous variable i takes either the value 0 or some value in the range \[x L(i), x U(i)\].  It is possible to combine integer and semi-continuous type to obtain the semi-integer type.
|-valign="top"
|||''sos1''||List of structures defining the Special Ordered Sets of Order One (SOS1). For SOS1 set k, sos1(k).var is a vector of indices for variables of type SOS1 in set k, sos1(k).row is the priority  of SOS k in the set of SOS1 and sos1(k).weight is a vector of the same length as sos1(k).var and it describes the order MILPSOLVE  will weight the variables in SOS1 set k.
|-
|||||a low number of a row and a weight means high priority.
|-
|||''sos2''||List of n structures defining the Special Ordered Sets (SOS) of Order Two (SOS2). (see MIP.sos1)
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed:
|-
|||''x_k''||Optimal  solution (or some other solution if optimum could not been found)
|-
|||''f_k''||Optimal objective value.
|-
|||''v_k''||\[rc; duals\]. If Reduced cost and dual variables are not available, then v_k is empty.
|-
|||''ExitFlag''||TOMLAB information parameter.
|-
|||||0 = Optimal solution found.
|-
|||||1 = Suboptimal solution or user abort.
|-
|||||2 = Unbounded solution.
|-
|||||3 = Numerical failure.
|-
|||||4 = Infeasible model.
|-
|||||10 = Out of memory.
|-
|||||11 = Branch and bound stopped.
|-
|||''ExitText''||Status text from MILPSOLVE.
|-
|||''Inform''||MILPSOLVE  information parameter.
|-
|||||-2 = Out of memory.
|-
|||||0 = Optimal solution found.
|-
|||||1 = Suboptimal solution.
|-
|||||2 = Infeasible model.
|-
|||||3 = Unbounded solution.
|-
|||||4 = Degenerate solution.
|-
|||||5 = Numerical failure.
|-
|||||6 = User abort.
|-
|||||7 = Timeout.
|-
|||||10 = Branch and bound failed.
|-
|||||11 = Branch and bound stopped.
|-
|||||12 = Feasible branch and bound solution.
|-
|||||13 = No feasible branch and bound solution. Other = Unknown status.
|-valign="top"
|||''Iter''||The total  number of nodes processed in the branch-and-bound algorithm. Is only applicable if the model contains integer variables. In the case of an LP model Result.Iter contains the number of iterations. This is however not documented.
|-
|||''MinorIter''||The total number of Branch-and-bound iterations. When the problem is LP, MinorIter equals Result.Iter
|-
|||''MILPSOLVE.basis''||Optimal basis, on the format described above under Prob.MILPSOLVE.basis.
|-
|||''MILPSOLVE.MaxLevel''||The deepest Branch-and-bound  level of the last solution. Is only applicable if the model contains integer variables.
|-
|||''MILPSOLVE.sa.objStatus''||1 successful
|-
|||||0 SA not requested
|-
|||||-1 Error: error from MILPSOLVE
|-
|||||-3 no SA available
|-
|||''MILPSOLVE.sa.ObjLower''||An array that  will  contain the values of the lower limits  on the objective function.
|-
|||''MILPSOLVE.sa.ObjUpper''||An array that will contain the values of the upper limits on the objective function.
|-
|||''MILPSOLVE.sa.RhsStatus''||see MILPSOLVE.sa.objStatus.
|-
|||''MILPSOLVE.sa.RhsLower''||An array that will contain the values of the lower limits on the RHS.
|-
|||''MILPSOLVE.sa.RhsUpper''||An array that will contain the values of the upper limits on the RHS.
|-
|||''xState''||State of each variable
|-
|||||0 - free variable,
|-
|||||1 - variable on lower bound,
|-
|||||2 - variable on upper bound,
|-
|||||3 - variable is fixed, lower bound = upper bound.
|-
|||''bState''||State of each linear constraint
|-
|||||0 - Inactive constraint,
|-
|||||1 - Linear constraint on lower bound,
|-
|||||2 - Linear constraint on upper bound,
|-
|||||3 - Linear equality constraint.
|}
 
====minlpSolve====
 
'''Purpose'''


Branch & Bound algorithm for Mixed-Integer Nonlinear Programming (MINLP) with convex or nonconvex sub problems using NLP relaxation (Formulated as minlp-IP).  
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]]
 
minlpSolve depends on a suitable NLP solver.
 
''minlpSolve ''solves problems of the form
 
 
<math>
\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}
</math>
 
 
where <math>x,x_{L},x_{U}\in \MATHSET{R}^{n}</math> , <math>c(x),c_{L},c_{U}\in
\MATHSET{R}^{m_{1}}</math> , <math>A\in \MATHSET{R}^{m_{2}\times n}</math> and
<math>b_{L},b_{U}\in \MATHSET{R}^{m_{2}}</math>. The variables <math>x \in I</math> , the
index subset of <math>1,...,n</math> are restricted to be integers.
 
'''Calling  Syntax'''
 
Result = tomRun('minlpSolve',Prob,...)
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|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.
|-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.
|-
|||''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
|-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.
|--valign="top"
|||''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
|-valign="top"
|||''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:
|-valign="top"
|||''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.
|-valign="top"
|||''VarWeight''||Weight for each variable in the variable selection phase. A lower value gives higher priority.  Setting Prob.MIP.VarWeight might improve convergence.
|-valign="top"
|||''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"
|||''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.
|-valign="top"
|||''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
|-valign="top"
|||''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''||colspan="2"|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.
|-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
|-
|||''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.
|-valign="top"
|||''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);
==mipSolve==
 
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);
 
====mipSolve====
 
'''Purpose'''


Solve mixed integer linear programming problems (MIP).
Solve mixed integer linear programming problems (MIP).


''mipSolve ''solves problems of the form
*[[mipSolve]]


==multiMin==


<math>
multiMin solves general constrained mixed-integer global optimization problems. It tries to find all local minima by a multi-start method using a suitable nonlinear programming subsolver.
\begin{array}{cccccc}
\min\limits_{x} & f(x) & = & c^{T}x & \\s/t & x_{L} & \leq  & x  & \leq & x_{U} \\& b_{L} & \leq  & Ax & \leq & b_{U} \\ &      &      & \multicolumn{3}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \in $I$}  \\
\end{array}
</math>


*[[multiMin]]


where <math>c, x, x_L, x_U \in \MATHSET{R}^{n}</math> , <math>A\in \MATHSET{R}^{m\times n}</math> and <math>b_L, b_U \in\MATHSET{R}^{m}</math>.The variables <math>x \in I</math> , the index subset of <math>1,...,n</math> are restricted to beintegers.
==multiMINLP==


Starting with TOMLAB version 4.0, ''mipSolve ''accepts upper and lower bounds on the linear constraints like most other TOMLAB  solvers. Thus it is no longer necessary to use slack variables to handle inequality constraints.
multiMINLP solves general constrained mixed-integer global nonlinear optimization problems.


'''Calling  Syntax'''
*[[multiMINLP]]


Result = tomRun('mipSolve',Prob,...)
==nlpSolve==


'''Description  of Inputs'''
Solve general constrained nonlinear optimization problems.


{|
*[[nlpSolve]]
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''c''||The vector ''c ''in <math>c^{T}x</math>.
|-
|||''A ''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints. If empty, ''Prob.b U ''is used.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''x_L''||Lower bounds on the variables.
|-
|||''x_U''||Upper bounds on the variables.
|-
|||''x_0''||Starting point.
|-valign="top"
|||''MaxCPU''||Maximal CPU Time (in seconds) to be used by mipSolve, stops with best point found.
|-
|||''QP.B''||Active set ''B 0 ''at start:
|-
|||||''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set.
|-
|||||''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound.
|-
|||||''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound.
|-valign="top"
|||''SolverLP''||Name of solver used for initial  LP subproblem. Default solver is used if empty, see ''GetSolver.m ''and ''tomSolve.m''.
|-valign="top"
|||''SolverDLP''||Name of solver used for the dual LP subproblems. Default  solver is used if empty, see ''GetSolver.m ''and ''tomSolve.m''.
|-
|||''PriLevOpt ''||Print level in ''lpSimplex ''and ''DualSolve'':
|-
|||||0: No output; ''> ''0: Convergence result;
|-
|||||''> ''1: Output every iteration; ''> ''2: Output each step in simplex algorithm.
|-
|||''PriLev''||Print level in ''mipSolve''.
|-
|||''SOL.optPar''||Parameters for the SOL solvers, if they are used as subsolvers.
|-
|||''SOL.PrintFile''||Name of print file for SOL solvers, if they are used as subsolvers.
|-
|||''MIP''||Structure with fields for integer optimization The following fields are used:
|-
|||''IntVars''||The set of integer variables.
|-
|||||If empty, all variables are assumed non-integer (LP problem)
|-
|||''VarWeight''||Weight for each variable in the variable selection phase.
|-
|||||A lower value gives higher priority. Setting ''Prob.MIP.VarWeight  ''= ''Prob.c'' improves convergence for knapsack problems.
|-
|||''DualGap''||''mipSolve ''stops if the duality  gap is less than ''DualGap''. To stop at the first found integer solution, set ''DualGap ''=1. For example, ''DualGap ''= 0.01 makes the algorithm stop if the solution is ''< ''1% from the optimal solution.
|-
|||''fIP''||An upper bound on the IP value wanted.  Makes it possible to cut branches and avoid node computations.
|-
|||''xIP''||The ''x''-value giving the ''fIP ''value.
|-
|||''KNAPSACK''||If solving a knapsack problem, set to true (1) to use a knapsack heuristic.
|-
|||''optParam''||Structure with special fields for optimization parameters, see Table 141.Fields used are: ''IterPrint'', ''MaxIter'', ''PriLev'', ''wait'', ''eps f ''and ''eps Rank''.
|-
|||''Solver''||Structure with fields for algorithm choices:
|-
|||''Alg''||Node selection method:
|-
|||||0: Depth first
|-
|||||1: Breadth first
|-
|||||2: Depth first. When integer solution found, switch to Breadth.
|-
|||''method''||Rule to select new variables in DualSolve/lpSimplex:
|-
|||||0: Minimum reduced cost, sort variables increasing. (Default)
|-
|||||1: Bland's rule (default).
|-
|||||2: Minimum reduced cost. Dantzig's rule.
|}


'''Description  of Outputs'''
==pdcoTL==


{|
''pdcoTL ''solves linearly constrained convex nonlinear optimization problems.
|-valign"top"
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed:
|-
|||''x_k''||Optimal point.
|-
|||''f_k''||Function value at optimum.
|-
|||''g_k''||Gradient value at optimum, ''c''.
|-
|||''v_k''||Lagrange multipliers, \[Constraints + lower + upper bounds\].
|-
|||''x_0''||Starting point.
|-
|||''f_0''||Function value at start.
|-
|||''xState''||State of each variable, described in Table 150, page 239.
|-
|||''Inform''||If ''ExitF lag > ''0, ''I nf orm ''= ''ExitF lag''.
|-
|||''QP.B''||Optimal active set. See input variable ''QP.B''.
|-
|||''QP.y''||Dual parameters ''y ''(also part of ''Result.v_k''.
|-
|||''p_dx''||Search steps in ''x''.
|-
|||''alphaV''||Step lengths for each search step.
|-
|||''ExitFlag''||0: OK.
|-
|||||1: Maximal number of iterations reached.
|-
|||||2: Empty feasible set, no integer solution found.
|-
|||||3: Rank problems. Can not find any solution point.
|-
|||||4: No feasible point found running LP relaxation.
|-
|||||5: Illegal''x_0 ''found in LP relaxation.
|-
|||||99: Maximal CPU Time used (cputime ''> ''Prob.MaxCPU).
|-
|||''Iter''||Number of iterations.
|-
|||''Solver''||Solver used ('mipSolve').
|-
|||''SolverAlgorithm''||Text description of solver algorithm used.
|-
|||''Prob''||Problem structure used.
|}


'''Description'''
*[[pdcoTL]]


The routine ''mipSolve ''is an implementation of a branch and bound algorithm from Nemhauser and Wolsey \[58, chap.  8.2\].  ''mipSolve ''normally uses the linear programming routines ''lpSimplex ''and ''DualSolve ''to solve relaxed subproblems. ''mipSolve ''calls the general interface routines ''SolveLP ''and ''SolveDLP''. By changing the setting of the structure fields ''Prob.Solver.SolverLP ''and ''Prob.Solver.SolverDLP'', different sub-solvers are possible to use, see the help for the interface routines.
==pdscoTL==


'''Algorithm'''
''pdscoTL'' solves linearly constrained convex nonlinear optimization problems.


See \[58, chap. 8.2\] and the code in ''mipSolve.m''.
*[[pdscoTL]]


'''Examples'''
==qpSolve==


See ''exip39'',  ''exknap'', ''expkorv''.
Solve general quadratic programming problems.


'''M-files  Used'''
*[[qpSolve]]


''lpSimplex.m'', ''DualSolve.m'', ''GetSolver.m'', ''tomSolve.m''
==slsSolve==


'''See Also'''
Find a Sparse Least Squares (sls) solution to a constrained least squares problem with  the use of any suitable TOMLAB  NLP solver.


''cutplane'', ''balas'', ''SolveLP'', ''SolveDLP''
*[[slsSolve]]


====multiMin====
==sTrustr==
 
'''Purpose'''
 
multiMin  solves general constrained  mixed-integer global optimization problems. It tries to find all local minima by a multi-start  method using a suitable nonlinear programming subsolver.
 
''multiMin  ''solves problems of the form
 
 
<math>
\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}{c}{x_i \in \MATHSET{N} \; \forall i \in I} \\
\end{array}
</math>
 
where <math>x,x_{L},x_{U}\in \MATHSET{R}^{n}</math> , <math>c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}</math> , <math>A\in \MATHSET{R}^{m_{2}\times n}</math> and <math>b_{L},b_{U}\in \MATHSET{R}^{m_{2}}</math>.
 
The variables <math>x \in I</math> , the index subset of <math>1,...,n</math> are restricted to be integers.
 
The integer components of every x_0 is rounded to the nearest integer value inside simple bounds, and these components are fixed during the nonlinear local search.
 
If generating random points and there are linear constraints, multiMin  checks feasibility with respect to the linear constraints, and for each initial  point tries 100 times to get linear feasibility before accepting the initial  point.
 
'''Calling  Syntax'''
 
Result = multiMin(Prob, xInit)
 
Result = tomRun('multiMin', Prob, PriLev) (driver call)
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|''xInit''||colspan="2"|Either, 1x1 number - The number of random initial  points, default 10\*Prob.N dxm matrix - Every column is an initial  point (of length d=Prob.N). May also be set as Prob.xInit.
|-
|||''fCut''||If initial  f(x_0) ''> ''fCut, no local optimization is done.
|-valign="top"
|||''WarmStart''||If true, ''> ''0, multiMin assumes the field multiMin  defined with the output from a previous run on the same problem. See the Output fields of Result.multiMin. Use WarmDefGLOBAL  to set the correct fields in the Prob structure.  Nec- essary fields are fOpt and xOpt. If any of the other fields are missing, the corresponding variables are initialized to 0. These other fields are: localTry, Iter, FuncEv, GradEv, HessEv, ConstrEv Inform (is set to zeros(length(fOpt,1) if not defined).
|-
|||||In WarmDefGLOBAL the Result structure for the optimal run will be fed back to multiMin  as Prob.multiMin.ResOpt In case this field is not defined, and no better point is found during the runs, a special call to the localSolver is used to generate a proper Result structure.
|-valign="top"
|||''RandState''||If ''WarmStart ''and isscalar(xInit), 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
|-valign="top"
|||''xEqTol''||Tolerance to test if new point  x_k already defined as optimum: ''norm(xk - xOpt(:, i))'' <= ''xEqTol * max(1, norm(xk))'' If test fulfilled x_k is assumed to be too close to xOpt(:,i) Default xEqTol = 1E-5
|-
|||''x_L''||Lower bounds for each element in x. If generating random points, -inf elements of x L are set to -10000.
|-valign="top"
|||''x_U''||Upper bounds for each element in x. If generating random points, inf elements of x U are set to 10000.
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''c_L''||Lower bounds on the general constraints.
|-
|||''c_U''||Upper bounds on the general constraints.
|-
|||''PriLevOpt''||0 = silent.
|-
|||||1 = Display one row for each unique local minima found. The minima are sorted, lowest value first (possibly the global minima)
|-
|||||The following 4 information values are displayed:
|-
|||||1. Order \#
|-
|||||2. Function value f(x) at local minima
|-
|||||3. Point x at local minima. Only up to 10 values are displayed
|-
|||||4. Inform value returned from local Solver (normally 0)
|-
|||||2 = One row of output from each multiMin  local optimization trial
|-
|||||The following 6 information values are displayed:
|-
|||||1. Step \#
|-
|||||2. Text Old (previously found local minima), FAIL (solver failed to verify local minima) or blank (solver success, new local minima found)
|-
|||||3. Inform value from local solver
|-
|||||4. f(x_0) - function value f(x_0) for initial  x_0
|-
|||||5. f(x) - best f(x) value found in this local search
|-
|||||6. x - point for which best f(x) value was found in this local search. Only up to 10 values are displayed.
|-
3 = tomRun (PrintResult)  output from every optimization, print level 1.
|-
|||||4 = tomRun (PrintResult)  output from every optimization, print level 2. For constrained problems output  of sum(-constr-) and information if optimal point was accepted w.r.t.  feasibility.
|-
|||||5 = tomRun (PrintResult)  output from every optimization, print level 3.
|-
|||''GO''||Structure in ''Prob'', ''Prob.GO''. Fields used:
|-valign="top"
|||''localSolver''||The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0).
|-
|||''optParam''||Defines optimization parameters. Fields used:
|-valign="top"
|||''fGoal''||Goal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done.
|-
|||''eps_f''||Relative accuracy for function value, fTol == eps_f. Stop if abs(f-fGoal) ''<''= abs(fGoal) \* fTol , if fGoal  = 0. Stop if abs(f-fGoal) ''<''= fTol , if fGoal ==0.
|-valign="top"
|||''bTol''||The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0).
|-valign="top"
|||''MIP.IntVars''||Structure in Prob, Prob.MIP. If empty, all variables are assumed non-integer (LP problem). If ''length''(''I ntV ars'') ''> ''1 ==''> length''(''I ntV ars'') == ''length''(''c'') should hold.  Then ''I ntV ars''(''i'')  == 1 ==''> x''(''i'')  integer. ''I ntV ars''(''i'')  == 0 ==''> x''(''i'')  real.  If  ''length''(''I ntV ars'')  ''< n'', IntVars  is assumed to be a set of indices.  It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
|-
|''varargin''||colspan="2"|Other parameters directly sent to low level routines.
|}
 
'''Description  of Outputs'''
 
{|
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed:
|-
|||colspan="2"|The following fields in Result are changed by multiMin  before return:
|-
|||''ExitFlag''||= 0 normal output, of if fGoal set and found.
|-
|||||= 1 A solution reaching the user defined fGoal was not found
|-
|||colspan="2"|The Solver, SolverAlgorithm and ExitText  fields are also reset.
|-
|||colspan="2"|A special field in Result is also returned, Result.multiMin:
|-valign="top"
|||''xOpt''||Prob.N x k matrix with k distinct local optima, the test being ''norm''(''xk -xOpt''(:'', i'')) ''<''= ''xEqT ol * max''(1'', norm''(''xk '')) that if fulfilled assumes x k to be to closeto xOpt(:,i)
|-
|||''fOpt''||The k function values in the local optima xOpt(:,i),i=1,...,k.
|-valign="top"
|||''Inform''||The Inform value returned by the local solver when finding each of the local optima xOpt(:,i);  i=1,...,k. The Inform value can be used to judge the validity of the local minimum reported.
|-
|||''localTry''||Total number of local searches.
|-
|||''Iter''||Total number of iterations.
|-
|||''FuncEv''||Total number of function evaluations.
|-
|||''GradEv''||Total number of gradient evaluations.
|-
|||''HessEv''||Total number of Hessian evaluations.
|-
|||''ConstrEv''||Total number of constraint function evaluations.
|-
|||''ExitText''||Text string giving ExitFlag and Inform information.
|}
 
====multiMINLP====
 
'''Purpose'''
 
multiMINLP solves general constrained  mixed-integer global nonlinear optimization problems.
 
It is aimed for problems where the number of integer combinations nMax is huge and relaxation of the integer constraint is possible.
 
If no integer variables, multiMINLP calls multiMin. If nMax ''<''= min(Prob.optParam.MaxFunc,5000), glcDirect is used. Otherwise, multiMINLP first finds a set M of local minima calling multiMin  with no integer restriction on any variable. The best local minimum is selected.  glcDirect is called to find the best integer feasible solution fIP in a small area (''< ''+- 2 units) around the best local minimum found.
 
The other local minima are pruned, if fOpt(i) ''> ''fIP, no integer feasible solution could be found close to this local minimum i.
 
The area close to the remaining candidate local minima are searched one by one by calling glcDirect to find any fIPi ''< ''fIP.
 
''multiMINLP ''solves problems of the form
 
 
<math>
\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}
</math>
 
where <math>x,x_{L},x_{U}\in \MATHSET{R}^{n}</math> , <math>c(x),c_{L},c_{U}\in
\MATHSET{R}^{m_{1}}</math> , <math> A\in \MATHSET{R}^{m_{2}\times n}</math> and
<math>b_{L},b_{U}\in \MATHSET{R}^{m_{2}}</math> . The variables <math>x \in I</math> , the index subset of <math>1,...,n</math> are restricted to be integers.
 
'''Calling  Syntax'''
 
Result = tomRun('multiMINLP',Prob,...)
 
'''Description  of Inputs'''
 
{|
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||||Prob is a structure, defined  as to solve a standard MINLP  problem. The Prob structure is fed to the localSolver. See e.g. minlpAssign.
|-
|||||See multiMin  and glcDirect for input to the subsolvers e.g. Prob.xInit is used in multiMin (and fCut, RandState, xEQTol).
|-valign="top"
|||''x_L''||Lower bounds for each element in x. If generating random points, -inf elements of x L are set to min(-L,xMin,x  U-L) xMin is the minimum of the finite x L values.
|-valign="top"
|||''x_U''||Upper bounds for each element in x. If generating random points, inf elements of x U are set to max(L,xMax,x L+L) xMax is the maximum of the finite x U values.
|-
|||||L is 100 for nonlinear least squares, otherwise 1000.
|-
|||''b_L''||Lower bounds on linear constraints.
|-
|||''b_U''||Upper bounds on linear constraints.
|-
|||''A''||The linear constraint matrix.
|-
|||''c_L''||Lower bounds on nonlinear constraints.
|-
|||''c_U''||Upper bounds on nonlinear constraints.
|-
|||''PriLev''||Print Level:
|-
|||||0 = Silent
|-
|||||1 = Display 2 summary rows
|-
|||||2 = Display some extra summary rows
|-
|||||5 = Print level 1 in tomRun call
|-
|||||6 = Print level 2 in tomRun call
|-
|||||7 = Print level 3 in tomRun call
|-
|||''xInit''||Used in multiMin. See help for multiMin.
|-valign="top"
|||''GO.localSolver ''||The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0).
|-valign="top"
|||''optParam''||Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
|-
|||''MaxFunc''||Max number of function evaluations in each subproblem
|-
|||''fGoal''||Goal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done
|-valign="top"
|||''eps_f''||Relative accuracy for function value, fTol == eps_f.  Stop if abs(f-fGoal) ''<''= abs(fGoal) \* fTol , if fGoal = 0. Stop if abs(f-fGoal) ''<''= fTol , if fGoal ==0. Default 1e-8.
|-
|||''bTol''||Linear constraint feasibility tolerance. Default 1e-6
|-
|||''cTol''||Nonlinear constraint feasibility tolerance. Default 1e-6
|-valign="top"
|||''MIP''||Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used:
|-valign="top"
|||''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.
|-
|||''nMax''||Number of integer combinations possible, if  empty multiMINLP computes nMax.
|-
|||''Rfac''||Reduction factor for real variables in MINLP  subproblem  close to local multiMINLP minimum. Bounds set to x_L = max(x_L,x-Rfac\*(x_U-x_L)) and x_U= min(x_U,x+Rfac\*(x_U-x_L)). Default 0.25.
|}
 
'''Description  of Outputs'''
{|
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed:
|-
|||||Result structure from the last good optimization step giving the best f(x) value, the possible global MINLP  minimum.
|-
|||||The following fields in Result are changed by multiMINLP before return:
|-
|||''ExitFlag''||= 0 normal output, of if fGoal set and found.
|-
|||||= 1 A solution reaching the user defined fGoal was not found.
|-
|||||= 2 Unbounded problem.
|-
|||||=4 Infeasible problem.
|-
|||||The Solver, SolverAlgorithm and ExitText fields are also reset.
|-
|||||A special field in Result is also returned, Result.multiMINLP:
|-
|||''xOpt''||Prob.N x k matrix with k distinct  local optima, the test being norm(x k- xOpt(:,i)) ''<''= xEqTol\*max(1,norm(x k)) that if fulfilled assumes x_k to be to close to xOpt(:,i).
|-
|||''fOpt''||The k function values in the local optima xOpt(:,i),i=1,...,k.
|-
|||''Inform''||The Inform value returned by the local solver when finding each of the local optima xOpt(:,i);  i=1,...,k.  The Inform value can be used to judge the validity of the local minimum reported.
|-
|||''localTry''||Total number of local searches.
|-
|||''Iter''||Total number of iterations.
|-
|||''FuncEv''||Total number of function evaluations.
|-
|||''GradEv''||Total number of gradient evaluations.
|-
|||''HessEv''||Total number of Hessian evaluations.
|-
|||''ConstrEv''||Total number of constraint function evaluations.
|-
|||''ExitText''||Text string giving Inform information.
|}
 
====nlpSolve====
 
'''Purpose'''
 
Solve general constrained nonlinear optimization problems.


''nlpSolve ''solves problems of the form
Solve optimization problems constrained by a convex feasible region.


*[[sTrustr]]


<math>
==Tfmin==
\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}
\end{array}
</math>


Minimize function of one variable. Find miniumum x in [x_L, x_U] for function Func within tolerance xTol.  Solves using Brents minimization algorithm.


where <math>x,x_{L},x_{U}\in \MATHSET{R}^{n}</math> , <math>c(x),c_{L},c_{U}\in \MATHSET{R} ^{m_{1}}</math> , <math>A\in \MATHSET{R}^{m_{2}\times n}</math> and <math>b_{L},b_{U}\in \MATHSET{R}^{m_{2}}</math>.
*[[Tfmin]]


'''Calling  Syntax'''
==Tfzero==


Result = nlpSolve(Prob, varargin)
Tfzero, TOMLAB  fzero routine.


Result = tomRun('nlpSolve', Prob);
*[[Tfzero]]


'''Description  of Inputs'''
==ucSolve==


{|
Solve unconstrained  nonlinear optimization problems with simple bounds on the variables.
|''Prob''||colspan="2"|Problem description structure. The following fields are used:
|-
|||''A''||Constraint matrix for linear constraints.
|-
|||''b_L''||Lower bounds on the linear constraints.
|-
|||''b_U''||Upper bounds on the linear constraints.
|-
|||''c_L''||Lower bounds on the general constraints.
|-
|||''c_U''||Upper bounds on the general constraints.
|-
|||''x_L''||Lower bounds on the variables.
|-
|||''x_U''||Upper bounds on the variables.
|-
|||''x_0''||Starting point.
|-valign="top"
|||''PriLevOpt''||Print level: 0 Silent, 1 Final result, 2 Each iteration, short, 3 Each iteration, more info, 4 Matrix  update information.
|-
|||''FUNCS.f''||Name of m-file computing the objective function ''f ''(''x'').
|-
|||''FUNCS.g''||Name of m-file computing the gradient vector ''g''(''x'').
|-
|||''FUNCS.H''||Name of m-file computing the Hessian matrix ''H ''(''x'').
|-
|||''FUNCS.c''||Name of m-file computing the vector of constraint functions ''c''(''x'').
|-
||||''FUNCS.dc''||Name of m-file computing the matrix of constraint normals ''?c''(''x'')''/dx''.
|-valign="top"
|||''FUNCS.d2c''||Name of m-file computing the second derivatives of the constraints, weighted by an input Lagrange vector
|-
|||''NumDiff''||How to obtain derivatives (gradient, Hessian).
|-
|||''ConsDiff''||How to obtain the constraint derivative matrix.
|-
|||''SolverQP''||Name of the solver used for QP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m.
|-
|||''SolverFP''||Name of the solver used for FP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m.
|-
|||''optParam''||Structure with special fields for optimization parameters,  see Table 141.
|-
|||||Fields used are: ''eps_g'', ''eps_x'', ''MaxIter'', ''wait'', ''size_x'', ''method'', ''IterPrint'', ''xTol'', ''bTol'', ''cTol'', and ''QN InitMatrix''.
|-
|''varargin''||colspan="2"|Other parameters directly sent to low level routines.
|}


'''Description  of Outputs'''
*[[ucSolve]]


{|
==Additional solvers==
|''Result''||colspan="2"|Structure with result from optimization. The following fields are changed:
|-
|||''x_k''||Optimal point.
|-
|||''f_k''||Function value at optimum.
|-
|||''g_k''||Gradient value at optimum.
|-
|||''c_k''||Value of constraints at optimum.
|-
|||''H_k''||Hessian value at optimum.
|-
|||''v_k''||Lagrange multipliers.
|-
|||''x_0''||Starting point.
|-
|||''f_0''||Function value at start.
|-
|||''cJac''||Constraint Jacobian at optimum.
|-
|||''xState''||State of each variable, described in Table 150.
|-
|||''bState''||State of each linear constraint, described in Table 151.
|-
|||''cState''||State of each general constraint.
|-
|||''Inform''||Type of convergence.
|-
|||''ExitFlag''||Flag giving exit status.
|-
|||''ExitText''||0: Convergence. Small step. Constraints fulfilled.
|-
|||||1: Infeasible problem?
|-
|||||2: Maximal number of iterations reached.
|-
|||||3: No progress in either function value or constraint reduction.
|-
|||''Inform''||1: Iteration points are close.
|-
|||||2: Small search direction
|-
|||||3: Function value below given estimate. Restart with lower fLow if minimum not reached.
|-
|||||4: Projected gradient small.
|-
|||||10: Karush-Kuhn-Tucker conditions fulfilled.
|-
|||''Iter''||Number of iterations.
|-
|||''Solver''||Solver used.
|-
|||''SolverAlgorithm''||Solver algorithm used.
|-
|||''Prob''||Problem structure used.
|}


'''Description'''
Documentation for the following solvers is only available at http://tomopt.com and in the m-file help.


The routine ''nlpSolve ''implements the Filter SQP by Roger Fletcher and Sven Leyffer presented in the paper \[21\].
*goalSolve - For sparse multi-objective goal attainment problems, with linear and nonlinear constraints.


'''M-files  Used'''
*Tlsqr - Solves large, sparse linear least squares problem, as well as unsymmetric linear systems.


''tomSolve.m'', ''ProbCheck.m'', ''iniSolve.m'', ''endSolve.m''
*lsei - For linearly constrained least squares problem with both equality and inequality constraints.


'''See Also'''
*Tnnls - Also for linearly constrained least squares problem with both equality and inequality constraints.


''conSolve'', ''sTrustr''
*qld - For convex quadratic programming problem.

Latest revision as of 13:30, 17 July 2011

Notice.png

This page is part of the TOMLAB Manual. See TOMLAB Manual.

Detailed descriptions of the TOMLAB solvers, driver routines and some utilities are given in the following sections. Also see the M-file help for each solver. All solvers except for the TOMLAB Base Module are described in separate manuals.

For a description of solvers called using the MEX-file interface, see the M-file help, e.g. for the MINOS solver minosTL.m. For more details, see the User's Guide for the particular solver.

clsSolve

Solves dense and sparse nonlinear least squares optimization problems with linear inequality and equality con- straints and simple bounds on the variables.

conSolve

Solve general constrained nonlinear optimization problems.

cutPlane

Solve mixed integer linear programming problems (MIP).

DualSolve

Solve linear programming problems when a dual feasible solution is available.

expSolve

Solve exponential fitting problems for given number of terms p.

glbDirect

Solve box-bounded global optimization problems.

glbSolve

Solve box-bounded global optimization problems.

glcCluster

Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.

glcDirect

Solve global mixed-integer nonlinear programming problems.

glcSolve

Solve general constrained mixed-integer global optimization problems.

infLinSolve

Finds a linearly constrained minimax solution of a function of several variables with the use of any suitable TOMLAB solver. The decision variables may be binary or integer.

infSolve

Find a constrained minimax solution with the use of any suitable TOMLAB solver.

linRatSolve

Finds a linearly constrained solution of a function of the ratio of two linear functions with the use of any suitable TOMLAB solver. Binary and integer variables are not supported.

lpSimplex

Solve general linear programming problems.

L1Solve

Find a constrained L1 solution of a function of several variables with the use of any suitable nonlinear TOMLAB solver.

MilpSolve

Solve mixed integer linear programming problems (MILP).

minlpSolve

Branch & Bound algorithm for Mixed-Integer Nonlinear Programming (MINLP) with convex or nonconvex sub problems using NLP relaxation (Formulated as minlp-IP).

mipSolve

Solve mixed integer linear programming problems (MIP).

multiMin

multiMin solves general constrained mixed-integer global optimization problems. It tries to find all local minima by a multi-start method using a suitable nonlinear programming subsolver.

multiMINLP

multiMINLP solves general constrained mixed-integer global nonlinear optimization problems.

nlpSolve

Solve general constrained nonlinear optimization problems.

pdcoTL

pdcoTL solves linearly constrained convex nonlinear optimization problems.

pdscoTL

pdscoTL solves linearly constrained convex nonlinear optimization problems.

qpSolve

Solve general quadratic programming problems.

slsSolve

Find a Sparse Least Squares (sls) solution to a constrained least squares problem with the use of any suitable TOMLAB NLP solver.

sTrustr

Solve optimization problems constrained by a convex feasible region.

Tfmin

Minimize function of one variable. Find miniumum x in [x_L, x_U] for function Func within tolerance xTol. Solves using Brents minimization algorithm.

Tfzero

Tfzero, TOMLAB fzero routine.

ucSolve

Solve unconstrained nonlinear optimization problems with simple bounds on the variables.

Additional solvers

Documentation for the following solvers is only available at http://tomopt.com and in the m-file help.

  • goalSolve - For sparse multi-objective goal attainment problems, with linear and nonlinear constraints.
  • Tlsqr - Solves large, sparse linear least squares problem, as well as unsymmetric linear systems.
  • lsei - For linearly constrained least squares problem with both equality and inequality constraints.
  • Tnnls - Also for linearly constrained least squares problem with both equality and inequality constraints.
  • qld - For convex quadratic programming problem.
Retrieved from "http://tomwiki.com/index.php?title=TOMLAB_Solver_Reference&oldid=615"