MISQP

From TomWiki

Jump to: navigation, search

Contents

Introduction

Overview

Welcome to the TOMLAB /MISQP User's Guide. TOMLAB /MISQP includes the MISQP and MIQL solvers from Klaus Schittkowski and an interface to The MathWorks' MATLAB.

MISQP solves mixed-integer nonlinear mathematical programming problems with equality and inequality constraints. It is assumed that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value.

The internal algorithm uses a modified sequential quadratic approximation method, stabilized by a trust region method including Yuan's second order corrections. The Hessian of the Lagrangian function is approximated by BFGS updates subject to the continous and integer variables.

MIQL solves strictly convex mixed-integer quadratic mathematical programming problems with linear equality and inequality constraints. The mixed-integer problem is solved by a branch-and-cut algorithm.

Contents of this Manual

More information

Please visit the following links for more information:

Prerequisites

In this manual we assume that the user is familiar with mixed-integer nonlinear programming, setting up problems in TOMLAB (in particular unconstrained and constrained mixed-integer nonlinear programming (minlp) problems) and the Matlab language in general.

Using the Matlab Interface

The MISQP solver is accessed via the tomRun driver routine, which calls the misqpTL interface routine. The solver itself is located in the MEX file misqp. The same applies for the other two solvers.

Observe that miqpAssign should be used when defining the problem for MIQL and qpAssign for QL.

FunctionDescription
misqpTLThe interface routine called by the TOMLAB driver routine tomRun.

This routine then calls the MEX file misqp

miqlTLThe interface routine called by the TOMLAB driver routine tomRun.

This routine then calls the MEX file miql

qlTLThe interface routine called by the TOMLAB driver routine tomRun.

This routine then calls the MEX file ql

Setting MISQP Options

All MISQP control parameters are possible to set from Matlab.

Setting options using the Prob.MISQP structure

The parameters can be set as subfields in the Prob.MISQP structure. The following example shows how to set a limit on the maximum number of iterations.

Prob = minlpAssign(...)   %   Setup problem,  see help minlpAssign for more information
Prob.MISQP.maxit = 2000;  %   Setting maximum number of iterations

The maximum number of iterations can also be done through the TOMLAB parameter MaxIter:

Prob.optParam.MaxIter = 200;

In the cases where a solver specific parameter has a corresponding TOMLAB general parameter, the latter is used only if the user has not given the solver specific parameter.

A complete description of the available MISQP parameters can be found in #misqpTL.

Setting options using the Prob.MIQL structure

Options can be set for MIQL in the same way as for MISQP as described above in #Setting options using the Prob.MISQP structure. The only difference is in the name of the structure (MIQL instead of MISQP) and the assign-routine (miqpAssign instead of minlpAssign).

Setting options using the Prob.QL structure

Options can be set for QL in the same way as for MISQP as described above in #Setting options using the Prob.MISQP structure. The only difference is in the name of the structure (QL instead of MISQP) and the assign-routine (qpAssign instead of minlpAssign).

MISQP Solver References

Table: Solver routines in TOMLAB /MISQP.

FunctionDescriptionReference
qlQuadratic programming using a primal-dual method with cholesky decomposition.qlTL.m
miqlMixed-integer quadratic programming using a branch-and-cut method with ql as subsolver.miqlTL.m
misqpConstrained, mixed-integer nonlinear minimization using a sequential quadratic approximation method. miql is used as MIQP subsolver.misqpTL.m

A detailed description of the TOMLAB /MISQP solver interfaces is given below. Also see the M-file help for misqpTL.m, miqlTL.m and qlTL.m.

misqpTL

Purpose

Solves mixed-integer nonlinear optimization problems.

MISQP solves problems of the form


\begin{array}{cccccc}
\min\limits_{x} & f(x) \\ 
& \\
s/t & x_{L} & \leq  & x    & \leq  & x_{U} \\ 
& b_{L} & \leq  & Ax   & \leq  & b_{U} \\ 
& c_{L} & \leq  & c(x)    & \leq  & c_{U}
\end{array}


where x,x_{L},x_{U}\in \mathbb{R}^{n}, A\in \mathbb{R}^{m_{1}\times n} and b_{L},b_{U}\in \mathbb{R}^{m_{1}} and c(x),c_{L},c_{U}\in \mathbb{R} ^{m_{2}}, Furthermore, x_i,\, i\in\mathbb{I} are restricted to integer values only.

Calling Syntax

Prob = minlpAssign( ... );
Result = tomRun('misqp',Prob,...);

Description of Inputs

Prob Problem description structure. The following fields are used:

FieldDescription
x_L, x_UBounds on variables.
b_L, b_UBounds on linear constraints.
ALinear constraint matrix.
PriLevOptPrint Level in solver
MIP.IntVarsIf empty, all variables are assumed non-integer

If islogical(IntVars) (i.e. all elements are 0/1), then 1 = integer variable, 0 = continuous variable.

If any element >1, IntVars is the indices for integer variables

MISQP.PrintFile Name of MISQP print file. Amount and type of printing determined by PriLevOpt. Default name misqp_printfile.txt.
MISQP.maxitMaximum number of outer iterations, where one iteration corresponds to one formulation and solution of the quadratic programming subproblem, or, alternatively, one evaluation of gradients (default is to use optParam.MaxIter if set, otherwise set maxit to 1000).
MISQP.mnfsMaximum number of feasible steps without improvements, where the relative change of objective function values is measured by acc and feasibility is measured by sqrt(acc), must be greater than 1 (default maxit).
MISQP.maxndeMaximum number of branch-and-bound steps for solving MIQP. Default is (2*n+m+4)^2, where n is the number of variables and m is the number of constraints.
MISQP.nonmonMaximum number of successive iterations, which are to be considered for the non-monotone trust region algorithm (default 2).
MISQP.accDesired final accuracy. The termination accuracy should not be smaller than the accuracy by which gradients are computed. If acc<=0, the machine precision is computed by MISQP and subsequently multiplied by 1.0e4 (default 1e-6).
MISQP.accqpThe tolerance is needed for the QP solver to perform several tests, for example whether optimality conditions are satisfied or whether a number is considered as zero or not. If accqp is less or equal to zero, then the machine precision is computed by MISQP and subsequently multiplied by 1.0E4 (default 1e-9).
MISQP.rpenFactor for increasing a penalty parameter (sigma), must be greater than one (default 10).
MISQP.dltdecFactor for decreasing the internal descent parameter DELTA. dltdec must be less than than one (default 0.1).
MISQP.sigmaInitial penalty parameter, greater than one (default 1000).
MISQP.deltaInitial scaling parameter (default 0.05).
MISQP.trustcInitial trust region radius for continuous variables, must be greater than or equal to one (default 10.0).
MISQP.trustiInitial trust region radius for integer variables (default 10.0).
MISQP.scbndScaling bound in case of fscale=1, i.e., function values are scaled only if their absolute initial values are greater than the bound (default 1.0).
MISQP.mrsMaximum number of internal restarts without improving solution. Setting might lead to better results, but increases the number of function evaluations. The value must be less than 15 (default 2).
MISQP.fscaleMISQP internally scales function values.

0 - No scaling.

1 - Subject to their absolute values, if greater than 1.0 or scbnd, respectively (default).

MISQP.scaleMISQP internally scales continuous variables.

0 - No scaling.

1 - Scaling enabled (default).

MISQP.bmodMISQP modifies the Hessian approximation in order to get more accurate search directions. Calculation time is increased in case of integer variables.

0 - No modification

1 - (default 1).

Options for the MIQP subsolver MIQL:

MISQP.iprqpPrint level of subsolver MIQL (default 0).
MISQP.ibrBranching rule for MIQP subproblem

1 - Maximal fractional branching (default).

2 - Minimal fractional branching.

MISQP.insNode selection rule for MIQP subproblem.

1 - Best of all.

2 - Best of two.

3 - Depth first (default).

MISQP.wstartMaximal number of successive warmstarts. Default 100.
MISQP.impbSet nonzero to calculate improved bounds when Best-of-All node selection strategy is used (default 0).
MISQP.dfdirSet nonzero to select direction for Depth-First according to value of Lagrange function (default 0).
MISQP.cholmCholesky decomposition mode.

0 - Calculate Cholesky decomposition once and reuse it.

1 - Calculate new Cholesky decomposition whenever warmstart is not active (default).

MISQP.cutControl the cutting process.

0 - No cuts (default).

1 - Use disjunctive cuts only.

2 - Complemented mixed integer rounding (CMIR) cuts only.

3 - Both disjunctive cuts and CMIR cuts.

MISQP.maxdcMaximal number of rounds for disjunctive cuts. Default 5.
MISQP.maxcmMaximal number of cuts for CMIR cuts. Default 5.
MISQP.phmPrimal heuristic mode.

0 - No primal heuristics (default).

1 - Nearest integer.

2 - Feasibility pump.

Description of Outputs

Result Structure with result from optimization. The following fields are set:

OutputDescription
ResultThe structure with results (see ResultDef.m).
x_kSolution vector.
x_0Initial solution vector.
f_kFunction value at optimum.
g_kGradient of the objective function.
c_kNonlinear constraint residuals.
cJacNonlinear constraint gradients.
xStateState of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bStateState of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
cStateState of nonlinear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
ExitFlagExit status from misqp.m (similar to TOMLAB).
ExitTextExit text from solver.
InformMISQP information parameter.

0 - The optimality conditions are satisfied.

1 - Termination after maxit iterations.

2 - Trust region radius lower than termination tolerance of the QP solver.

3 - Penalty parameter sigma tends to infinity.

4 - Termination at infeasible iterate.

5 - Termination with zero trust region for integer variables.

6 - Length of a working array is too short.

7 - There are false dimensions.

8 - Lower or upper bound of variable violates initial value.

9 - Linear constraints are inconsistent.

11 - QL could not solver the QP after 40*(n+m) iterations.

12 - The termination accuracy is insufficient for QL.

13 - QL terminated due to internal inconsistency, division by zero.

14 - Numerical instabilities in QL.

15 - More than mnfs steps without improvements of feasible function values.

> 90 - QP sub problem error.

FuncEvNumber of function evaluations.
GradEvNumber of gradient evaluations.
ConstrEvNumber of constraint evaluations.
QP.BBasis vector in TOMLAB QP standard.
SolverName of solver (misqp).
SolverAlgorithmDescription of the solver.

miqlTL

Purpose

Solves strictly convex mixed-integer quadratic programming problems.

MIQL solves problems of the form


\begin{array}{ll}
\min\limits_{x} & f(x) = \frac{1}{2} x^T F x + c^T x\\
& \\
s/t & \begin{array}{lcccl}
x_{L} & \leq & x & \leq & x_{U} \\
b_{L} & \leq  & A x  & \leq & b_{U} \\
\end{array}
\end{array}


where c, x, x_L, x_U \in \mathbb{R}^n, F \in \mathbb{R}^{n \times n} and positive definite, A \in \mathbb{R}^{m_1 \times n}, and b_L,b_U \in \mathbb{R}^{m_1}.

The variables x \in 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

Prob = miqpAssign( ... );
Result = tomRun('miql',Prob,...);

Description of Inputs

Prob Problem description structure. The following fields are used:

FieldDescription
x_L, x_UBounds on variables.
b_L, b_UBounds on linear constraints.
ALinear constraint matrix.
QP.c Linear coefficients in objective function.
QP.F Quadratic matrix of size n x n.
PriLevOptPrint Level in solver (0-4)

0 - No output. Default

1 - Root QP and final performance summary.

2 - Additional branch and bound iterations counter.

3 - Additional total output from all generated subproblems.

4 - Additional formal details.

MIP.IntVarsVector of indices of the integer variables.
MIQL.PrintFile Name of MIQL print file. Amount and type of printing determined by PriLevOpt. Default name miql.txt.
MIQL.epsDesired final accuracy. The parameter value should not be smaller than the underlying machine precision.
MIQL.accThe accuracy to identify integer values for integer variables. If acc is less than machine precision, e.g., acc = 0, then acc is set to the machine precision.
MIQL.ibrBranching rule

1 - Maximal fractional branching (default).

2 - Minimal fractional branching.

MIQL.insNode selection strategy

1 - Best of all (large search trees) (default).

2 - Best of two (warmstarts, less memory for search tree.)

3 - Depth first (good warmstarts, smallest memory, many QPs.)

MIQL.maxndeMaximal number of nodes, e.g., 100,000.

Default: (2*n + 2*m + 6)^2 for cut == 1,3), (2*n + m + 4)^2 otherwise.

MIQL.wstartMaximal number of successive warmstarts to avoid numerical instabilities. Default 100.
MIQL.impb1 - Calculate improved bounds when best-of-all node selection strategy (ins = 1) is used.

0 - Default.

MIQL.dfdir1 Select direction for depth-first node selection strategy (ins = 3) according to value of Lagrange function.

0 - Default.

MIQL.cholmCholesky decomposition mode.

0 - Calculate Cholesky decomposition once and reuse it.

1 - Calculate new Cholesky decomposition whenever warmstart is not active. Default.

MIQL.cutControl the cutting process.

0 - No cuts. Default

1 - Use disjunctive cuts only.

2 - Complemented mixed integer rounding (CMIR) cuts only.

3 - Both disjunctive cuts and CMIR cuts.

MIQL.maxdcMaximal number of rounds for disjunctive cuts. Default 1, if disjunctive cuts should be generated.
MIQL.maxcmMaximal number of cuts for CMIR cuts. Default 1, if CMIR cuts should be generated.
MIQL.phmPrimal heuristic mode.

0 - No primal heuristics. Default

1 - Nearest integer.

2 - Feasibility pump.

Description of Outputs

Result Structure with result from optimization. The following fields are set:

OutputDescription
ResultThe structure with results (see ResultDef.m).
f_kFunction value at optimum.
x_kSolution vector.
x_0Initial solution vector.
g_kExact gradient computed at optimum.
xStateState of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bStateState of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
v_kLagrangian multipliers (for bounds + dual solution vector).
ExitFlagExit status from miql.m (similar to TOMLAB).
InformMIQL information parameter.

-4 - Branch and Bound root QP could not be solved.

-3 - Relaxed QP without feasible solution.

-2 - A feasible solution could not be computed by maxnde subproblems.

-1 - A feasible solution does not exist.

0 - The optimal solution is found.

1 - A feasible solution is found, but tree search is terminated because of reaching maxnde nodes.

2 - Index in Prob.MIP.intVars out of bounds.

3 - Internal inconsistency of continuous QP.

4 - Length of a work array is too short.

5 - Sizes are incorrectly set.

6 - An integer option for Branch and Bound is incorrectly set.

7 - Independent Lagrangian multipliers could not be calculated, working arrays are too small, increase maxnde.

8 - Print file or print level is incorrectly set.

9 - Lower variable bound greater than upper variable bound.

11 - Subsolver QL could not solve QP after a maximal number of 40*(n+m) iterations.

12 - The termination accuracy is insufficient for QL to satisfy its convergence criteria.

13 - QL terminated due to an internal inconsistency, e.g., division by zero.

14 - Numerical instabilities prevent successful termination of QL.

> 90 - Constraints are inconsistent and constraint number Inform - 100 is causing the conflict. The problem has no feasible solution.

rcReduced costs. If ninf=0, last m == -v_k.
IterNumber of iterations.
FuncEvNumber of function evaluations. Set to Iter.
GradEvNumber of gradient evaluations. Set to Iter.
ConstrEvNumber of constraint evaluations. Set to 0.
QP.BBasis vector in TOMLAB QP standard.
MinorIterNumber of minor iterations. NOT SET.
SolverName of solver (miql).
SolverAlgorithmDescription of the solver.
MIQL.cutgesTotal number of cutting planes.
MIQL.nodesTotal number of branch and bound nodes.
MIQL.ctimeTime spent generating cutting planes.
MIQL.bbtimeTime spent for branch and bound process.
MIQL.cutgapGap reduced by cutting planes compared to original relaxed solution.
MIQL.rlxoptRelaxed optimal value.
MIQL.gencutNonzero if cuts were generated.

qlTL

Purpose

Solves strictly convex quadratic programming problems.

QL solves problems of the form


\begin{array}{ll}
\min\limits_{x} & f(x) = \frac{1}{2} x^T F x + c^T x\\
&  \\
s/t & \begin{array}{lcccl}
x_{L} & \leq & x & \leq & x_{U} \\
b_{L} & \leq  & A x  & \leq & b_{U} \\
\end{array}
\end{array}


where c, x, x_L, x_U \in \mathbb{R}^n, F \in \mathbb{R}^{n \times n} and positive definite, A \in \mathbb{R}^{m_1 \times n}, and b_L,b_U \in \mathbb{R}^{m_1}.

Calling Syntax

Prob = qpAssign( ... );
Result = tomRun('ql',Prob,...);

Description of Inputs

Prob Problem description structure. The following fields are used:

FieldDescription
x_L, x_UBounds on variables.
b_L, b_UBounds on linear constraints.
ALinear constraint matrix.
QP.c Linear coefficients in objective function.
QP.F Quadratic matrix of size n x n.
PriLevOptPrint Level in solver (0 = off, 1 = only final error message).
QL.epsDesired final accuracy. The parameter value should not be smaller than the underlying machine precision.
QL.PrintFile Name of print file. Amount/print type determined by optPar(1). Default name ql.txt.

Description of Outputs

Result Structure with result from optimization. The following fields are set:

OutputDescription
ResultThe structure with results (see ResultDef.m).
f_kFunction value at optimum.
x_kSolution vector.
x_0Initial solution vector.
g_kExact gradient computed at optimum.
xStateState of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3;
bStateState of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3;
v_kLagrangian multipliers (for bounds + dual solution vector).
ExitFlagExit status from ql.m (similar to TOMLAB).
InformQL information parameter.

0 - Optimal solution with unique minimizer found

1 - Too many iterations

2 - Accuracy insufficient to attain convergence

3 - Internal inconsistency, division by zero

5 - An input parameter was invalide

> 100 - Constraints are inconsistent and Inform=100+iCon where iCon denotes the index of the constraint causing the conflict. The problem has no feasible solution.

rcReduced costs. If ninf=0, last m == -v_k.
IterNumber of iterations.
FuncEvNumber of function evaluations. Set to Iter.
GradEvNumber of gradient evaluations. Set to Iter.
ConstrEvNumber of constraint evaluations. Set to 0.
QP.BBasis vector in TOMLAB QP standard.
MinorIterNumber of minor iterations. NOT SET.
SolverName of solver (ql).
SolverAlgorithmDescription of the solver.
Retrieved from "http://tomwiki.com/MISQP"
Personal tools