branch and bound method

branch and bound method is a solution approach that can be applied to a number of different types of problems. It is based on the principle that the total set of feasible solutions can be partitioned into smaller subsets of solutions, which can then be evaluated systematically until the best solution is found. Essentially it’s a divide and conquer strategy to iteratively reduce the solution space.

When used for integer programming problems, it’s used in addition to non-integer solution approach like in linear programming.

Key concepts

Process for a integer programming maximization problem

From Taylor, B.W. (2019). Introduction to Management Science, Global Edition (13e) Companion Module C: Integer Programming: The Branch and Bound Method. New York: Pearson. Pages C2-C9

Given the integer programming maximization problem

the resulting enumeration tree is:

1. Find the optimal solution to the linear programming model with the integer restrictions relaxed. e.g., Node 1
2. At any node let
   1. the relaxed solution to the relaxed linear programming be the upper bound
   2. the best integer solution (at any node) solution be the lower bound . It’s the value of best known feasible solution (if none known, round down the upper bound, e.g., node 1 round down (2.22, 5.56) to (2, 5))
   3. the optimal integer solution should be between these bounds
3. Select the variable with the greatest fractional part for branching (so the solution space is smaller). Create two new constraints for this variable reflecting the partitioned integer values: one constraint and one constraint
4. Create two new nodes, one for the constraint and one for the constraint . The constraints from parent nodes should follow. Solve the relaxed linear programming model with the new constraint added at each of these nodes.
5. See step 2 to establish upper and lower bounds after solving
6. If a feasible integer solution does not emerge, branch from the node with the greatest upper bound. e.g, from node 3 instead of node 2 since
7. Node ends (i.e. the node with relaxed linear programming has been fathomed) if ONE of the following conditions is met:
   1. the linear program over is infeasible, like nodes 5 and 7
   2. the optimal linear programming solution over is integer, like node 6 where the variables x1 x2 are integers
   3. the value of the linear programming solution over doesn’t exceed the best-known integer solution
8. The optimal integer solution is reached e.g., node 6
   1. a node ends with an integer solution that meets both bounds, AND
   2. NO OTHER feasible branches could yield a better integer solution.
9. Otherwise, return to step 2.

For a minimization model, relaxed solutions are rounded up, and upper and lower bounds are reversed.

Example

(PCW Debrief)

# !pip install cvxopt
 
import cvxpy as cp
from cvxopt import glpk
 
#Initialize the variables
x, y = cp.Variable(integer=True), cp.Variable(integer=True)
 
#Create objective function
objective = cp.Maximize(5*x + 4*y)
 
#Initialize constraints
constraints = [3*x + 4*y <= 10, x>=0, y>=0]
 
problem = cp.Problem(objective, constraints)
 
#Solve our problem
problem.solve(solver='GLPK_MI')
 
#Show optimal values
print(problem.value)
print(x.value, y.value)