The goal is to implement a branch and bound algorithm. We will have two types of branch and bound algorithms to code.
-
The first algorithm will be based on the Schrage technique to find upper and lower bounds at each branch node. Everything will be based on this Schrage procedure. At each node we will have to do this procedure and a criterion will allow us to branch.
-
a second branch and bound algorithm can be based on mixed programming. It is in fact the classical version of this algorithm. At each node we consider a linear relaxation, which we solve (dual simplex/simplex algorithm).