Back
MIQL

Mixed-Integer Quadratic Programming

Version 3.3 (2014)

## Purpose

MIQL solves strictly convex mixed-integer quadratic programming problems subject to linear equality and inequality constraints by a branch-and-cut method. The continuous subproblem solutions are obtained by the primal-dual method of Goldfarb and Idnani. The code is designed for solving small to medium size mixed-integer programs.

## Numerical Method

At the root node of the branch-and-bound search tree, disjunctive and complemented mixed-integer rounding cuts are generated. A branch-and-bound strategy is implemented where different options are available for selecting a branching variable and a free node:

maximal fractional branching | Select an integer variable from the solution of the relaxed subproblem with largest distance from next integer value. |

minimal fractional branching | Select an integer variable from the solution of the relaxed subproblem with smallest distance from next integer value. |

Then we search for a free node from where branching, i.e., the generation of two new subproblems, is started:

best of two | The optimal objective function values of the two
child nodes are compared and the node with a lower value is chosen. If
both are leafs, i.e., if the corresponding solution is integral, or if
the corresponding problem is infeasible or if there is already a better
integral solution, strategy best of all is started. |

best of all | Select an integer variable from the solution of the relaxed subproblem with smallest distance from next integer value. |

depth first | Selects a child node whenever possible. If the node
is a leaf the best of all strategy is applied. |

## Program Organization

MIQL is a FORTRAN subroutine where all data are passed by subroutine arguments.

## Special Features

- separate handling of upper and lower bounds
- exploiting dual information for early branching
- warm starts
- full documentation by initial comments
- FORTRAN source code (close to F77, conversion to C by f2c possible)

## Applications

## Reference

- M.J.D. Powell, On the quadratic programming algorithm of Goldfarb and Idnani, Report DAMTP 1983/Na 19, University of Cambridge, Cambridge (1983)
- T. Lehmann, K. Schittkowski, MIQL: A Fortran code for convex mixed-integer quadratic programming - User's guide, Report, Department of Computer Science, University of Bayreuth (2009)