« Previous « Start » Next »
3 TOMLAB /MINLP Solver Reference
The MINLP solvers are a set of Fortran solvers that were developed
by Roger Fletcher and Sven Leyffer, University 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.
Table
2 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
|
|
f(x) |
|
|
s/t |
−∞ < |
xL |
≤ |
x |
≤ |
xU |
< ∞ |
|
bL |
≤ |
A x |
≤ |
bU |
|
|
cL |
≤ |
c(x) |
≤ |
cU, |
xj N j I, |
|
|
(1) |
where
x,
xL,
xU Rn,
f(
x)
R,
A
Rm1 × n,
bL,
bU Rm1
and
cL,
c(
x),
cU Rm2. The variables
x I,
the index subset of 1,...,
n, are restricted to be integers.
mixed-integer quadratic programming (
miqp) problems
defined as
|
|
|
|
|
s/t |
xL |
≤ |
x |
≤ |
xU, |
bL |
≤ |
A x |
≤ |
bU |
|
|
(2) |
where
c,
x,
xL,
xU Rn,
F Rn
× n,
A Rm1 × n, and
bL,
bU
Rm1. The variables
x I, the index subset of
1,...,
n, are restricted to be integers.
as well as sub-types of these problems.
Table 2: Solver routines in TOMLAB /MINLP .
|
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 |
|
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.
3.1.1 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
c,
x Rn,
F Rn × n,
A Rm1 × n, and
bL,
bU
Rn+m1.
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: |
|
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. |
|
optPar(1): iprint |
Print level in BQPD, default 0. |
optPar(2): tol |
Relative accuracy in solution, default 1E-10. |
optPar(3): emin |
Use cscale (constraint scaling)
0.0 no scaling, default 1.0. |
optPar(4): sgnf |
Max rel error in two numbers equal
in exact arithmetic, default 5E-4. |
optPar(5): nrep |
Max number of refinement steps, default 2. |
optPar(6): npiv |
No repeat if no more than npiv steps
were taken, default 3. |
optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
optPar(8): nfreq |
The max interval between refactorizations, default 500. |
|
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: |
|
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. |
|
3.1.2 Using TOMLAB
Purpose
bqpdTL solves nonlinear optimization
problems defined as
|
|
|
|
|
s/t |
xL |
≤ |
x |
≤ |
xU, |
bL |
≤ |
A x |
≤ |
bU |
|
|
(4) |
where
c,
x,
xL,
xU Rn,
F Rn
× n,
A Rm1 × n, and
bL,
bU
Rm1.
Calling Syntax
Using the driver routine
tomRun:
Prob = ◇Assign( ... );
Result = tomRun('bqpd', Prob ... );
or
Prob = ProbCheck(Prob,'bpqd');
Result = bqpdTL(Prob);
Call Prob = ◇Assign( ... ) or Prob=ProbDef; to define the
Prob for the second option.
Description of Inputs
Prob , The following fields are used: |
|
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: |
|
|
DUNDEE.optPar(1): iprint |
Print level in PrintFile, default 0. |
DUNDEE.optPar(2): tol |
Relative accuracy in solution, default 1E-10. |
DUNDEE.optPar(3): emin |
1.0 Use cscale (constraint scaling) 0.0 no scaling, default 1.0. |
DUNDEE.optPar(4): sgnf |
Max rel error in two numbers equal in exact arithmetic, default 5E-4. |
DUNDEE.optPar(5): nrep |
Max number of refinement steps, default 2. |
DUNDEE.optPar(6): npiv |
No repeat if no more than npiv steps were taken, default 3. |
DUNDEE.optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
DUNDEE.optPar(8): nfreq |
The max interval between refactorizations, default 500. |
|
Description of Outputs
Result , The following fields are used: |
|
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. |
|
|
3.2 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.
3.2.1 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
x Rn,
f(
x)
R,
A
Rm1 × n,
bL,
bU Rn+m1+m2
and
c(
x)
Rm2.
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. |
|
optPar(1): iprint |
Print level in filterSQP, default 0. |
optPar(2): tol |
Relative tolerance for BQPD subsolver, default 1E-10. |
optPar(3): emin |
1=Use cscale in BQPD, 0=no scaling , default 1.0. |
optPar(4): sgnf |
Max rel error in two numbers equal in exact arithmetic (BQPD), default 5E-4. |
optPar(5): nrep |
Max number of refinement steps (BQPD), default 2. |
optPar(6): npiv |
No repeat if no more than npiv steps were taken, default 3. |
optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
optPar(8): nfreq |
The max interval between refactorizations, default 500. |
optPar(9): NLP_eps |
NLP subproblem tolerance, default 1E-6. |
optPar(10): ubd |
Upper bound on constraint violation used in the filter, default 1E-2. |
optPar(11): tt |
Parameter related to ubd. The actual upper
bound is defined by the maximum of ubd and tt multiplied by the
initial constraint violation., default 0.125. |
optPar(19): infty |
A large value representing infinity, default 1E20. |
optPar(20): Nonlin |
If 1, skip linear feasibility tests filterSQP treating all constraints as nonlinear, default 0. |
|
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_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. |
|
istat(1) |
Dimension of nullspace at solution |
istat(2) |
Number of iterations |
istat(3) |
Number of feasibility iterations |
istat(4) |
Number of objective evaluations |
istat(5) |
Number of constraint evaluations |
istat(6) |
Number of gradient evaluations |
istat(7) |
Number of Hessian evaluations |
istat(8) |
Number of QPs with mode<=2 |
istat(9) |
Number of QPs with mode>=4 |
istat(10) |
Total number of QP pivots |
istat(11) |
Number of SOC steps |
istat(12) |
Maximum size of filter |
istat(13) |
Maximum size of Phase 1 filter |
istat(14) |
Number of QP crashes |
|
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) |
|
3.2.2 Using TOMLAB
Purpose
filterSQPTL solves constrained nonlinear optimization
problems defined as
|
|
f(x) |
|
|
s/t |
xL |
≤ |
x |
≤ |
xU, |
bL |
≤ |
A x |
≤ |
bU |
cL |
≤ |
c(x) |
≤ |
cU |
|
|
(6) |
where
x,
xL,
xU Rn,
f(
x)
R,
A
Rm1 × n,
bL,
bU Rm1
and
cL,
c(
x),
cU Rm2.
Calling Syntax
Using the driver routine
tomRun:
Prob = ◇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. |
Prob |
Problem structure in TOMLAB format. |
|
Call Prob = ◇Assign( ... ) or Prob=ProbDef; to define the
Prob for the second option.
Description of Inputs
Prob , The following fields are used: |
|
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 necessary
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 filterSQP.sum, filterSQP.out. |
|
DUNDEE.optPar |
Vector of max length 20 with optimization parameters: If any element is -999, default value is assigned. |
|
DUNDEE.optPar(1): iprint |
Print level in filterSQP, default 0. |
DUNDEE.optPar(2): tol |
Relative tolerance for BQPD subsolver, default 1E-10. |
DUNDEE.optPar(3): emin |
1=Use cscale in BQPD, 0=no scaling , default 1.0. |
DUNDEE.optPar(4): sgnf |
Max rel error in two numbers equal in exact arithmetic (BQPD), default 5E-4. |
DUNDEE.optPar(5): nrep |
Max number of refinement steps (BQPD), default 2. |
DUNDEE.optPar(6): npiv |
No repeat if no more than npiv steps were taken, default 3. |
DUNDEE.optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
DUNDEE.optPar(8): nfreq |
The max interval between refactorizations, default 500. |
DUNDEE.optPar(9): NLP_eps |
NLP subproblem tolerance, default 1E-6. |
DUNDEE.optPar(10): ubd |
Upper bound on constraint violation used in the filter, default 1E-2. |
DUNDEE.optPar(11): tt |
Parameter related to ubd. The actual upper
bound is defined by the maximum of ubd and tt multiplied by the
initial constraint violation., default 0.125. |
DUNDEE.optPar(19): infty |
A large value representing infinity, default 1E20. |
DUNDEE.optPar(20): Nonlin |
If 1, skip linear feasibility tests filterSQP treating all constraints as nonlinear, default 0. |
|
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 memory 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 warmstarts. |
|
DUNDEE.lam |
Vector of multipliers, required if doing warmstarts. |
|
istat |
Solution statistics, integer values. First element
is required as input if doing a warmstart. |
|
istat(1) |
Dimension of nullspace at solution |
istat(2) |
Number of iterations |
istat(3) |
Number of feasibility iterations |
istat(4) |
Number of objective evaluations |
istat(5) |
Number of constraint evaluations |
istat(6) |
Number of gradient evaluations |
istat(7) |
Number of Hessian evaluations |
istat(8) |
Number of QPs with mode<=2 |
istat(9) |
Number of QPs with mode>=4 |
istat(10) |
Total number of QP pivots |
istat(11) |
Number of SOC steps |
istat(12) |
Maximum size of filter |
istat(13) |
Maximum size of Phase 1 filter |
istat(14) |
Number of QP crashes |
|
rstat |
Solution statistics, floating point 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) |
|
3.3 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 continuous 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.
3.3.1 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
x Rn,
f(
x)
R,
A
Rm1 × n,
bL,
bU Rn+m1+m2
and
c(
x)
Rm2.
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. |
|
optPar(1): iprint |
Print level in filterSQP, default 0. |
optPar(2): tol |
Relative tolerance for BQPD subsolver, default 1E-10. |
optPar(3): emin |
1=Use cscale in BQPD, 0=no scaling , default 1.0. |
optPar(4): sgnf |
Max rel error in two numbers equal in exact arithmetic (BQPD), default 5E-4. |
optPar(5): nrep |
Max number of refinement steps (BQPD), default 2. |
optPar(6): npiv |
No repeat if no more than npiv steps were taken, default 3. |
optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
optPar(8): nfreq |
The max interval between refactorizations, default 500. |
optPar(9): NLP_eps |
NLP subproblem tolerance, default 1E-6. |
optPar(10): ubd |
Upper bound on constraint violation used in the filter, default 1E-2. |
optPar(11): tt |
Parameter related to ubd. The actual upper
bound is defined by the maximum of ubd and tt multiplied by the
initial constraint violation., default 0.125. |
optPar(19): infty |
A large value representing infinity, default 1E20. |
optPar(20): Nonlin |
If 1, skip linear feasibility tests filterSQP treating all constraints as nonlinear, default 0. |
|
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_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. |
|
istat(1) |
Dimension of nullspace at solution |
istat(2) |
Number of iterations |
istat(3) |
Number of feasibility iterations |
istat(4) |
Number of objective evaluations |
istat(5) |
Number of constraint evaluations |
istat(6) |
Number of gradient evaluations |
istat(7) |
Number of Hessian evaluations |
istat(8) |
Number of QPs with mode<=2 |
istat(9) |
Number of QPs with mode>=4 |
istat(10) |
Total number of QP pivots |
istat(11) |
Number of SOC steps |
istat(12) |
Maximum size of filter |
istat(13) |
Maximum size of Phase 1 filter |
istat(14) |
Number of QP crashes |
|
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) |
|
3.3.2 Using TOMLAB
Purpose
minlpBBTL solves mixed-integer nonlinear optimization
problems defined as
|
|
f(x) |
|
|
s/t |
xL |
≤ |
x |
≤ |
xU, |
bL |
≤ |
A x |
≤ |
bU |
cL |
≤ |
c(x) |
≤ |
cU |
|
|
(8) |
where
x Rn,
f(
x)
R,
A
Rm1 × n,
bL,
bU Rn+m1+m2
and
c(
x)
Rm2.
The variables
x I, the index subset of 1,...,
n, are
restricted to be integers.
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 = ◇Assign( ... );
Result = tomRun('minlpBB', Prob ... );
or
Result = minlpBBTL(Prob).
Call Prob = ◇Assign( ... ) or Prob=ProbDef; to define the
Prob for the second option.
Description of Inputs
Prob , The following fields are used: |
|
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: |
|
optPar(1): iprint |
Print level in minlpBB
Summary on file minlpBB.sum. More printout on file minlpBB.out. Default 0. |
optPar(2): tol |
Relative tolerance for BQPD subsolver. Default 1E-10. |
optPar(3): emin |
1=Use cscale in BQPD, 0=no scaling. Default 1.0. |
optPar(4): sgnf |
Max rel error in two numbers equal in exact
arithmetic (BQPD). Default 5E-4. |
optPar(5): nrep |
Max number of refinement steps (BQPD). Default 2. |
optPar(6): npiv |
No repeat if no more than npiv steps were taken. Default 3. |
optPar(7): nres |
Max number of restarts if unsuccessful. Default 2. |
optPar(8): nfreq |
The max interval between refactorizations. Default 500. |
optPar(9): NLP_eps |
NLP subproblem tolerance. Default 1E-6. |
optPar(10): ubd |
Upper bound on constraint violation used
in the filter. Default 1E-2. |
optPar(11): tt |
Parameter related to ubd. The actual
upper bound is defined by the maximum of ubd and tt multiplied by the initial
constraint violation. Default 0.125. |
optPar(12): epsilon |
Tolerance for x-value tests. Default 1E-6. |
optPar(13): MIopttol |
Tolerance for function value tests. Default 1E-4. |
optPar(17): branchtype |
Branch strategy. Currently only 1 strategy. |
optPar(19): infty |
A large value representing infinity. Default 1E20. |
optPar(20): Nonlin |
If 1, skip linear feasibility tests minlpBB treating
all constraints as nonlinear. Default 0. |
|
morereal |
Number of extra REAL workspace locations. Set to <0
for problem dependent default strategy. |
|
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: |
|
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 memory 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). |
|
3.4 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.
3.4.1 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
c,
x Rn,
F Rn × n,
A Rm1 × n, and
bL,
bU
Rn+m1.
The variables
x I, the index subset of 1,...,
n, 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, PrintFile, Prob, moremem);
Description of Inputs
The following fields are used: |
|
[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. |
|
mlp |
Maximum 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. |
|
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(1): iprint |
Print level in miqpbb, default 0. |
optPar(2): tol |
Relative accuracy in solutio, default 1E-10. |
optPar(3): emin |
1.0 Use cscale (constraint scaling) 0.0 no scaling, default 1.0. |
optPar(4): sgnf |
Max rel error in two numbers equal in exact arithmetic, default 5E-4. |
optPar(5): nrep |
Max number of refinement steps, default 2. |
optPar(6): npiv |
No repeat if no more than npiv steps were taken, default 3. |
optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
optPar(8): nfreq |
The max interval between refactorizations, default 500. |
optPar(12): epsilon |
Tolerance used for x value tests, default 1E-5. |
optPar(13): MIopttol |
Tolerance used for function value tests, default 1E-4. |
optPar(14): fIP |
Upper bound on f(x). Only consider solutions < fIP - epsilon, default 1E20. |
optPar(15): timing |
No Timing = 1, Use timing, = 0. Default, no timing |
optPar(16): max_time |
Maximal time allowed for the run in seconds, default 4E3. |
optPar(17): branchType |
Branch on variable with highest
priority. If tie: |
|
= 1. Variable with largest fractional part, among those branch
on the variable giving the largest increase in the
objective. |
|
= 2. Tactical Fletcher (PMO) branching. The var that solves
max(min(e+,e-)) is chosen. The problem than corresponding to
min(e+,e-) is placed on the stack first. |
|
= 3. Tactical branching, Padberg/Rinaldi,91, Barahona et al.,89
(i) Choose the branching variable the one that most violates the
integrality restrictions. i.e. find max(i)min(pi+,pi-)
pi+ = int(x(i)+1) - x(i) , pi- = x(i) - int(x(i))
(ii) among those branch on the variable that gives the greatest
increase in the obj. function (iii) Finally a LOWER BOUND is
computed on the branched problems using the bounding method of
Fletcher and Leyffer (dual active set step) DEFAULT = 1. |
optPar(18): ifsFirst |
If 1, then only search for first ifs (ifail=6), Default 0. |
optPar(19): infty |
Real value for infinity, default 1E20. |
|
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. |
|
3.4.2 Using TOMLAB
Purpose
miqpBBTL solves mixed-integer quadratic optimization
problems defined as
|
|
|
|
|
s/t |
xL |
≤ |
x |
≤ |
xU, |
bL |
≤ |
A x |
≤ |
bU |
|
|
(10) |
where
c,
x,
xL,
xU Rn,
F Rn
× n,
A Rm1 × n, and
bL,
bU
Rm1.
The variables
x I, the index subset of 1,...,
n, 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 = ◇Assign( ... );
Result = tomRun('miqpBB', Prob ... );
or
Result = miqpBBTL(Prob);
Call Prob = ◇Assign( ... ) or Prob=ProbDef; to define the
Prob for the second option.
Description of Inputs
Prob , The following fields are used: |
|
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.optPar(1) |
Print level in miqpBB. |
|
= 0 Silent |
|
= 1 Warnings and Errors |
|
= 2 Summary information |
|
= 3 More detailed information |
DUNDEE.optPar(2): tol |
Relative accuracy in solution, default 1E-10. |
DUNDEE.optPar(3): emin |
1.0 Use cscale (constraint scaling) 0.0 no scaling, default 1.0. |
DUNDEE.optPar(4): sgnf |
Max rel error in two numbers equal in exact arithmetic, default 5E-4. |
DUNDEE.optPar(5): nrep |
Max number of refinement steps, default 2. |
DUNDEE.optPar(6): npiv |
No repeat if no more than npiv steps were taken, default 3. |
DUNDEE.optPar(7): nres |
Max number of restarts if unsuccessful, default 2. |
DUNDEE.optPar(8): nfreq |
The max interval between refactorizations, default 500. |
DUNDEE.optPar(12): epsilon |
Tolerance used for x value tests, default 1E-5. |
DUNDEE.optPar(13): MIopttol |
Tolerance used for function value tests, default 1E-4. |
DUNDEE.optPar(14): fIP |
Upper bound on f(x). Only consider solutions < fIP - MIopttol, default 1E20. |
DUNDEE.optPar(15): timing |
If 1 - use timing, if 0 no timing (default). |
DUNDEE.optPar(16): max_time |
Maximal time allowed for the run in seconds, default 4E3. |
DUNDEE.optPar(17): branchType |
Branch on variable with highest priority. If tie: |
|
= 1. Variable with largest fractional part, among those branch
on the variable giving the largest increase in the objective. |
|
= 2. Tactical Fletcher (PMO) branching. The var that solves
max(min(e+,e-)) is chosen. The problem than corresponding to
min(e+,e-) is placed on the stack first. |
|
= 3. Tactical branching, Padberg/Rinaldi,91, Barahona et
al.,89. (i) Choose the branching variable the one that most violates the
integrality restrictions. i.e. find max(i)min(pi+,pi-)
pi+ = int(x(i)+1) - x(i) , pi- = x(i) - int(x(i))
(ii) among those branch on the variable that gives the greatest
increase in the obj. function (iii) Finally a LOWER BOUND is
computed on the branched problems using the bounding method of
Fletcher and Leyffer (dual active set step) DEFAULT =
1. |
|
DUNDEE.optPar(18): ifsFirst |
If 1, then only search for first ifs (ifail=6), DEFAULT 0. |
DUNDEE.optPar(19): infty |
Real value for infinity (default 1E20). |
|
|
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 dependent 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). |
|
« Previous « Start » Next »