BFOUR - Branch-and-Bound

 

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:

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