Back BFOUR

Branch-and-Bound

Version 3.2 (2015)

Purpose

BFOUR solves mixed-integer optimization problems subject to linear equality and inequality constraints by a branch-and-bound method.

Numerical Method

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

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

Special Features

  • general framework for integer optimization
  • reverse communication
  • full documentation by initial comments
  • FORTRAN source code (close to F77, conversion to C by f2c possible

Applications

BFOUR is an essential part of the mixed-integer quadratic programming routine MIQL.

Reference