« 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 mixedinteger quadratic programming
(
qp,
miqp) and continuous and mixedinteger nonlinear
constrained optimization.
Table
2 lists the solvers included in TOMLAB
/MINLP. The solvers are called using a set of MEXfile 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 mfile 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
mixedinteger nonlinear
programming (
minlp) problem defined as


f(x) 


s/t 
−∞ < 
x_{L} 
≤ 
x 
≤ 
x_{U} 
< ∞ 

b_{L} 
≤ 
A x 
≤ 
b_{U} 


c_{L} 
≤ 
c(x) 
≤ 
c_{U}, 
x_{j} N j I, 


(1) 
where
x,
x_{L},
x_{U} R^{n},
f(
x)
R,
A
R^{m1 × n},
b_{L},
b_{U} R^{m1}
and
c_{L},
c(
x),
c_{U} R^{m2}. The variables
x I,
the index subset of 1,...,
n, are restricted to be integers.
mixedinteger quadratic programming (
miqp) problems
defined as


f(x) = 

x^{T} F x + c^{T} x 



s/t 
x_{L} 
≤ 
x 
≤ 
x_{U}, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 


(2) 
where
c,
x,
x_{L},
x_{U} R^{n},
F R^{n
× n},
A R^{m1 × n}, and
b_{L},
b_{U}
R^{m1}. The variables
x I, the index subset of
1,...,
n, are restricted to be integers.
as well as subtypes of these problems.
Table 2: Solver routines in TOMLAB /MINLP .

Function 
Description 
Reference 

bqpd 
Quadratic programming using a nullspace method. 
bqpdTL.m 

miqpBB 
Mixedinteger quadratic programming using bqpd as subsolver. 
miqpBBTL.m 

filterSQP 
Constrained nonlinear minimization using a Filtered Sequential QP method. 
filterSQPTL.m 

minlpBB 
Constrained, mixedinteger nonlinear minimization using a branchandbound
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 KuhnTucker point that is usually a local solution
is found.
The code implements a nullspace active set method with a
technique for resolving degeneracy that guarantees that cycling
does not occur even when roundoff errors are present. Feasibility
is obtained by minimizing a sum of constraint violations. The
Devex method for avoiding nearzero 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


f(x) = 

x^{T} F x + c^{T} x 



s/t 


(3) 
where
c,
x R^{n},
F R^{n × n},
A R^{m1 × n}, and
b_{L},
b_{U}
R^{n+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 nk used for warm start. 

e 
Steepestedge 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 1E10. 
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 5E4. 
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 2x1vector 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 nk used for warm start. 

e 
Steepestedge 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


f(x) = 

x^{T} F x + c^{T} x 



s/t 
x_{L} 
≤ 
x 
≤ 
x_{U}, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 


(4) 
where
c,
x,
x_{L},
x_{U} R^{n},
F R^{n
× n},
A R^{m1 × n}, and
b_{L},
b_{U}
R^{m1}.
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 
Steepestedge normalization coefficients (Warm Start). 

DUNDEE.ls 
Indices of active constraints, first nk 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 1E10. 
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 5E4. 
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 trustregion 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
trustregion 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


f(x) 


s/t 


x 

, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 


c(x) 




(5) 
where
x R^{n},
f(
x)
R,
A
R^{m1 × n},
b_{L},
b_{U} R^{n+m1+m2}
and
c(
x)
R^{m2}.
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 01 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 trustregion radius. 

mlp 
Maximum level parameter for resolving degeneracy in BQPD. 

kmax 
Maximum size of nullspace (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 28 are BQPD parameters, 1,911,1920 for filterSQP. 

optPar(1): iprint 
Print level in filterSQP, default 0. 
optPar(2): tol 
Relative tolerance for BQPD subsolver, default 1E10. 
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 5E4. 
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 1E6. 
optPar(10): ubd 
Upper bound on constraint violation used in the filter, default 1E2. 
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 2x1vector 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 
x_{L} 
≤ 
x 
≤ 
x_{U}, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 
c_{L} 
≤ 
c(x) 
≤ 
c_{U} 


(6) 
where
x,
x_{L},
x_{U} R^{n},
f(
x)
R,
A
R^{m1 × n},
b_{L},
b_{U} R^{m1}
and
c_{L},
c(
x),
c_{U} R^{m2}.
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 nullspace, 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 1E10. 
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 5E4. 
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 1E6. 
DUNDEE.optPar(10): ubd 
Upper bound on constraint violation used in the filter, default 1E2. 
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 mixedinteger
linear, quadratic and nonlinear programming problems. minlpBB
implements a branchandbound 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


f(x) 


s/t 


x 

, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 


c(x) 




(7) 
where
x R^{n},
f(
x)
R,
A
R^{m1 × n},
b_{L},
b_{U} R^{n+m1+m2}
and
c(
x)
R^{m2}.
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 01 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 trustregion radius. 

mlp 
Maximum level parameter for resolving degeneracy in BQPD. 

kmax 
Maximum size of nullspace (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 28 are BQPD parameters, 1,911,1920 for filterSQP. 

optPar(1): iprint 
Print level in filterSQP, default 0. 
optPar(2): tol 
Relative tolerance for BQPD subsolver, default 1E10. 
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 5E4. 
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 1E6. 
optPar(10): ubd 
Upper bound on constraint violation used in the filter, default 1E2. 
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 2x1vector 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 mixedinteger nonlinear optimization
problems defined as


f(x) 


s/t 
x_{L} 
≤ 
x 
≤ 
x_{U}, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 
c_{L} 
≤ 
c(x) 
≤ 
c_{U} 


(8) 
where
x R^{n},
f(
x)
R,
A
R^{m1 × n},
b_{L},
b_{U} R^{n+m1+m2}
and
c(
x)
R^{m2}.
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 branchandbound scheme with a depthfirst
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
zeroone vector where all nonzero 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 nullspace, 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 1E10. 
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 5E4. 
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 1E6. 
optPar(10): ubd 
Upper bound on constraint violation used
in the filter. Default 1E2. 
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 xvalue tests. Default 1E6. 
optPar(13): MIopttol 
Tolerance for function value tests. Default 1E4. 
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 mixedinteger 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 mixedinteger quadratic optimization
problems defined as


f(x) = 

x^{T} F x + c^{T} x 



s/t 


(9) 
where
c,
x R^{n},
F R^{n × n},
A R^{m1 × n}, and
b_{L},
b_{U}
R^{n+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 subproblem 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
treesearch. 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 1E10. 
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 5E4. 
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 1E5. 
optPar(13): MIopttol 
Tolerance used for function value tests, default 1E4. 
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 2x1vector 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 mixedinteger quadratic optimization
problems defined as


f(x) = 

x^{T} F x + c^{T} x 



s/t 
x_{L} 
≤ 
x 
≤ 
x_{U}, 
b_{L} 
≤ 
A x 
≤ 
b_{U} 


(10) 
where
c,
x,
x_{L},
x_{U} R^{n},
F R^{n
× n},
A R^{m1 × n}, and
b_{L},
b_{U}
R^{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.
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 1E10. 
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 5E4. 
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 1E5. 
DUNDEE.optPar(13): MIopttol 
Tolerance used for function value tests, default 1E4. 
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 
Steepestedge normalization coefficients (Warm Start). 

DUNDEE.ls 
Indices of active constraints, first nk 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 »