MISQP: Difference between revisions
Line 167: | Line 167: | ||
''Prob ''Problem description structure. The following fields are used: | ''Prob ''Problem description structure. The following fields are used: | ||
{|class="wikitable" | |||
!Field||Description | |||
|-valign="top" | |||
|''x_L, x_U''||Bounds on variables. | |||
|-valign="top" | |||
|''b_L, b_U''||Bounds on linear constraints. | |||
|-valign="top" | |||
|''A''||Linear constraint matrix. | |||
|-valign="top" | |||
|''QP.c ''||Linear coefficients in objective function. | |||
|-valign="top" | |||
|''QP.F ''||Quadratic matrix of size n x n. | |||
|-valign="top" | |||
|''PriLevOpt''||Print 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. | |||
|-valign="top" | |||
|''MIP.IntVars''||Vector of indices of the integer variables. | |||
|-valign="top" | |||
|''MIQL.PrintFile ''||Name of MIQL print file. Amount and type of printing determined by PriLevOpt. Default name ''miql.txt''. | |||
|-valign="top" | |||
|''MIQL.eps''||Desired final accuracy. The parameter value should not be smaller than the underlying machine precision. | |||
|-valign="top" | |||
|''MIQL.acc''||The 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. | |||
|-valign="top" | |||
|''MIQL.ibr''||Branching rule | |||
1 - Maximal fractional branching (default). | |||
2 - Minimal fractional branching. | |||
|-valign="top" | |||
|''MIQL.ins''||Node 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.) | |||
|-valign="top" | |||
|''MIQL.maxnde''||Maximal number of nodes, e.g., 100,000. | |||
Default: (2*n + 2*m + 6)^2 for cut == 1,3), (2*n + m + 4)^2 otherwise. | |||
|-valign="top" | |||
|''MIQL.wstart''||Maximal number of successive warmstarts to avoid numerical instabilities. Default 100. | |||
|-valign="top" | |||
|''MIQL.impb''||1 - Calculate improved bounds when best-of-all node selection strategy (ins = 1) is used. | |||
0 - Default. | |||
|-valign="top" | |||
|''MIQL.dfdir''||1 Select direction for depth-first node selection strategy (ins = 3) according to value of Lagrange function. | |||
0 - Default. | |||
|-valign="top" | |||
|''MIQL.cholm''||Cholesky decomposition mode. | |||
0 - Calculate Cholesky decomposition once and reuse it. | |||
1 - Calculate new Cholesky decomposition whenever warmstart is not active. Default. | |||
|-valign="top" | |||
|''MIQL.cut''||Control 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. | |||
|-valign="top" | |||
|''MIQL.maxdc''||Maximal number of rounds for disjunctive cuts. Default 1, if disjunctive cuts should be generated. | |||
|-valign="top" | |||
|''MIQL.maxcm''||Maximal number of cuts for CMIR cuts. Default 1, if CMIR cuts should be generated. | |||
|-valign="top" | |||
|''MIQL.phm''||Primal heuristic mode. | |||
0 - No primal heuristics. Default | |||
1 - Nearest integer. | |||
2 - Feasibility pump. | |||
|} | |||
====Description of Outputs==== | ====Description of Outputs==== |
Revision as of 04:10, 14 August 2013
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:
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
where , and and , Furthermore, 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
where , and positive definite, , and .
The variables , the index subset of , are restricted to be integers.
If F is empty, an LP or MILP problem is solved.
Calling Syntax
Prob = miqpAssign( ... ); Result = tomRun('miql',Prob,...);
Description of Inputs
Prob Problem description structure. The following fields are used:
Field | Description |
---|---|
x_L, x_U | Bounds on variables. |
b_L, b_U | Bounds on linear constraints. |
A | Linear constraint matrix. |
QP.c | Linear coefficients in objective function. |
QP.F | Quadratic matrix of size n x n. |
PriLevOpt | Print Level 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.IntVars | Vector 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.eps | Desired final accuracy. The parameter value should not be smaller than the underlying machine precision. |
MIQL.acc | The 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.ibr | Branching rule
1 - Maximal fractional branching (default). 2 - Minimal fractional branching. |
MIQL.ins | Node 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.maxnde | Maximal 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.wstart | Maximal number of successive warmstarts to avoid numerical instabilities. Default 100. |
MIQL.impb | 1 - Calculate improved bounds when best-of-all node selection strategy (ins = 1) is used.
0 - Default. |
MIQL.dfdir | 1 Select direction for depth-first node selection strategy (ins = 3) according to value of Lagrange function.
0 - Default. |
MIQL.cholm | Cholesky decomposition mode.
0 - Calculate Cholesky decomposition once and reuse it. 1 - Calculate new Cholesky decomposition whenever warmstart is not active. Default. |
MIQL.cut | Control 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.maxdc | Maximal number of rounds for disjunctive cuts. Default 1, if disjunctive cuts should be generated. |
MIQL.maxcm | Maximal number of cuts for CMIR cuts. Default 1, if CMIR cuts should be generated. |
MIQL.phm | Primal 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:
Output | Description |
---|---|
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 | 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 miql.m (similar to TOMLAB). |
Inform | MIQL 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. |
rc | Reduced costs. If ninf=0, last m == -v_k. |
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 solver (miql). |
SolverAlgorithm | Description of the solver. |
MIQL.cutges | Total number of cutting planes. |
MIQL.nodes | Total number of branch and bound nodes. |
MIQL.ctime | Time spent generating cutting planes. |
MIQL.bbtime | Time spent for branch and bound process. |
MIQL.cutgap | Gap reduced by cutting planes compared to original relaxed solution. |
MIQL.rlxopt | Relaxed optimal value. |
MIQL.gencut | Nonzero if cuts were generated. |
qlTL
Solves strictly convex quadratic programming problems.
QL solves problems of the form
where , and positive definite, , and .
Calling Syntax
Prob = qpAssign( ... ); Result = tomRun('ql',Prob,...);
Description of Inputs
Prob Problem description structure. The following fields are used:
Field | Description |
---|---|
x_L, x_U | Bounds on variables. |
b_L, b_U | Bounds on linear constraints. |
A | Linear constraint matrix. |
QP.c | Linear coefficients in objective function. |
QP.F | Quadratic matrix of size n x n. |
PriLevOpt | Print Level in solver (0 = off, 1 = only final error message). |
QL.eps | Desired 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:
Output | Description |
---|---|
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 | 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 ql.m (similar to TOMLAB). |
Inform | QL 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. |
rc | Reduced costs. If ninf=0, last m == -v_k. |
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 solver (ql). |
SolverAlgorithm | Description of the solver. |