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

- B. Sachsenberg, NLPIP: A Fortran implementation of an SQP interior point method for solving large-scale nonlinear optimization problems - User's guide, Version 2.0, Report, Department of Computer Science, University of Bayreuth (2013)
- B. Sachsenberg, K. Schittkowski (2015): A combined SQP–IPM algorithm for solving large-scale nonlinear optimization problems, Optimization Letters, Vol. 9, 1271-1282