## 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.

The corresponding continuous relaxed optimization problems are to be solved by any available external solver.

Program Organization:
BFOUR is a FORTRAN subroutine where all data are passed by subroutine arguments.
Special Features:
1. general framework for integer optimization
2. reverse communication
3. full documentation by initial comments
4. 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:
 T. Lehmann, K. Schittkowski, BFOUR: A Fortran subroutine for integer optimization by branch-and-bound - User's guide, Report, Department of Computer Science, University of Bayreuth (2015)
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: