MIQL - Mixed-Integer Quadratic Programming

 

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:

1. separate handling of upper and lower bounds
2. exploiting dual information for early branching
3. warm starts
4. full documentation by initial comments
5. 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:

	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)

Availability:

For more details contact the author or click here for free license for members and students of academic institutions.