MISQP

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.

TOMLAB /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.

TOMLAB /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

• #Introduction provides a basic overview of the TOMLAB /MISQP solver package.
• #Using the Matlab Interface provides an overview of the Matlab interface to MISQP.
• #Setting MISQP Options describes how to set MISQP solver options from Matlab.
• #MISQP Solver Reference gives detailed information about the interface routine misqpTL.
• #MIQL Solver Reference gives detailed information about the interface routine miqlTL.
• #QL Solver Reference gives detailed information about the interface routine qlTL.

More information

Please visit the following links for more information:

• http://tomopt.com/tomlab/products/misqp/

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.

Function	Description
misqpTL	The interface routine called by the TOMLAB driver routine tomRun. This routine then calls the MEX file misqp
miqlTL	The interface routine called by the TOMLAB driver routine tomRun. This routine then calls the MEX file miql
qlTL	The 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.

Function	Description	Reference
ql	Quadratic programming using a primal-dual method with cholesky decomposition.	qlTL.m
miql	Mixed-integer quadratic programming using a branch-and-cut method with ql as subsolver.	miqlTL.m
misqp	Constrained, 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:

Description of Outputs

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

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}Fx+c^{T}x\\&\\s/t&{\begin{array}{lcccl}&&x&&,\\b_{L}&\leq &Ax&\leq &b_{U}\\\end{array}}\end{array}}$

where $c,x\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} ^{n+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:

Description of Outputs

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

qlTL

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}Fx+c^{T}x\\&\\s/t&{\begin{array}{lcccl}&&x&&,\\b_{L}&\leq &Ax&\leq &b_{U}\\\end{array}}\end{array}}$

where $c,x\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} ^{n+m_{1}}$.

Calling Syntax

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

Description of Inputs

Prob Problem description structure. The following fields are used:

Description of Outputs

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