MINLP Solver Reference: Difference between revisions
No edit summary |
No edit summary |
||
Line 313: | Line 313: | ||
|} | |} | ||
===Description of Outputs | ===Description of Outputs=== | ||
''Result'', The following fields are used: | ''Result'', The following fields are used: |
Revision as of 06:42, 14 December 2011
This page is part of the MINLP Manual. See MINLP. |
The MINLP solvers are a set of Fortran solvers that were developed by Roger Fletcher and Sven Leyffer, Univer- sity of Dundee, Scotland. All solvers are available for sparse and dense continuous and mixed-integer quadratic programming (qp,miqp) and continuous and mixed-integer nonlinear constrained optimization.
<xr id="tab:solverRoutines" /> lists the solvers included in TOMLAB /MINLP. The solvers are called using a set of MEX-file interfaces developed as part of TOMLAB. All functionality of the MINLP solvers are available and changeable in the TOMLAB framework in Matlab.
Detailed descriptions of the TOMLAB /MINLP solvers are given in the following sections. Extensive TOMLAB m-file help is also available, for example help minlpBBTL in Matlab will display the features of the minlpBB solver using the TOMLAB format.
TOMLAB /MINLP package solves mixed-integer nonlinear programming (minlp) problem defined as
where , , , and . The variables , the index subset of , are restricted to be integers.
mixed-integer quadratic programming (miqp) problems defined as
where , , , and . The variables , the index subset of , are restricted to be integers.
as well as sub-types of these problems.
<figtable id="tab:solverRoutines">
Function | Description | Reference |
---|---|---|
bqpd | Quadratic programming using a null-space method. | bqpdTL.m |
miqpBB | Mixed-integer quadratic programming using bqpd as subsolver. | miqpBBTL.m |
filterSQP | Constrained nonlinear minimization using a Filtered Sequential QP method. | filterSQPTL.m |
minlpBB | Constrained, mixed-integer nonlinear minimization using a branch- and bound search scheme. filterSQP is used as NLP solver. | minlpBBTL.m |
</figtable>
bqpd
The BQPD code solves quadratic programming (minimization of a quadratic function subject to linear constraints) and linear programming problems. If the Hessian matrix Q is positive definite, then a global solution is found. A global solution is also found in the case of linear programming (Q=0). When Q is indefinite, a Kuhn-Tucker point that is usually a local solution is found.
The code implements a null-space active set method with a technique for resolving degeneracy that guarantees that cycling does not occur even when round-off errors are present. Feasibility is obtained by minimizing a sum of constraint violations. The Devex method for avoiding near-zero pivots is used to promote stability. The matrix algebra is implemented so that the algorithm can take advantage of sparse factors of the basis matrix. Factors of the reduced Hessian matrix are stored in a dense format, an approach that is most effective when the number of free variables is relatively small. The user must supply a subroutine to evaluate the Hessian matrix Q, so that sparsity in Q can be exploited. An extreme case occurs when Q=0 and the QP reduces to a linear program. The code is written to take maximum advantage of this situation, so that it also provides an efficient method for linear programming.
Direct Solver Call
A direct solver call is not recommended unless the user is 100 % sure that no other solvers will be used for the problem. Please refer to Section 3.1.2 for information on how to use bqpd with TOMLAB.
Purpose
bqpd solves quadratic optimization problems defined as
where , , , and .
Calling Syntax
[Inform, x k, Obj, g, Iter, k, ls, e, peq, lp, v k] = bqpds(A, x 0, bl, bu, H, fLowBnd, mlp, mode, kmax, PriLev, PrintFile, k, ls, e, peq, lp, optPar, Prob, moremem);
The sparse version MEX is bqpds, the dense is bqpdd.
Description of Inputs
The following fields are used:
Input | Description | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A | Constraint matrix, n x m+1 (SPARSE). | ||||||||||||||||
bl | Lower bounds on (x, Ax). | ||||||||||||||||
bu | Upper bounds on (x, Ax). | ||||||||||||||||
x_0 | Initial x vector (if empty set as 0). | ||||||||||||||||
H | Quadratic matrix, n x n, SPARSE or DENSE, empty if LP problem. If H is a string, H should be the name of a function routine, e.g if H = 'HxComp' then the function routine.
function Hx = HxComp(x, nState, Prob) should compute H * x. The user must define this routine nState == 1 if calling for the first time, otherwise 0. Third argument, the Prob structure, should only be used if calling BQPD with the additional input parameter Prob, see below. Tomlab implements this callback to the predefined Matlab function HxFunc.m, using the call if Prob.DUNDEE.callback == 1. | ||||||||||||||||
fLowBnd | Lower bound on optimal f(x). | ||||||||||||||||
mlp | Maximum number of levels of recursion. | ||||||||||||||||
mode | Mode of operation, default set as 2*Prob.WarmStart. | ||||||||||||||||
kmax | Max dimension of reduced space (k), default n, set as 0 if LP. | ||||||||||||||||
PriLev | Print Level. (0 = off, 1 = summary, 2 = scalar information, 3 = verbose) | ||||||||||||||||
PrintFile | Name of the Print file. Unit 9 is used. Name includes the path, maximal number of characters = 500. Output is written on file bqpd.txt, if not given. To make bqpd to not open and not write anything to file: Set PriLev = 0. | ||||||||||||||||
For Warm Start: | |||||||||||||||||
k | Dimension of the reduced space (Warm Start). | ||||||||||||||||
ls | Indices of active constraints, first n-k used for warm start. | ||||||||||||||||
e | Steepest-edge normalization coefficients (Warm Start). | ||||||||||||||||
peq | Pointer to the end of equality constraint indices in ls (Warm Start). | ||||||||||||||||
lp | List of pointers to recursion information in ls (Warm Start). | ||||||||||||||||
optPar | Vector of optimization parameters. If -999, set to default. Length from 0 to 20 allowed.
| ||||||||||||||||
Prob | Sending the Prob structure is optional, only of use if sending H as a function string, see input H. | ||||||||||||||||
moremem | Scalar or 2x1-vector with workspace increase. If <0, use default strategy. If scalar, use same increase for both real and integer workspaces. If vector, first element is for real workspace, second for integer. |
Description of Outputs
The following fields are used:
Output | Description |
---|---|
Inform | Result of BQPD run, 0 = Optimal solution found. See the same parameter in section 3.1.2. |
x_k | Solution vector with n decision variable values. |
Obj | Objective function value at optimum. If infeasible, the sum of infeasibilities |
g | Gradient at solution. |
Iter | Number of iterations. |
For Warm Start: | |
k | Dimension of the reduced space (Warm Start). |
ls | Indices of active constraints, first n-k used for warm start. |
e | Steepest-edge normalization coefficients (Warm Start). |
peq | Pointer to the end of equality constraint indices in ls (Warm Start). |
lp | List of pointers to recursion information in ls (Warm Start). |
v_k | Lagrange parameters. |
Using TOMLAB
Purpose
bqpdTL solves nonlinear optimization problems defined as
where , , , and .
Calling Syntax
Using the driver routine tomRun :
Prob = ''o''Assign( ... ); Result = tomRun('bqpd', Prob ... );
or
Prob = ProbCheck(Prob,'bpqd'); Result = bqpdTL(Prob);
Call Prob = oAssign( ... ) or Prob=ProbDef; to define the Prob for the second option.
Description of Inputs
Prob, The following fields are used:
Field | Description | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
x_L, x_U | Bounds on variables. | ||||||||||||||||
b_L, b_U | Bounds on linear constraints. | ||||||||||||||||
A | Linear constraint matrix. | ||||||||||||||||
QP.c | Linear coefficients in objective function. | ||||||||||||||||
QP.F | Quadratic matrix of size n x n. | ||||||||||||||||
PriLevOpt | Print Level (0 = off, 1 = summary, 2 = scalar information, 3 = verbose). | ||||||||||||||||
WarmStart | If TRUE (=1), use warm start, otherwise cold start. | ||||||||||||||||
LargeScale | If TRUE (=1), use sparse version, otherwise dense. | ||||||||||||||||
DUNDEE.QPmin | Lower bound for the QP subproblems. Default: -1E300. | ||||||||||||||||
DUNDEE.callback | If 1, use a callback to Matlab to compute QP.F * x for different x. Faster when F is very large and almost dense, avoiding copying of F from Matlab to MEX. | ||||||||||||||||
DUNDEE.kmax | Max dimension of reduced space (k), default n, set as 0 if LP. | ||||||||||||||||
DUNDEE.mlp | Maximum number of levels of recursion. | ||||||||||||||||
DUNDEE.mode | Mode of operation, default set as 2*Prob.WarmStart. | ||||||||||||||||
DUNDEE.x | Solution (Warm Start). | ||||||||||||||||
DUNDEE.k | Dimension of the reduced space (Warm Start). | ||||||||||||||||
DUNDEE.e | Steepest-edge normalization coefficients (Warm Start). | ||||||||||||||||
DUNDEE.ls | Indices of active constraints, first n-k used for warm start. | ||||||||||||||||
DUNDEE.lp | List of pointers to recursion information in ls (Warm Start). | ||||||||||||||||
DUNDEE.peq | Pointer to the end of equality constraint indices in ls (Warm Start). | ||||||||||||||||
DUNDEE.PrintFile | Name of print file. Amount/print type determined by optPar(1). Default name bqpd.txt. | ||||||||||||||||
DUNDEE.optPar | Vector of optimization parameters. If -999, set to default Length from 0 to 20 allowed. Elements used:
|
Description of Outputs
Result, The following fields are used:
Output | Description |
---|---|
Result | The structure with results (see ResultDef.m). |
f_k | Function value at optimum or constraint deviation if infeasible. |
x_k | Solution vector. |
x_0 | Initial solution vector. |
g_k | Exact gradient computed at optimum. |
xState | State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; |
bState | State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; |
v_k | Lagrangian multipliers (for bounds + dual solution vector). |
ExitFlag | Exit status from bqpd.m (similar to TOMLAB). |
Inform | BQPD information parameter.
0 - Solution obtained 1 - Unbounded problem detected (f(x)¡=fLow occurred) 2 - Lower bound bl(i) > bu(i) (upper bound) for some i 3 - Infeasible problem detected in Phase 1 4 - Incorrect setting of m, n, kmax, mlp, mode or tol 5 - Not enough space in lp 6 - Not enough space for reduced Hessian matrix (increase kmax) 7 - Not enough space for sparse factors 8 - Maximum number of unsuccessful restarts taken |
Iter | Number of iterations. |
MinorIter | Number of minor iterations. Always set to 0. FuncEv Number of function evaluations. Set to Iter. |
GradEv | Number of gradient evaluations. Set to Iter. ConstrEv Number of constraint evaluations. Set to 0. |
QP.B | Basis vector in TOMLAB QP standard. |
filterSQP
The solver filterSQP is a Sequential Quadratic Programming solver suitable for solving large, sparse or dense linear, quadratic and nonlinear programming problems. The method avoids the use of penalty functions. Global convergence is enforced through the use of a trust-region and the new concept of a "filter" which accepts a trial point whenever the objective or the constraint violation is improved compared to all previous iterates. The size of the trust-region is reduced if the step is rejected and increased if it is accepted (provided the agreement between the quadratic model and the nonlinear functions is sufficiently good).
This method has performed very well in comparative numerical testing, and has the advantage that the user does not need to supply any estimates of penalty parameters. The NLP problem is specified by means of user subroutines, and it is necessary to provide information about both first and second derivatives of the nonlinear functions in the problem.
It must be used in conjunction with the bqpd solver.
Direct Solver Call
A direct solver call is not recommended unless the user is 100 % sure that no other solvers will be used for the problem. Please refer to Section 3.2.2 for information on how to use filterSQP with TOMLAB.
Purpose
filterSQP solves constrained nonlinear optimization problems defined as
where , , , and
The full input matrix A has three parts A = A = [g ConsPattern' A'];
Where g is a vector of length n, values irrelevant, ConsPattern is the 0-1 pattern of the nonlinear constraint gradients and A is the linear constraint coefficient matrix.
Calling Syntax
The file 'funfdf.m' must be defined and contain: function [mode, f, g] = funfdf(x, Prob, mode, nstate) to compute the objective function f and the gradient g at the point x.
The file 'funcdc.m' must be defined and contain: function [mode ,c ,dcS] = funcdc(x, Prob, mode, nstate) to compute the nonlinear constraint value c and the constraint Jacobian dcS for the nonlinear constraints at the point x.
[ifail, x k, f k, c k, v k, lws, istat, rstat] = filSQPs( A, bl, bu, nnCon, x 0, Scale, scmode, fLow, MaxIter, rho, mlp, kmax, maxf, WarmStart, lws, istat, PriLev, pname, optPar, Prob, moremem);
The sparse version MEX is filSQPs, the dense is filSQPd.
Description of Inputs
The following fields are used:
A | Gradient matrix [g ConsPattern' A'] (sparse or dense). | ||||||||||||||||||||||||||
bl | Lower bounds on (x,c(x),Ax). | ||||||||||||||||||||||||||
bu | Upper bounds on (x,c(x),Ax). | ||||||||||||||||||||||||||
nnCon | Number of nonlinear constraints (i.e. length(c(x)). | ||||||||||||||||||||||||||
x_0 | Initial x vector (if empty set as 0). | ||||||||||||||||||||||||||
Scale | n+m vector scale factors for variables and constraints (same ordering as bl, bu). | ||||||||||||||||||||||||||
scmode | Scale mode:
0 - unit variable and constraint scaling (Scale can be set empty). 1 - User provided scale factors for variables. Scale must be of length n. 2 - Unit variable scaling, user provided constraint scaling. Scale must be of length n+m, but only the last m elements are used. 3- User provided variable AND constraint scaling. Scale must be of length n+m (n+nnCon+nnLin) | ||||||||||||||||||||||||||
fLow | A lower bound on the objective function value. | ||||||||||||||||||||||||||
MaxIter | Maximum number of iterations. | ||||||||||||||||||||||||||
rho | Initial trust-region radius. | ||||||||||||||||||||||||||
mlp | Maximum level parameter for resolving degeneracy in BQPD. | ||||||||||||||||||||||||||
kmax | Maximum size of null-space (at most n). | ||||||||||||||||||||||||||
maxf | Maximum size of the filter. | ||||||||||||||||||||||||||
WarmStart | Set to 1 to restart the solver. If a warmstart is requested, the input parameters lws and istat must be provided. Also, n and m (the number of variables and constraints) may not change. | ||||||||||||||||||||||||||
lws | Used only when doing a warmstart. This must be the lws vector returned by the previous call to filterSQP. Otherwise, set to empty. | ||||||||||||||||||||||||||
lam | Multipliers, n+m values required for warmstarts. If wrong length, zeros are set in the MEX interface. | ||||||||||||||||||||||||||
istat | Used only when doing a warmstart. Must be the first element of the istat vector returned by the previous call to filterSQP. Otherwise, set to empty. | ||||||||||||||||||||||||||
PriLev | Print level. See also input parameter pname.
0 - Silent, except for minor output into ¡pname¿.out 1 - One line per iteration 2 - Scalar information printed 3 - Scalar and vector information printed | ||||||||||||||||||||||||||
pname | Problem name, at most 10 characters. The output files are named <pname>.sum and <pname>.out. | ||||||||||||||||||||||||||
optPar | Vector of max length 20 with optimization parameters: If any element is -999, default value is assigned. Elements 2-8 are BQPD parameters, 1,9-11,19-20 for filterSQP.
| ||||||||||||||||||||||||||
Prob | The Tomlab problem definition structure. | ||||||||||||||||||||||||||
moremem | Scalar or 2x1-vector with workspace increase. If <0, use default strategy. If scalar, use same increase for both real and integer workspaces. If vector, first element is for real workspace, second for integer. |
Description of Outputs
The following fields are used:
Output | Description | ||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Inform | Exit flag indicating success or failure:
0 - Solution found 1 - Unbounded: feasible point x with f(x)<=fmin found 2 - Linear constraints are infeasible 3 - (Locally) nonlinear infeasible, optimal solution to feasibility problem found 4 - Terminated at point with h(x)<=eps but QP infeasible 5 - Terminated with rho<=eps 6 - Terminated due to too many iterations 7 - Crash in user routine could not be resolved 8 - Unexpected failure in QP solver 9 - Not enough real workspace 10 - Not enough integer workspace | ||||||||||||||||||||||||||||||||||||||
x_k | Solution vector (n+m by 1) with n decision variable values together with the m slack variables. | ||||||||||||||||||||||||||||||||||||||
f_k | Function value at optimum x k | ||||||||||||||||||||||||||||||||||||||
c_k | Nonlinear constraints vector at optimum. | ||||||||||||||||||||||||||||||||||||||
v_k | Lagrange multipliers vector (bounds, nonlinear, linear). | ||||||||||||||||||||||||||||||||||||||
lws | Integer vector (used as input when doing warmstarts). | ||||||||||||||||||||||||||||||||||||||
istat | Solution statistics, integer values. First element is required as input if doing a warmstart.
|
Using TOMLAB
Purpose
filterSQPTL solves constrained nonlinear optimization problems defined as
where , , , and .
Calling Syntax
Using the driver routine tomRun :
Prob = ''o''Assign( ... ); Result = tomRun('filterSQP', Prob ... );
or
Result = filterSQPTL(funfdf, funcdc, Prob)
where the inputs are:
funfdf Name of routine [f, gradf ] = funfdf(x, Prob, mode, nstate).
Normally funfdf = nlp fg, included in TOMLAB.
funcdc Name of routine [g, gJac] = funcdc(x, Prob, mode, nstate).
Normally funcdc = nlp cdcS, included in TOMLAB. Probroblem structure in TOMLAB format.
Call Prob = oAssign( ... ) or Prob=ProbDef; to define the Prob for the second option.
Description of Inputs
Prob, The following fields are used:
Input | Description | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
x_L, x_U | Bounds on variables. | ||||||||||||||||||||||||
b_L, b_U | Bounds on linear constraints. | ||||||||||||||||||||||||
c_L, c_U | Bounds on nonlinear constraints. For equality constraints (or fixed variables), set e.g. b L(k) == b U(k). | ||||||||||||||||||||||||
LargeScale | If 1 use sparse version of solver. The default is 0, the dense version. | ||||||||||||||||||||||||
PriLevOpt | Print level in the filterSQP solver. | ||||||||||||||||||||||||
WarmStart | Indicates that the solver should be warmstarted. See Prob.DUNDEE for nec- essary arguments when doing warmstarts. | ||||||||||||||||||||||||
optParam | Structure with optimization parameters. Fields used: | ||||||||||||||||||||||||
MaxIter | Maximum number of iterations. | ||||||||||||||||||||||||
DUNDEE | Structure with special fields for filterSQP optimization parameters. The following fields are used: | ||||||||||||||||||||||||
DUNDEE.QPmin | Lower bound for the QP subproblems. Default: -1E300. | ||||||||||||||||||||||||
DUNDEE.rho | Initial trust region radius. Default: 10.0 (REAL). | ||||||||||||||||||||||||
DUNDEE.kmax | Maximum size of the null-space, less than or equal to no. of variables. Default: n (INTEGER). | ||||||||||||||||||||||||
DUNDEE.maxf | Maximum size of the filter. Default: 100 (INTEGER). | ||||||||||||||||||||||||
DUNDEE.mlp | Maximum level parameter for resolving degeneracy in BQPD QP subsolver.
Default: 100 (INTEGER). | ||||||||||||||||||||||||
DUNDEE.Name | Problem name, at most 10 characters. The output files are named <pname>.sum and <pname>.out. Default name filterSQP, i.e. files filter- SQP.sum, filterSQP.out. | ||||||||||||||||||||||||
DUNDEE.optPar | Vector of max length 20 with optimization parameters: If any element is -999, default value is assigned.
| ||||||||||||||||||||||||
lws | If doing warmstarts, this field is set to the Result.DUNDEE.lws field from the previous run. | ||||||||||||||||||||||||
istat | Similarly, for warmstarts, set istat to Result.DUNDEE.istat from the previous run. Only the first element is used. | ||||||||||||||||||||||||
lam | Vector of initial multipliers. Necessary for warmstarts, but can always be given if desired. Must be n+m elements in order to be used. | ||||||||||||||||||||||||
morereal | Increase of REAL workspace. A problem dependent default value is used if <0 or empty. | ||||||||||||||||||||||||
moreint | Increase of INTEGER workspace. A problem dependent default value is used if <0 or empty.
Scaling parameters: It is possible to supply scale factors for the variables and/or the constraints. Normally, the DUNDEE solvers does not differentiate between linear and nonlinear constraints with regard to scaling, but the Tomlab interface handles this automatically. Thus is it possible to give scale factors e.g. for the nonlinear constraints only. All scaling values must be greater than zero. | ||||||||||||||||||||||||
xScale | Vector of scale factors for variables. If less than n values given, 1's are used for the missing elements. | ||||||||||||||||||||||||
bScale | Vector of scale factors for the linear constraints. If length(bScale) is less than the number of linear constraints ( size(Prob.A,1) ), 1's are used for the missing elements. | ||||||||||||||||||||||||
cScale | Vector of scale factors for the nonlinear constraints. If length(cScale) is less than the number of nonlinear constraints, 1's are used for the missing elements. |
Description of Outputs
Result, The following fields are used:
Result | The structure with results (see ResultDef.m). | ||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
f_k | Function value at optimum. | ||||||||||||||||||||||||||||
g_k | Gradient of the function. | ||||||||||||||||||||||||||||
x_k | Solution vector. | ||||||||||||||||||||||||||||
x_0 | Initial solution vector. | ||||||||||||||||||||||||||||
c_k | Nonlinear constraint residuals. | ||||||||||||||||||||||||||||
cJac | Nonlinear constraint gradients. | ||||||||||||||||||||||||||||
xState | State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; | ||||||||||||||||||||||||||||
bState | State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; | ||||||||||||||||||||||||||||
cState | State of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; | ||||||||||||||||||||||||||||
v_k | Lagrangian multipliers (for bounds + dual solution vector). | ||||||||||||||||||||||||||||
ExitFlag | Exit status from filterSQP MEX. | ||||||||||||||||||||||||||||
Inform | filterSQP information parameter:
0 - Solution found 1 - Unbounded: feasible point x with f(x)<=fmin found 2 - Linear constraints are infeasible 3 - (Locally) nonlinear infeasible, optimal solution to feasibility problem found 4 - Terminated at point with h(x)<=eps but QP infeasible 5 - Terminated with rho<=eps 6 - Too many iterations 7 - Crash in user routine could not be resolved 8 - Unexpected ifail from QP solver. This is often due to too little mem- ory being allocated and is remedied by setting appropriate values in the Prob.DUNDEE.morereal and Prob.DUNDEE.moreint parameters. 9 - Not enough REAL workspace 10 - Not enough INTEGER workspace | ||||||||||||||||||||||||||||
Iter | Number of iterations. | ||||||||||||||||||||||||||||
FuncEv | Number of function evaluations. GradEv Number of gradient evaluations. | ||||||||||||||||||||||||||||
ConstrEv | Number of constraint evaluations. | ||||||||||||||||||||||||||||
Solver | Name of the solver (filterSQP). | ||||||||||||||||||||||||||||
SolverAlgorithm | Description of the solver. | ||||||||||||||||||||||||||||
DUNDEE.lws | Workspace vector, should be treated as integer valued. Required if doing warm- starts. | ||||||||||||||||||||||||||||
DUNDEE.lam | Vector of multipliers, required if doing warmstarts. | ||||||||||||||||||||||||||||
istat | Solution statistics, integer values. First element is required as input if doing a warmstart.
| ||||||||||||||||||||||||||||
rstat | Solution statistics, floating point values.
|
minlpBB
The solver minlpBB solves large, sparse or dense mixed-integer linear, quadratic and nonlinear programming problems. minlpBB implements a branch-and-bound algorithm searching a tree whose nodes correspond to con- tinuous nonlinearly constrained optimization problems. The user can influence the choice of branching variable by providing priorities for the integer variables.
The solver must be used in conjunction with both filterSQP and bqpd.
Direct Solver Call
A direct solver call is not recommended unless the user is 100 % sure that no other solvers will be used for the problem. Please refer to Section 3.2.2 for information on how to use filterSQP with TOMLAB.
Purpose
filterSQP solves constrained nonlinear optimization problems defined as
where , , , and .
The full input matrix A has three parts A = A = [g ConsPattern' A'];
Where g is a vector of length n, values irrelevant, ConsPattern is the 0-1 pattern of the nonlinear constraint gradients and A is the linear constraint coefficient matrix.
Calling Syntax
The file 'funfdf.m' must be defined and contain: function [mode, f, g] = funfdf(x, Prob, mode, nstate) to compute the objective function f and the gradient g at the point x.
The file 'funcdc.m' must be defined and contain: function [mode ,c ,dcS] = funcdc(x, Prob, mode, nstate) to compute the nonlinear constraint value c and the constraint Jacobian dcS for the nonlinear constraints at the point x.
[ifail, x k, f k, c k, v k, lws, istat, rstat] = filSQPs( A, bl, bu, nnCon, x 0, Scale, scmode, fLow, MaxIter, rho, mlp, kmax, maxf, WarmStart, lws, istat, PriLev, pname, optPar, Prob, moremem);
The sparse version MEX is filSQPs, the dense is filSQPd.
Description of Inputs
The following fields are used:
A | Gradient matrix [g ConsPattern' A'] (sparse or dense). | ||||||||||||||||||||||||
bl | Lower bounds on (x,c(x),Ax). | ||||||||||||||||||||||||
bu | Upper bounds on (x,c(x),Ax). | ||||||||||||||||||||||||
nnCon | Number of nonlinear constraints (i.e. length(c(x)). | ||||||||||||||||||||||||
x_0 | Initial x vector (if empty set as 0). | ||||||||||||||||||||||||
Scale' | 'n+m vector scale factors for variables and constraints (same ordering as bl, bu). | ||||||||||||||||||||||||
scmode | Scale mode:
0 - unit variable and constraint scaling (Scale can be set empty). 1 - User provided scale factors for variables. Scale must be of length n. 2 - Unit variable scaling, user provided constraint scaling. Scale must be of length n+m, but only the last m elements are used. 3- User provided variable AND constraint scaling. Scale must be of length n+m (n+nnCon+nnLin) | ||||||||||||||||||||||||
fLow | A lower bound on the objective function value. | ||||||||||||||||||||||||
MaxIter | Maximum number of iterations. | ||||||||||||||||||||||||
rho | Initial trust-region radius. | ||||||||||||||||||||||||
mlp | Maximum level parameter for resolving degeneracy in BQPD. | ||||||||||||||||||||||||
kmax | Maximum size of null-space (at most n). | ||||||||||||||||||||||||
maxf | Maximum size of the filter. | ||||||||||||||||||||||||
WarmStart | Set to 1 to restart the solver. If a warmstart is requested, the input parameters lws and istat must be provided. Also, n and m (the number of variables and constraints) may not change. | ||||||||||||||||||||||||
lws | Used only when doing a warmstart. This must be the lws vector returned by the previous call to filterSQP. Otherwise, set to empty. | ||||||||||||||||||||||||
lam | Multipliers, n+m values required for warmstarts. If wrong length, zeros are set in the MEX interface. | ||||||||||||||||||||||||
istat | Used only when doing a warmstart. Must be the first element of the istat vector returned by the previous call to filterSQP. Otherwise, set to empty. | ||||||||||||||||||||||||
PriLev | Print level. See also input parameter pname.
0 - Silent, except for minor output into ¡pname¿.out 1 - One line per iteration 2 - Scalar information printed 3 - Scalar and vector information printed | ||||||||||||||||||||||||
pname | Problem name, at most 10 characters. The output files are named <pname>.sum and <pname>.out. | ||||||||||||||||||||||||
optPar | Vector of max length 20 with optimization parameters: If any element is -999, default value is assigned. Elements 2-8 are BQPD parameters, 1,9-11,19-20 for filterSQP.
| ||||||||||||||||||||||||
Prob | The Tomlab problem definition structure. | ||||||||||||||||||||||||
moremem | Scalar or 2x1-vector with workspace increase. If <0, use default strategy. If scalar, use same increase for both real and integer workspaces. If vector, first element is for real workspace, second for integer. |
Description of Outputs
The following fields are used:
Inform | Exit flag indicating success or failure:
0 - Solution found 1 - Unbounded: feasible point x with f(x)<=fmin found 2 - Linear constraints are infeasible 3 - (Locally) nonlinear infeasible, optimal solution to feasibility problem found 4 - Terminated at point with h(x)<=eps but QP infeasible 5 - Terminated with rho<=eps 6 - Terminated due to too many iterations 7 - Crash in user routine could not be resolved 8 - Unexpected failure in QP solver 9 - Not enough real workspace 10 - Not enough integer workspace | ||||||||||||||||||||||||||||
x_k | Solution vector (n+m by 1) with n decision variable values together with the m slack variables. | ||||||||||||||||||||||||||||
f_k | Function value at optimum x k | ||||||||||||||||||||||||||||
c_kNonlinear constraints vector at optimum. | |||||||||||||||||||||||||||||
v_k | Lagrange multipliers vector (bounds, nonlinear, linear). | ||||||||||||||||||||||||||||
lws | Integer vector (used as input when doing warmstarts). | ||||||||||||||||||||||||||||
istat | Solution statistics, integer values. First element is required as input if doing a warmstart.
| ||||||||||||||||||||||||||||
rstat | Solution statistics, real values. | ||||||||||||||||||||||||||||
rstat(1) | l 2 norm of KT residual | ||||||||||||||||||||||||||||
rstat(3) | Largest modulus multiplier | ||||||||||||||||||||||||||||
rstat(4) | l inf norm of final step | ||||||||||||||||||||||||||||
rstat(5) | Final constraint violation h(x) |
Using TOMLAB
Purpose
minlpBBTL solves mixed-integer nonlinear optimization problems defined as
where , and and , Furthermore, are restricted to integer values only.
In addition, Special Ordered Sets of type 1 (SOS1) can be defined.
The algorithm uses a branch-and-bound scheme with a depth-first search strategy. The NLP relaxations are solved using the solver filterSQP by R. Fletcher and S. Leyffer.
Calling Syntax
Using the driver routine tomRun :
Prob = ''o''Assign( ... ); Result = tomRun('minlpBB', Prob ... );
or
Result = minlpBBTL(Prob).
Call Prob = oAssign( ... ) or Prob=ProbDef; to define the Prob for the second option.
Description of Inputs
Prob, The following fields are used:
moreint||Number of extra INTEGER workspace locations. Set to <0 for problem dependent default strategy. Scaling parameters. It is possible to supply scale factors for the variables and/or the constraints. Normally, the DUNDEE solvers does not differentiate between linear and nonlinear constraints with regard to scaling, but the TOMLAB interface handles this automatically. Thus is it possible to give scale factors e.g. for the nonlinear constraints only. The three parameters in the Prob.DUNDEE substructure that control scaling are:A | Linear constraints coefficient matrix. | ||||||||||||||||||||||||||||||||
x_L, x_U | Bounds on variables. | ||||||||||||||||||||||||||||||||
b_L, b_U | Bounds on linear constraints. | ||||||||||||||||||||||||||||||||
c_L, c_U | Bounds on nonlinear constraints. | ||||||||||||||||||||||||||||||||
LargeScale | If 1 use sparse version of solver. The default is 0, the dense version. | ||||||||||||||||||||||||||||||||
PriLevOpt | Print level in the minlpBB solver. | ||||||||||||||||||||||||||||||||
optParam.MaxIter | Maximum number of iterations. | ||||||||||||||||||||||||||||||||
MIP | Structure with fields defining the integer properties of the problem. The following fields are used: | ||||||||||||||||||||||||||||||||
IntVars | Vector designating which variables are restricted to integer values. This field is interpreted differently depending on the length.
If length(IntVars) = length(x), it is interpreted as a zero-one vector where all non-zero elements indicate integer values only for the corresponding variable. A length less than the problem dimension indicates that IntVars is a vector of indices for the integer variables, for example [1 2 3 6 7 12] | ||||||||||||||||||||||||||||||||
VarWeight | Defines the priorities of the integer variables. Can be any values, but minlpBB uses integer priorities internally, with higher values implying higher priorities. | ||||||||||||||||||||||||||||||||
sos1 | Structure defining the Special Ordered Sets of Type 1 (SOS1). If there are k sets of type sos1, then sos1(1).var is a vector of indices for variables in sos1, set 1. sos1(1).row is the row number for the reference row identifying the ordering information for the sos1 set, i.e. A(sos1(1).row,sos1(1).var) identifies this information sos1(1).prio sets the priority for sos1 test 1.
sos1(2).var is a vector of indices for variables in sos1, set 2. sos1(2).row is the row number for the reference row of sos1 set 2. sos1(2).prio is the priority for sos1 set 2. sos1(k).var is a vector of indices for variables in sos1, set k. sos1(k).row is the row number for the reference row of sos1 set k. sos1(k).prio is the priority for sos1 set k. | ||||||||||||||||||||||||||||||||
DUNDEE | Structure with special fields for minlpBB optimization parameters. The following fields are used: | ||||||||||||||||||||||||||||||||
stackmax | Maximum size of the LIFO stack storing info about B&B tree. Default: 10000. | ||||||||||||||||||||||||||||||||
QPmin | Lower bound for the QP subproblems. Default: -1E300. | ||||||||||||||||||||||||||||||||
rho | Initial trust region radius. Default: 10.0 (REAL). | ||||||||||||||||||||||||||||||||
kmax | Maximum size of the null-space, less than or equal to no. of variables Default:
n (INTEGER). | ||||||||||||||||||||||||||||||||
maxf | Maximum size of the filter Default: 100 (INTEGER). | ||||||||||||||||||||||||||||||||
mlp | Maximum level parameter for resolving degeneracy in BQPD QP subsolver.. | ||||||||||||||||||||||||||||||||
lam | Multipliers (n+m) on entry (NOTE: Experimental parameter). | ||||||||||||||||||||||||||||||||
Name | Problem name, at most 10 characters. The output files are named <pname>.sum and <pname>.out. Default name minlpBB, i.e. files minlpBB.sum, minlpBB.out. | ||||||||||||||||||||||||||||||||
optPar | Vector of max length 20 with optimization parameters. If any element is -999, default value is assigned. The elements used by minlpBB are:
| ||||||||||||||||||||||||||||||||
morereal | Number of extra REAL workspace locations. Set to <0 for problem dependent default strategy. | ||||||||||||||||||||||||||||||||
xScale | Vector of scale factors for variables. If less than n values given, 1's are used for the missing elements. | ||||||||||||||||||||||||||||||||
bScale | Vector of scale factors for the linear constraints. If length(bScale) is less than the number of linear constraints ( size(Prob.A,1) ), 1's are used for the missing elements. | ||||||||||||||||||||||||||||||||
cScale | Vector of scale factors for the nonlinear constraints. If length(cScale) is less than the number of nonlinear constraints, 1's are used for the missing elements. |
Description of Outputs
Result, The following fields are used:
Result | The structure with results (see ResultDef.m). |
---|---|
f_k | Function value at optimum. |
g_k | Gradient of the function. |
x_k | Solution vector. |
x_0 | Initial solution vector. |
c-k | Nonlinear constraint residuals. |
cJac | Nonlinear constraint gradients. |
xState | State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; |
bState | State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; |
cState | State of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; |
v_k | Lagrangian multipliers (for bounds + dual solution vector). |
ExitFlag | Exit status. |
Inform | minlpBB information parameter:
0 - Optimal solution found 1 - Root problem infeasible 2 - Integer infeasible 3 - Stack overflow - some integer solution. obtained 4 - Stack overflow - no integer solution obtained 5 - SQP termination with rho < eps 6 - SQP termination with iter > max iter 7 - Crash in user supplied routines 8 - Unexpected ifail from QP solvers This is often due to too little mem- ory being allocated and is remedied by setting appropriate values in the Prob.DUNDEE.morereal and Prob.DUNDEE.moreint parameters. 9 - Not enough REAL workspace or parameter error 10 - Not enough INTEGER workspace or parameter error |
rc | Reduced costs. If ninf=0, last m == -v k. |
Iter | Number of iterations. |
FuncEv | Number of function evaluations. GradEv Number of gradient evaluations. ConstrEv Number of constraint evaluations. |
QP.B | Basis vector in TOMLAB QP standard. |
Solver | Name of the solver (minlpBB). |
SolverAlgorithm | Description of the solver (sparse or dense, mainly). |
miqpBB
The solver miqpBB solves sparse and dense mixed-integer linear and quadratic programs. The package implements the Branch and Bound method with some special features such as the computation of improved lower bounds and hot starts for the QP subproblems. miqpBB allows the user to influence the choice of branching variable in two ways: Firstly by employing user supplied priorities in the branching decision and secondly by supplying a choice of branching routines. The package is also efficient as an MILP solver.
Direct Solver Call
A direct solver call is not recommended unless the user is 100 % sure that no other solvers will be used for the problem. Please refer to Section 3.4.2 for information on how to use miqpBB with TOMLAB.
Purpose
miqpBB solves mixed-integer quadratic optimization problems defined as
where , , , and .
The variables , the index subset of , are restricted to be integers.
If F is empty, an LP or MILP problem is solved.
Calling Syntax
[Inform, x k, Obj, Iter] = miqpbb(A, bl, bu, IntVars, Priority, Func, mlp, kmax, stackmax, optPar, PriLev, Print- File, Prob, moremem);
Description of Inputs
The following fields are used:
mlpMaximum level parameter for resolving degeneracy in BQPD which is used as sub-problem solver. If empty, the MEX interface sets mlp to m, the number of constraints.Input | Description | ||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
[c A'] | Linear constraint matrix, dense or sparse n x (m+1) matrix. miqpBB requires the transpose of the constraint matrix, and also with the linear part of the objective function as the first column. | ||||||||||||||||||||||||||
bl, bu | Lower and upper bounds on variables and constraints. Length must be n+m where the first n elements are simple bounds on the variables. | ||||||||||||||||||||||||||
IntVars | Vector with integer variable indices. | ||||||||||||||||||||||||||
Priority | Priorities for the integer variables. Length must the same as that of IntVars. | ||||||||||||||||||||||||||
Func | Name of MATLAB callback function that performs the Hessian - vector multiplication F*x. A standard routine is supplied in tomlab/lib/HxFunc.m, using the Prob.QP.F matrix. If the user for some reason wants to write his own callback function, it must take arguments similar to those of HxFunc.m. The second argument nState is always 0.0 in the current version of the solver. | ||||||||||||||||||||||||||
kmax | Maximum dimension of reduced space. Default (and maximum) value is n, the number of variables. | ||||||||||||||||||||||||||
stackmax | Size of the stack storing information during the tree-search. Default value if empty: 5000. | ||||||||||||||||||||||||||
optPar | Vector of optimization parameters. If -999, set to default. Length from 0 to 20 allowed. The following elements are used by miqpBB:
optPar(3): emin||1.0 Use cscale (constraint scaling) 0.0 no scaling, default 1.0.
optPar(6): npiv ||No repeat if no more than npiv steps were taken, default 3.
| ||||||||||||||||||||||||||
PriLev | Print level in the MEX interface: 0 = off, 1 = only result is printed, 2 = result and intermediate steps are printed. scalar information, 3 = verbose). | ||||||||||||||||||||||||||
PrintFile | Name of print file. Amount/print type determined by PriLev parameter. Default name miqpbbout.txt. | ||||||||||||||||||||||||||
Prob | The Tomlab problem description structure. This is a necessary argument if the standard HxFunc.m callback routine is used. HxFunc uses Prob.QP.F to calculate the Hessian*vector multiplication. | ||||||||||||||||||||||||||
moremem | Scalar or 2x1-vector giving values for extra work memory allocation. If scalar, the value given is added to both the INTEGER and REAL workspaces. If a vector is given, the first element controls the REAL workspace increase and the second the INTEGER workspace. Set one or both elements to values ¡0 for problem dependent memory increases. |
Description of Outputs
The following fields are used:
ifail | Status code: the following values are defined:
0 - Solution found 1 - Error in parameters for BQPD 2 - Unbounded QP encountered 3 - Stack overflow - no integer solution found 4 - Stack overflow - some integer solution found 5 - Integer infeasible 6 - (on I/O) only search for first ifs and stop 7 - Infeasible root problem |
x_k | The solution vector, if any found. If ifail is other than 0 or 4, the contents of x is undefined. |
Obj | The value of the objective function at x k. |
iter | The number of iterations used to solve the problem. |
Using TOMLAB
Purpose
miqpBBTL solves mixed-integer quadratic optimization problems defined as
where , , , and .
The variables , the index subset of , are restricted to be integers
If F is empty, an LP or MILP problem is solved.
miqpBBTL converts the problem from the Tomlab structure format and calls either miqpBBs (sparse) or miqpBBd (dense). On return converts the result to the Tomlab structure format.
Calling Syntax
Using the driver routine tomRun :
Prob = ''o''Assign( ... ); Result = tomRun('miqpBB', Prob ... );
or
Result = miqpBBTL(Prob);
Call Prob = oAssign( ... ) or Prob=ProbDef; to define the Prob for the second option.
Description of Inputs
Prob, The following fields are used:
Input | Description | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
x_L, x_U | Lower and upper bounds on variables. | ||||||||||||||||||||||||
b_L, b_U | Lower and upper bounds on linear constraints. | ||||||||||||||||||||||||
A | Linear constraint matrix, dense or sparse m x n matrix. | ||||||||||||||||||||||||
QP.c | Linear coefficients in objective function, size n x 1. | ||||||||||||||||||||||||
QP.F | Quadratic matrix of size n x n. | ||||||||||||||||||||||||
PriLevOpt | Print Level (0 = off, 1 = summary, 2 = scalar information, 3 = verbose). > 10 Pause statements, and maximal printing (debug mode) | ||||||||||||||||||||||||
LargeScale | If TRUE (=1), use sparse version, otherwise dense. | ||||||||||||||||||||||||
optParam.MaxIter | Limit of iterations. | ||||||||||||||||||||||||
MIP.IntVars | Defines which variables are integers. Variable indices should be in the range [1,...,n]. IntVars is a logical vector ==> x(find(IntVars > 0)) are integers. IntVars is a vector of indices ==> x(IntVars) are integers (if [], then no integers of type I or B are defined). | ||||||||||||||||||||||||
MIP.VarWeight | Variable priorities. Lower value means higher priority. | ||||||||||||||||||||||||
DUNDEE.kmax | Max dimension of reduced space (k), default n, set as 0 if LP. | ||||||||||||||||||||||||
DUNDEE.mlp | Maximum number of levels of recursion. | ||||||||||||||||||||||||
DUNDEE.stackmax | Maximum size of the LIFO stack storing info about B&B tree. Default 5000. | ||||||||||||||||||||||||
DUNDEE.PrintFile | Name of print file. Amount/print type determined by optPar(1) Default name miqpBBout.txt. | ||||||||||||||||||||||||
DUNDEE.optPar | Vector of optimization parameters. If -999, set to default Length from 0 to 20 allowed.
| ||||||||||||||||||||||||
DUNDEE.morereal | Number of extra REAL workspace locations. Set to <0 for problem dependent default value. | ||||||||||||||||||||||||
DUNDEE.moreint | Number of extra INTEGER workspace locations. Set to <0 for problem de- pendent default value. |
Description of Outputs
Result, The following fields are used:
Result | The structure with results (see ResultDef.m). |
---|---|
f_k | Function value at optimum. |
x_k | Solution vector. |
x_0 | Initial solution vector. |
g_k | Gradient of the function. |
xState | State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; |
bState | State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; |
v_k | Lagrangian multipliers (for bounds + dual solution vector). |
ExitFlag | Exit status from miqpBB.m (similar to TOMLAB). |
Inform | miqpBB information parameter.
0 - Optimal solution obtained 1 - Error in parameters for BQPD 2 - Unbounded QP encountered 3 - Stack overflow NO ifs found 4 - Stack overflow some ifs obtained 5 - Integer infeasible 6 - (on I/O) only search for first ifs and stop 7 - Infeasible root problem |
rc | Reduced costs. NOT SET. |
Iter | Number of iterations. |
FuncEv | Number of function evaluations. Set to Iter. |
GradEv | Number of gradient evaluations. Set to Iter. |
ConstrEv | Number of constraint evaluations. Set to 0. |
QP.B | Basis vector in TOMLAB QP standard. |
MinorIter | Number of minor iterations. NOT SET. |
Solver | Name of the solver (miqpBB) |
SolverAlgorithm | Description of the solver. |
DUNDEE.kmax | Max dimension of reduced space (k), default n, set as 0 if LP. |
DUNDEE.mlp | Maximum number of levels of recursion. |
DUNDEE.stackmax | Maximum size of the LIFO stack storing info about B&B tree. |
DUNDEE.mode | Mode of operation, default set as 2 Prob.WarmStart. |
DUNDEE.x | Solution (Warm Start). |
DUNDEE.k | Dimension of the reduced space (Warm Start). |
DUNDEE.e | Steepest-edge normalization coefficients (Warm Start). |
DUNDEE.ls | Indices of active constraints, first n-k used for warm start. |
DUNDEE.lp | List of pointers to recursion information in ls (Warm Start). |
DUNDEE.peq | Pointer to the end of equality constraint indices in ls (Warm Start). |