Mixed Integer Programming: A Straight Forward Tutorial

In a previous article (Linear Programming in Python: A Straight Forward Tutorial) I covered linear programming where we solved a factory production problem by defining a set of linear constraints and the variables were continuous. But what happens if the variables are not continuous? What should we do if we want to introduce decision variables? This is where Mixed Integer Programming comes in.

We will be using PuLP further in this tutorial if you want an installation guide for it you can look into the previous article for setting it up and defining basic functionality. Let’s first look at the problem statement again, adjusted a bit to see where Mixed Integer Programming may be useful.

Problem Statement

Imagine that you work for a company that builds computers. A computer is a fairly complex product, and there are several factories that assemble them which the company pays a certain amount per unit. The cost of this computer model on the market is fixed at 500$, different factories assemble the computers at different speeds and costs. Factory f0 produces 2000 per day at 450$ per unit, factory f1 1500 per day at 420$ per unit and f2 1000 per day at 400$ per unit. We have 1 month to assemble 80 000 units under the constraint that no factory is to produce more than double the units than any other factory. Only two factories can work at the same time. The question is, what is the optimal production allocation between the factories such that we maximize the profit obtained from selling the computers under those constraints?

Notice the additional constraint “Only two factories can work at the same time”. This can’t be solved with classic Linear Programming, since we need to decide which 2 factories work at a given day. There are multiple ways to solve this problem though, I have opted for a perhaps intuitive approach for understanding it better.

So we know we have 30 days to assemble all of those units, how can we define our constraints? Well, it is quite straightforward. We can define 3 binary variables for each day (1 variable per factory) and set the constraint that they shouldn’t sum up to more than 2. Binary variables are basically integer variables constrained to be between 0 and 1, inclusively. In the end, our mixed integer program looks as simple as this:

If you are wondering now why does it resemble a linear program, you’ve understood the point, the only difference is that we introduce integer variables. We can take a look at the problem definition to understand it a bit more. Basically, we can see the resulting objective is combined logically of all of those variables that we summed up in the above for loop. And also all the integer constraints.

computerAssembly:MAXIMIZE-450*f0eachDay_0 + -450*f0eachDay_1 + -450*f0eachDay_10 + -450*f0eachDay_11 + -450*f0eachDay_12 + -450*f0eachDay_13 + -450*f0eachDay_14 + -450*f0eachDay_15 + -450*f0eachDay_16 + -450*f0eachDay_17 + -450*f0eachDay_18 + -450*f0eachDay_19 + -450*f0eachDay_2 + -450*f0eachDay_20 + -450*f0eachDay_21 + -450*f0eachDay_22 + -450*f0eachDay_23 + -450*f0eachDay_3 + -450*f0eachDay_4 + -450*f0eachDay_5 + -450*f0eachDay_6 + -450*f0eachDay_7 + -450*f0eachDay_8 + -450*f0eachDay_9 + -420*f1eachDay_0 + -420*f1eachDay_1 + -420*f1eachDay_10 + -420*f1eachDay_11 + -420*f1eachDay_12 + -420*f1eachDay_13 + -420*f1eachDay_14 + -420*f1eachDay_15 + -420*f1eachDay_16 + -420*f1eachDay_17 + -420*f1eachDay_18 + -420*f1eachDay_19 + -420*f1eachDay_2 + -420*f1eachDay_20 + -420*f1eachDay_21 + -420*f1eachDay_22 + -420*f1eachDay_23 + -420*f1eachDay_3 + -420*f1eachDay_4 + -420*f1eachDay_5 + -420*f1eachDay_6 + -420*f1eachDay_7 + -420*f1eachDay_8 + -420*f1eachDay_9 + -400*f2eachDay_0 + -400*f2eachDay_1 + -400*f2eachDay_10 + -400*f2eachDay_11 + -400*f2eachDay_12 + -400*f2eachDay_13 + -400*f2eachDay_14 + -400*f2eachDay_15 + -400*f2eachDay_16 + -400*f2eachDay_17 + -400*f2eachDay_18 + -400*f2eachDay_19 + -400*f2eachDay_2 + -400*f2eachDay_20 + -400*f2eachDay_21 + -400*f2eachDay_22 + -400*f2eachDay_23 + -400*f2eachDay_3 + -400*f2eachDay_4 + -400*f2eachDay_5 + -400*f2eachDay_6 + -400*f2eachDay_7 + -400*f2eachDay_8 + -400*f2eachDay_9 + 0SUBJECT TO_C1: f0eachDay_0 + f1eachDay_0 + f2eachDay_0 <= 2_C2: f0eachDay_1 + f1eachDay_1 + f2eachDay_1 <= 2_C3: f0eachDay_2 + f1eachDay_2 + f2eachDay_2 <= 2_C4: f0eachDay_3 + f1eachDay_3 + f2eachDay_3 <= 2_C5: f0eachDay_4 + f1eachDay_4 + f2eachDay_4 <= 2_C6: f0eachDay_5 + f1eachDay_5 + f2eachDay_5 <= 2_C7: f0eachDay_6 + f1eachDay_6 + f2eachDay_6 <= 2_C8: f0eachDay_7 + f1eachDay_7 + f2eachDay_7 <= 2_C9: f0eachDay_8 + f1eachDay_8 + f2eachDay_8 <= 2_C10: f0eachDay_9 + f1eachDay_9 + f2eachDay_9 <= 2_C11: f0eachDay_10 + f1eachDay_10 + f2eachDay_10 <= 2_C12: f0eachDay_11 + f1eachDay_11 + f2eachDay_11 <= 2_C13: f0eachDay_12 + f1eachDay_12 + f2eachDay_12 <= 2_C14: f0eachDay_13 + f1eachDay_13 + f2eachDay_13 <= 2_C15: f0eachDay_14 + f1eachDay_14 + f2eachDay_14 <= 2_C16: f0eachDay_15 + f1eachDay_15 + f2eachDay_15 <= 2_C17: f0eachDay_16 + f1eachDay_16 + f2eachDay_16 <= 2_C18: f0eachDay_17 + f1eachDay_17 + f2eachDay_17 <= 2_C19: f0eachDay_18 + f1eachDay_18 + f2eachDay_18 <= 2_C20: f0eachDay_19 + f1eachDay_19 + f2eachDay_19 <= 2_C21: f0eachDay_20 + f1eachDay_20 + f2eachDay_20 <= 2_C22: f0eachDay_21 + f1eachDay_21 + f2eachDay_21 <= 2_C23: f0eachDay_22 + f1eachDay_22 + f2eachDay_22 <= 2_C24: f0eachDay_23 + f1eachDay_23 + f2eachDay_23 <= 2_C25: 2000 f0eachDay_0 + 2000 f0eachDay_1 + 2000 f0eachDay_10 + 2000 f0eachDay_11 + 2000 f0eachDay_12 + 2000 f0eachDay_13 + 2000 f0eachDay_14 + 2000 f0eachDay_15 + 2000 f0eachDay_16 + 2000 f0eachDay_17 + 2000 f0eachDay_18 + 2000 f0eachDay_19 + 2000 f0eachDay_2 + 2000 f0eachDay_20 + 2000 f0eachDay_21 + 2000 f0eachDay_22 + 2000 f0eachDay_23 + 2000 f0eachDay_3 + 2000 f0eachDay_4 + 2000 f0eachDay_5 + 2000 f0eachDay_6 + 2000 f0eachDay_7 + 2000 f0eachDay_8 + 2000 f0eachDay_9 + 1500 f1eachDay_0 + 1500 f1eachDay_1 + 1500 f1eachDay_10 + 1500 f1eachDay_11 + 1500 f1eachDay_12 + 1500 f1eachDay_13 + 1500 f1eachDay_14 + 1500 f1eachDay_15 + 1500 f1eachDay_16 + 1500 f1eachDay_17 + 1500 f1eachDay_18 + 1500 f1eachDay_19 + 1500 f1eachDay_2 + 1500 f1eachDay_20 + 1500 f1eachDay_21 + 1500 f1eachDay_22 + 1500 f1eachDay_23 + 1500 f1eachDay_3 + 1500 f1eachDay_4 + 1500 f1eachDay_5 + 1500 f1eachDay_6 + 1500 f1eachDay_7 + 1500 f1eachDay_8 + 1500 f1eachDay_9 + 1000 f2eachDay_0 + 1000 f2eachDay_1 + 1000 f2eachDay_10 + 1000 f2eachDay_11 + 1000 f2eachDay_12 + 1000 f2eachDay_13 + 1000 f2eachDay_14 + 1000 f2eachDay_15 + 1000 f2eachDay_16 + 1000 f2eachDay_17 + 1000 f2eachDay_18 + 1000 f2eachDay_19 + 1000 f2eachDay_2 + 1000 f2eachDay_20 + 1000 f2eachDay_21 + 1000 f2eachDay_22 + 1000 f2eachDay_23 + 1000 f2eachDay_3 + 1000 f2eachDay_4 + 1000 f2eachDay_5 + 1000 f2eachDay_6 + 1000 f2eachDay_7 + 1000 f2eachDay_8 + 1000 f2eachDay_9 >= 80000VARIABLES0 <= f0eachDay_0 <= 1 Integer0 <= f0eachDay_1 <= 1 Integer0 <= f0eachDay_10 <= 1 Integer0 <= f0eachDay_11 <= 1 Integer0 <= f0eachDay_12 <= 1 Integer0 <= f0eachDay_13 <= 1 Integer0 <= f0eachDay_14 <= 1 Integer0 <= f0eachDay_15 <= 1 Integer0 <= f0eachDay_16 <= 1 Integer0 <= f0eachDay_17 <= 1 Integer0 <= f0eachDay_18 <= 1 Integer0 <= f0eachDay_19 <= 1 Integer0 <= f0eachDay_2 <= 1 Integer0 <= f0eachDay_20 <= 1 Integer0 <= f0eachDay_21 <= 1 Integer0 <= f0eachDay_22 <= 1 Integer0 <= f0eachDay_23 <= 1 Integer0 <= f0eachDay_3 <= 1 Integer0 <= f0eachDay_4 <= 1 Integer0 <= f0eachDay_5 <= 1 Integer0 <= f0eachDay_6 <= 1 Integer0 <= f0eachDay_7 <= 1 Integer0 <= f0eachDay_8 <= 1 Integer0 <= f0eachDay_9 <= 1 Integer0 <= f1eachDay_0 <= 1 Integer0 <= f1eachDay_1 <= 1 Integer0 <= f1eachDay_10 <= 1 Integer0 <= f1eachDay_11 <= 1 Integer0 <= f1eachDay_12 <= 1 Integer0 <= f1eachDay_13 <= 1 Integer0 <= f1eachDay_14 <= 1 Integer0 <= f1eachDay_15 <= 1 Integer0 <= f1eachDay_16 <= 1 Integer0 <= f1eachDay_17 <= 1 Integer0 <= f1eachDay_18 <= 1 Integer0 <= f1eachDay_19 <= 1 Integer0 <= f1eachDay_2 <= 1 Integer0 <= f1eachDay_20 <= 1 Integer0 <= f1eachDay_21 <= 1 Integer0 <= f1eachDay_22 <= 1 Integer0 <= f1eachDay_23 <= 1 Integer0 <= f1eachDay_3 <= 1 Integer0 <= f1eachDay_4 <= 1 Integer0 <= f1eachDay_5 <= 1 Integer0 <= f1eachDay_6 <= 1 Integer0 <= f1eachDay_7 <= 1 Integer0 <= f1eachDay_8 <= 1 Integer0 <= f1eachDay_9 <= 1 Integer0 <= f2eachDay_0 <= 1 Integer0 <= f2eachDay_1 <= 1 Integer0 <= f2eachDay_10 <= 1 Integer0 <= f2eachDay_11 <= 1 Integer0 <= f2eachDay_12 <= 1 Integer0 <= f2eachDay_13 <= 1 Integer0 <= f2eachDay_14 <= 1 Integer0 <= f2eachDay_15 <= 1 Integer0 <= f2eachDay_16 <= 1 Integer0 <= f2eachDay_17 <= 1 Integer0 <= f2eachDay_18 <= 1 Integer0 <= f2eachDay_19 <= 1 Integer0 <= f2eachDay_2 <= 1 Integer0 <= f2eachDay_20 <= 1 Integer0 <= f2eachDay_21 <= 1 Integer0 <= f2eachDay_22 <= 1 Integer0 <= f2eachDay_23 <= 1 Integer0 <= f2eachDay_3 <= 1 Integer0 <= f2eachDay_4 <= 1 Integer0 <= f2eachDay_5 <= 1 Integer0 <= f2eachDay_6 <= 1 Integer0 <= f2eachDay_7 <= 1 Integer0 <= f2eachDay_8 <= 1 Integer0 <= f2eachDay_9 <= 1 Integer

Now, it is evident that mixed integer programs can get quite big because of the decision variables. Introducing integer variables and constraints is also introducing nonlinearity to the optimization problem, which makes the problem a lot harder to solve. As a matter of fact, for a decent size mixed integer program, the solution time grows exponentially with the number of integer variables! Just imagine that you have n binary variables, how many configurations exist for those binary variables? Well, 2^n configurations. This is why mixed integer programming is still an active area of research. The applications of such programs are immense, such as in combinatorial optimization or in any problem that requires decision making.

I hope this article has demystified mixed integer programming a bit in a short and straight-forward way such that it can be useful for you. Keep on optimizing!

Mixed Integer Programming: A Straight Forward Tutorial was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.