Understanding Branch and Bound in Optimization Problems
1. Introduction
Let me give you some background of optimization based problems before talking about Branch and Bound. Most of the businesses attempt to achieve maximum output with minimal input ( for instance realizing maximum profit by investing the least amount of capital ). Not only businesses, we as individuals also try to optimize our personal goals. Take the example of weight loss. Due to our busy schedules, we do not have much time to run long distances on a daily basis. We can increase the calorie burn per minute of mobility by avoiding lifts and taking the staircases. We can also complement this with a balanced diet. Walmart too has a variety of business problems that require similar kind of optimization ranging from setting a minimum price for items for customers without losing out on the target profits, optimizing the items availability in the inventory, figuring out the best routes for technicians for open tickets across the stores and store selection for running campaigns and remodeling of stores. The basic formulation of these problems remains the same i.e maximize/minimize your objective while following other constraints. The branch of mathematics which deals with these problems is called linear programming. Linear programming (also called linear optimization ) is a mathematical modeling technique used to achieve the best outcome (such as maximum profit or lowest cost) whose requirements are represented by linear expressions or relationships.
In this blog, I will take you through the working of the Branch and Bound method on a basic integer linear programming problem example and extend the same to a common staffing problem faced by many businesses using the PULP python library. Happy Reading!
2. What is Branch and Bound?
Let us take an example of a basic optimization problem
Here x1 and x2 are the unknowns. The objective is to maximize y which is a function of x1 and x2. Solving this graphically will give us the feasible region as shown below.
Consider the lines 5x1 + 9x2 = 45 and x1 + x2 = 6. As both the constraints have less than equal to the condition, the area marked in green towards the origin is the feasible region.
Solving for the equations
5x1 + 9x2 = 45
and x1 + x2 = 6
gives
x1 = 2.25 and x2 = 3.75 for the intersection point E
Now we have 5 points with respective values of y ( 5x1 + 8x2 )
O ( x1 = 0, x2 = 0 ), y = 5*0 + 3*0 = 0
A ( x1 = 0, x2 = 5), y = 5*0 + 3*5 = 15
B ( x1 = 0, x2 = 6 ), y = 5*0 + 3*6 = 18
C ( x1 = 6, x2 = 0 ), y = 5*6 + 3*0 = 30
D ( x1 = 9, x2 = 0 ), y = 5*9 + 3*0 = 45
E ( x1 = 2.25, x2 = 3.75 ), y = 5*2.25 + 3*3.75 = 41.25
D ( y= 45 ) is maximum. However, it is not in the feasible region, next largest value is E, which gives the value of y i.e 41.25.
This means x1 = 2.25 and x2 = 3.75 is the best solution among these.
You can see that both the values are non-integers. Think about the business problems where the technician's hours or whether a store is selected or not are all discrete. In these scenarios where the solution has to take discrete values, we need to add another constraint to the problem.
x1 and x2 are integers.
The above approach will not assure integer solutions. Now branch and bound will come to play!
If only one of them is integers, then we will start branching the non-integer value to get the next best integer. In this case, none of them is integers. We will have to start branching the bigger number i.e x2 = 3.75 as per the algorithm. Consider both sides of this value of x2.
x2 ≤ 3 and x2 ≥ 4
This will give two subproblems SP1 ( x2 ≤ 3 ) and SP2 ( x2≥4 ).
SP1 can be graphically represented as shown below
Solving SP1 gives x1 = 3 and x2 = 3 and corresponding y ( 5x1 + 8x2 ) will be 39
SP2 can be graphically represented as shown below
Solving SP2 gives x1 = 1.8 and x2 = 4 and corresponding y ( 5x1 + 8x2 ) will be 41
The left branch has both the roots as integers so we will bound it. The right branch will be further branched as one of the roots x1 is still not an integer. Consider both sides of this value of x1.
x1 ≤ 1and x1 ≥ 2
This will give two subproblems SP3 ( x1 ≤ 1) and SP4 ( x1≥2 ).
Solving SP3 gives x1 = 1 and x2 = 4.44 and corresponding y ( 5x1 + 8x2 ) will be 40.5.
x2 is not an integer, so this will be further branched. This will give two subproblems SP5 ( x2 ≤ 4) and SP6 ( x2≥5).
Solving SP4 gives x1 = 2 and x2 = 4 and corresponding y ( 5x1 + 8x2 ) will be 42. However, there is no feasible region in the graph. This sub-problem is discarded and will not be considered for the final solution.
The next step is to solve for SP5 and SP6 in a similar pattern.
For SP5, the feasible region is the line x2 = 4 and the solution is x1 =1 and
x 2 =4. The corresponding value of y is 37
For SP6, the feasible region is the line x2 = 5and the solution is x1 =0 and
x 2 =5, for maximum value of y i.e 40.
No, we will compare the value of the objective function of all the leaf nodes i.e SP1, SP5 and SP6 with feasible solutions.
As SP6 is giving y = 40 which is the maximum among all of the leaf nodes,
x1 = 0 and x2 = 5 is the optimal solution!!
Example1: Sample Toy Problem Implementation in python using PULP
PuLP is a linear programming modeler written in Python. It is an open source package that allows mathematical programs to be described in the Python programming language. It is a high-level modeling library that leverages the power of the Python language and allows users to create programs using expressions that are natural to the Python language, avoiding special syntax and keywords wherever possible. The syntax is quite easy to write and interpretable for many of the common business problems. It also makes it very easy to translate a business problem into objective functions and constraints using PULP.
Let us first try to solve a toy example used in section 2.
I will not be going into the details of the PULP library here. For a detailed tutorial, you refer to this link.
- After you install the PULP library, start with the import.
from pulp import *
2. Create a problem variable to declare this as a maximize problem as per the problem definition.
# Create the ‘prob’ variable
prob = LpProblem(“Test Problem”,LpMaximize)
3. Declare the two problem variables x1 and x2 as integers. The lower limit is zero and the upper limit is ‘None’.
# Variables x1 and x2 are created with a lower limit of zero and declared as integers
x1=LpVariable(“var1”,0,None,LpInteger)x2=LpVariable(“var2”,0,None,LpInteger)
4. Define the objective function
# The objective function is added to ‘prob’ first
prob += 5*x1 + 8*x2, “maximum output”
5. Add the two constraints
# The two constraints are added
prob += 5*x1 + 9*x2 <= 45, “constraint1”
prob += x1 + x2 <= 6, “constraint2”
6. Run the solve function. This step runs the branch and bound algorithm steps discussed in section 2 of this blog
# The problem data is written to a .lp file
prob.writeLP(“test_model.lp”)
# The problem is solved using PuLP’s choice of Solver
prob.solve()
7. Check the status of the solution. If this returns optimal, this means you have at least 1 feasible solution in one of your leaf nodes
# The status of the solution is printed on the screen
print (“Status:”, LpStatus[prob.status])
8.Print the roots/solution of the problem
# Each of the variables is printed with its resolved optimum value
for v in prob.variables():
print (v.name, “=”, v.varValue)
You will observe that you get the same solution i.e x1 = 0 and x2 = 5. This matches with what we got in section 2 with the manual calculation!
You can see the whole code below -
Example 2: Staffing problem in Store Remodelling
Remodeling is one of the major responsibilities of any facilities department. For this exercise, a lot of resources have to be deployed to the store requiring remodeling.
Assume, a major remodel of a warehouse is planned. As part of first phase, there are a lot of plumbing and electrical tasks and many tickets are in the open state. Here are few important considerations:
The operations manager wants to close as many tickets as possible within a span of 80 days.
Technicians working hours are from 10 am to 4 pm i.e 6 hours a day. It takes 2 hours to close a plumbing ticket as compared to 3 hours for an electrical ticket.
At one point in time, only one of the technicians ( either one plumber or one electrician ) can work in the store so that it does not impact the daily operations and the nature of the remodeling tickets.
The store operations manager wants to close a minimum of 5 electrical and 2 plumbing tickets during these 80 days.
The difference between the count of electrical and plumbing tickets closed should not be more than 10.
The number of hours worked by each technician should be an integer as the system can only capture the duration in discrete hour values ( minute level details are not possible ).
Let us try to understand the solution approach and implementation in PULP step by step.
- After you install the PULP library, start with the import.
from pulp import *
2. Create a problem variable to declare this as a maximize problem as per the problem definition. We want to maximize the number of tickets closed.
# Create the ‘prob_tech_staffing’ variable
prob_tech_staffing = LpProblem(“technician staffing”,LpMaximize)
3. Declare the two variables hours worked by Electricians hrsE and hours worked by Plumbers hrsP as integers as mentioned in the problem statement.
# The two variables hours worked by Electricians hrsE and hours worked by Plumbers hrsP are created with a lower limit of zero and declared as integers.
hrs_P=LpVariable(“hours plumbers have to work in the store”,1, None, LpInteger)
hrs_E=LpVariable(“hours electricians have to work in the store”,1, None, LpInteger)
4. The objective of the problem has to be declared next. The goal is to close the maximum number of tickets within the specified period of 80 days.
Total hours worked by electrician -> hrsE
Total hours worked by plumber -> hrsP
Total electrical tickets = hrsE/3
Total plumbing tickets = hrsP/2
Total Tickets = hrsE/3 + hrsP/2
Let us call our objective function as
count_tickets = hrsE/3 + hrsP/2
Maximize count_tickets is the objective.
# The objective function is added to ‘prob_tech_staffing’ first
prob_tech_staffing += (hrsE/3) + (hrsP/2), “maximum number of tickets based on the maximum number of hours worked upon by Electricians and Plumbers”
5. Let us add the constraints now
a) Minimum 5 Electrician tickets to be closed
Total number of electrical tickets = Total number of hours worked by Electrician divided by 2 ( hours required to close one electrical ticket ) i.e hrsE/2 ≥ 5
This can be represented as hrsE >= 5 * 3
prob_tech_staffing += hrsE >= 5*3, “Minimum 5 Electrician tickets to be closed “
b) Minimum 2 Plumbing tickets to be closed
Similar to previous constraint
prob_tech_staffing += hrsP >= 2 * 2, “Minimum 2 Plumbing tickets to be closed “
c) Maximum 480 hours( 6 hours* 80 days ) available
prob_tech_staffing += hrsE + hrsP <= 480 , “Maximum 480 hours( 6 hours* 80 days ) available “
d) Difference between Electrical and Plumbing count should not be more than 10
As it takes 2 hours to close a plumbing ticket as compared to 3 hours for an electrical ticket.
#hrsE/3 — hrsP/2 <=10
After doing cross multiplication we get
#2*hrsE — 3*hrsP <= 60
prob_tech_staffing += 2*hrsE — 3*hrsP <= 60 , “Difference between Electrical and Plumbing count should not be more than 10”
Similarly, one more constraint is added
#hrs_P/2 — hrs_E/3 <= 10
#3*hrs_P — 2*hrs_E <= 60
prob_tech_staffing += 3*hrs_P — 2*hrs_E <= 60 , “Difference between Plumbing and Electrical count should not be more than 10”
6. Let us run the branch and bound now.
# The problem data is written to an .lp file
prob_tech_staffing.writeLP(“tech_staffing_model.lp”)
# The problem is solved using PuLP’s choice of Solver
prob_tech_staffing.solve()
# The status of the solution is printed to the screen
print (“Status:”, LpStatus[prob_tech_staffing.status])
# Each of the variables is printed with it’s resolved optimum value
for v in prob_tech_staffing.variables():
print (v.name, “=”, v.varValue)
Running this will give you this output:
Solving this gives
Number of hours electrician have to work: 276
Number of hours plumber have to work: 204
Total tickets which can be completed = hrsE/3 + hrsP/2
i.e 100 tickets can be completed in 80 days given the electrician and technician will be spending 276 and 204 hours respectively in the store.
As the variables hrsE and hrsP are integers, branch and bound is the backbone of the optimization algorithm. More details about how the algorithm works will be discussed in the later sections.
This means a maximum of 276/3 = 92 electrical tickets and 204/2 = 102 plumbing tickets can be closed during these 80 days! You can validate all the declared constraints for this solution.
See the whole code below -
This problem formulation can be extended to more complex scenarios like paid time off, ad hoc meetings, flexible working hours, travel time between stores for multiple store scenarios, tickets that need multiple technicians at a time, handling of emergency tickets, variation in time required for different tickets and handling multiple other trades like landscaping, wall painting, installation of security devices, garbage clearing etc.
5. Conclusion
I hope I was able to explain the nitty-gritty of branch and bound, one of the core algorithms to solve integer linear programming problems which is also used by many popular packages like PULP, CVXPY, etc. You have also seen how to solve a toy problem and a more realistic business problem using the PULP library in python. These formulations are a good starting point to cater to more complex real world problems.
Start thinking about business problems like
-> real-time workforce scheduling for multiple parallel tasks or
-> setting an optimal price for a perishable product at every stage of its lifecycle on the shelf or
-> how to plan a balanced diet without compromising on the variety, allergies or choices or
-> how to optimize the ingredients of a canned eatable for best nutrition!
6. References
https://www.coin-or.org/PuLP/main/optimisation_concepts.html
