Creating a Branch-and-Bound Algorithm

Table of Contents

• Basics
• More Advanced Topics

Describes how to create a branch-and-bound algorithm.

The branch-and-bound algorithm is a very well-known approach to solve combinatorial problems. It is a divide and conquer type of algorithms. For an introduction, please refer to the Wikipedia page or to the book Integer Programming.

Warning

The rest of this tutorial assumes a basic understanding of branch-and-bound procedures.

Basics

Writing a branch-and-bound algorithm with idol can be done using the BranchAndBound<NodeTypeT> class. This is a template class where the template argument, NodeTypeT, is the class that stores the information of each node in the tree. If none is specified, the default one is picked, i.e., DefaultNodeInfo. This class is more than enough for classic LP-based branch-and-bounds.

Then, at least three ingredients need to be provided in order to set up the algorithm:

• An optimizer, for solving each node;
• A node selection rule, for choosing which node to be solved next;
• A branching rule, for choosing how to branch on a node whose solution is not feasible for the original problem.

Clearly, the BranchAndBound class can be used to create any sort of branch-and-bound algorithm. To streamline the discussion, however, we will focus on a branch-and-bound algorithm for solving an MILP, based on the LP relaxation.

To start with, we give a minimal example for constructing such a branch-and-bound method. Assume to have an object called model of the class Model, storing your MILP. Here is how to define a branch-and-bound method to solve it.

// Create the algorithm
auto branch_and_bound = BranchAndBound();
 
// Set the optimizer used to solve the nodes
branch_and_bound.with_node_optimizer(Gurobi::ContinuousRelaxation());
 
// Set the node selection rule
branch_and_bound.with_node_selection_rule(BestBound());
 
// Set the branching rule
branch_and_bound.with_branching_rule(MostInfeasible());
 
// Use the optimizer
model.use(branch_and_bound);
 
// Solve
model.optimize();

Pretty easy no? Beware, however, that we are using here the Gurobi::ContinuousRelaxation() optimizer, and not Gurobi(). This is because Gurobi() would not relax the integrality requirements by default and solve the node's problem directly as a MILP. Here, we really want to solve each node by means of the continuous relaxation of the problem at that node.

More Advanced Topics

In the following sub-pages, we give a more in-depth description for these basic ingredients as well as more advanced features like callbacks, presolve, cutting planes, etc.

• Node Selection Rules
• Branching Rules
• Callbacks (TODO)
• Presolve
• Cutting Planes (TODO)
• Heuristics (TODO)
• Using Your Own Node Type (TODO)
• Other Options (TODO)