Linear programming: Integer Linear Programming with Branch and Bound
Up until now in this series, we've talked about strict Linear Programming – where the objective function, constraints and decision variables have all been linear and continuous. This linear set up comes with some really nice properties, but it isn't very flexible. In this article, I'll discuss how we can allow for discrete decision variables using a tool called integer linear programming (ILP).
This is the fourth article in a series I'm writing on linear programming. The other articles (including an introduction – in case you aren't familiar with linear programming) can be found here:
In this article we'll be covering the following topics:
- When discrete decision variables are needed
- How the branch and bound algorithm solves integer linear programming problems
- The pros and cons of integer linear programming compared to regular linear programming
- Solving an ILP problem in Python
Why discrete decision variables are needed
Discrete decision variables can be required in an Optimization for two reasons:
- The nature of a variable is discrete
- To handle conditional logic and ‘or' logic
We'll get into the details of these two reasons below!
The nature of the variable is discrete
Often, decision variables that we are modelling are discrete in nature and won't be well modelled with continuous variables. Here are some examples of discrete decision variables:
- Turning a machine on or off in a production process – represented with discrete, binary variables
- Scheduling staff to be in or out of office – represented with discrete binary variables
- Planning fire station locations— specific locations can be represented with discrete variables
- Purchasing large items – the number of items to purchase can be represented by a discrete variable
- Product production plans – the number of each type of product created can be represented by discrete variables
When the nature of a decision variable is discrete, you have two options on how to handle it — (1) treat it as continuous or (2) treat it as discrete. Treating a discrete variable as continuous has the distinct advantage of allowing you to use traditional LP optimization (which has multiple benefits we will discuss in the next section). But, it comes at the cost of potentially modelling the variable poorly. Treating the variable as discrete will require you to use the less-powerful ILP optimization, but will model the ‘real world' better.
As a rule of thumb, if a variable is well-approximated by a decimal, you can model it as continuous. For example, the number of nails a factory produces might be well approximated by a decimal — 1,000,000 nails is a pretty good approximation of 1,000,000.35 nails. If the variable is not well approximated by a decimal, then you will probably have to go the integer route. Binary variables fall into this category, 0.35 is not a good approximation of 0 and 0.75 is not a good approximation of 1. Additionally, variables that tend to take on lower volume won't do well. Imagine a business that makes a handful of mobile homes every month — 11 mobile homes is probably not a good approximation of 10.63 mobile homes.
Two things can go wrong if you incorrectly treat a discrete variable as a continuous variable:
- You can get suboptimal solutions – rounding to an integer forfeits the guarantee of an optimal solution
- You can get infeasible solutions – rounding can put the solution outside of the feasible solution space. e.g., mobile homes cost $10k to make, you have a budget of $105,000 – the LP solution says to create 10.5 units. You round that up to 11 units and now you are over budget!
Handle conditional logic and ‘or' logic
The regular linear programming can't handle complex relationships in the constraints and objective functions. It can only work with ‘and' logic. For example: X1 < 10 AND X2 < 20. There are a lot of scenarios where ‘or' logic is needed. For example, imagine a micro chip manufacturing plant that receives government grants. To be eligible for the grants, they need to make 1000 ‘A' chips OR 800 ‘A' chips. Traditional linear programming could not optimize this logic. ILP can handle the logic by introducing binary auxiliary variables. These binary variables can be used to turn on and off constraints based on the values of the other decision variables. The fact that it has to be binary requires the use of ILP instead of LP.
Binary auxiliary variables can also be used to capture non-linear jumps in constraints. Imagine you are scheduling staff for a call center – your goal is to have coverage for the estimated call volume while minimizing salary cost. After 40 hours, employees will receive over-time pay. Traditional LP can't handle this type of jump, the use of a binary auxiliary variables can. And of course, if we introduce a binary variable, we are now in the space of ILP. Going over the specifics of how to set up auxiliary variables will be covered in another article. For now, it is sufficient to say that binary auxiliary variables can capture these complexities.
How the branch and bound algorithm solves ILP problems
I hope you have a good idea of why we often need to use integers in linear programming problems. The presence of integers in a problem necessitates that we use integer linear programming. The most popular algorithm for solving ILPs is called ‘branch and bound.' Let's jump into how branch and bound works.
The branch and bound algorithm splits an ILP into multiple LP sub-problems (that's the branching part). It uses information learned from some sub-problems to skip over other sub-problems (that's the bound part) — this saves computation and avoids an exhaustive search. I think it's hard to conceptualize a verbal description of the algorithm, how about an example?
We are going to solve the ILP below using the branch and bound algorithm:
Step 1: Relax the integer constraint and solve the LP problem
This is easy enough, we just allow x and y to take continuous values and solve – as I covered in previous articles, LP problems can generally be solved quickly and easily via the simplex method.
With the relaxation of the integer requirement, we easily get a solution of x = 2.25, y = 3.75 with a maximized objective value of 52.5. At the end of every step in branch and bound, we check to see if the solution is a feasible integer solution – if it is we don't branch, if it isn't, we branch. Clearly we do not meet the integer solution criteria since neither x or y are integers. So now we move on to branching!
Step 2: Pick an integer variable that doesn't have an integer solution and branch it into two sub-LP problems
Given our solution from the prior step, we split our single LP problem into two sub-problems. We do this by picking a variable (we can pick either one) — here, we'll pick x, creating two LPs with extra constraints on that variable. The constraints we set are determined by the result of the solution in the prior step. For our example, we'll make one LP problem with the new constraint x ≤ 2 and another with the constraint x ≥ 3 added. Note that since we are interested in integer solutions, setting the constraints to 2 and 3 doesn't cut out any part of the solution space from the original problem (the numbers between 2 and 3 are non-integers). We then solve the new LP problems.
Step 3: Continue to iterate conditional on the input from the prior step
After the first two steps, we are now set to continue making iterative branches based on the results of the prior steps. At each iteration, one of three things can happen. The table below shows what can happen and what the algorithm does for each event:
We continue following this algorithm until all branches are finished. At this point, we take the best integer solution found and return this as the optimal solution.
It is a little difficult to conceptualize the algorithm without a visualization. I hope my description has put you in a good place to understand the visual walk-through below.
Note that because each level of the tree adds additional constraints, we know that the objective value will get lower as we go down (more constraints generate lower objective values). That is why we know that we don't have to continue down the x ≥ 3 branch even though we could create two sub-problems splitting on y (y≤2 and y≥3). Since we know that nothing below the leaf can be higher than 50, we can ‘prune' the branch and not continue down.
The problem I picked for our first example was very simple. I'm going to put another ILP problem setup with the algorithm's visual execution below to give you some more exposure. I'll spare you the description of each step this time!
The moving image is good for understanding the sequence of the algorithm – here is the still image so you can take a closer look:
The pros and con of integer linear programming
The pros:
- Some problems are not well modeled with continuous linear equations, others flat out can't be modeled as LP problems at all. Integer programming allows for these cases.
- Because of the convex solution space of linear programming, ILP is guaranteed to find the global optimum.
The Con:
The main problem with ILP is that the branch and bound algorithm isn't very efficient — even though it is generally considered the best algorithm for ILP. For large problems, it can require a lot of computational resources and memory. Not all problem formulations will find optimal solutions in a reasonable amount of time — i.e., some ILP problems are not tractable.
Given that the primary challenge with ILP is execution, here are a few recommendations to help ILP run faster – note, not all of these potential solutions are possible for all ILP problems:
- Approximate integers with continuous variables when possible
- Try to use binary variables when possible — binary variables require fewer splits, which in turn make smaller trees
- Limit the number of variables (if possible) – the more variables, the more complex the solution space
Integer Linear Programming in Python
Okay, now that we know why we need integer linear programming and we understand how the branch and bound algorithm works, let's show how we can solve ILPs in Python. Using the ‘pulp' package in Python, ILP looks really similar to regular LP problems. Other articles in this series go into more details on setting up an LP problem with pulp. The only difference (for the end user of pulp at least) between ILP and LP is how the decision variables are set up. As you can see below, the ‘cat' attribute is set to ‘Integer' for both x and y. From this, pulp automatically solves the problem with a variant of the branch and bound algorithm because of the presence of integers in the decision variables.
import pulp
# Define the problem
problem = pulp.LpProblem("Maximize_Profit", pulp.LpMaximize)
# Define the decision variables as integers
x = pulp.LpVariable("x", lowBound=0, cat="Integer")
y = pulp.LpVariable("y", lowBound=0, cat="Integer")
# Objective function
problem += 10 * x + 8 * y, "Objective"
# Constraints
problem += x + y <= 6, "Constraint 1"
problem += 20 * x + 12 * y <= 90, "Constraint 2"
# Solve the problem
status = problem.solve()
# Output the results
print(f"Status: {pulp.LpStatus[status]}")
print(f"Optimal value of x: {x.varValue}")
print(f"Optimal value of y: {y.varValue}")
print(f"Maximized Profit: {pulp.value(problem.objective)}")The output from the code is pasted below – as you can see, it ties our results from our manual solving of the problem above!
Conclusion
Integer linear programming is a very important tool in the optimization tool box. It allows for the handling of discrete decision variables and complex logic amongst constraints. This additional flexibility comes with an extra computational cost compared to the classic linear programming optimization framework. Multiple things can be done to speed up ILP execution — these speed increasing helpers are problem dependent however. Despite some drawbacks, ILP is powerful in its flexibility and is a valuable and frequently used technique.
