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.
The corresponding continuous relaxed problems are solved by the FORTRAN 77 code QL, an implementation of a primal-dual method. The internal matrix transformations are performed in numerically stable way. A special variant of the branch-and-bound solver BFOUR is included.

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

As an essential part of the mixed-integer nonlinear programming routine MISQP, MIQL solves the internal mixed-integer quadratic programming subproblems of the SQP-trust-region method.

Reference