Your best resource to learn mixed-integer programming to solve practical decision-making problems.
OBS: We are migrating all the content of Mip Master to Mip Wise.
MIP stands for Mixed-integer Programming. It’s an important field of mathematical optimization and a fantastic technology for modeling and solving decision-making problems in a variety of domains such as supply chain, logistics, scheduling, electric power generation, and so many more.
Here, you will find lots of practical, hands-on examples to learn and apply MIP to solve real-world problems. Many years of academic and industry experience are being combined to develop this material aiming to help you to adopt the best practices right from the beginning.
It’s our commitment to keeping this material freely available for everyone.
One of the primary goal of Mip Master is to make the MIP technology accessible beyond the operations research community, and especially to the data science community. With that in mind, the use cases we share are designed to be as didactic as they can be (without compromising performance) and all of them are implemented in Python.
After covering this material, you will be able to:
We will cover the basic theory, but the emphasis will be on application. In fact, first we teach you how to use MIP with lots of practical, hands-on examples. You will find templates and sample codes that you can personalize, expand, and use in your own projects. Then, as you feel motivated, we give you the opportunity to dive deeper into the theory and move to the next level.
While coding is an important component of this course, only basic Python skills are required. And if you are a beginner in Python, you will learn a lot more in this course as well.
We hope you will enjoy this content and find it useful. We also hope that you will always come back to learn more and to use MIP with confidence, starting from your next project!
If you want to jump straight to the use cases, here is a list of the ones currently available. Keep in mind that we are constantly adding new use cases to the list. We recommend to explore the use cases following the order in this list, especially if you are not familiar with MIP yet.
TicTech - Illustrates how to implement a
very simple optimization model.
Author: Aster Santana, Jul 2020
Concepts:
Ukulele-la♬-la♫ - A simplified version of a practical
fulfillment problem.
Author: Aster Santana, Jul 2020
Concepts:
Paper Tree - A simplified version of a practical
production planning.
Author: Aster Santana, Jul 2020
Concepts:
Would you like to contribute with an use case too?! We provide templates and would be happy to helping you to build your use case!
Let’s dive a little deeper into the MIP technology.
MIP stands for Mixed-Integer Programming.
Putting all together, “MIP is an optimization problem that involves a mix of continuous and integer/binary decision variables.”
If you are not familiar with optimization, no worries! We will provide more background throughout the use cases. For now, all you need to know is that an optimization problem consists of minimizing or maximizing an objective function subject to a set of constraints, and the objective and constraints are functions of decision variables.
A decision variable could be the number of products to manufacture in given machine, or whether to fulfil orders from Facility A or from Facility B. Examples of objectives include minimizing waste and maximizing profit. A constraint could be a resource capacity such as maximum number of daily working hours.
At the end of the day, we want to define the set of all acceptable (feasible) solutions to the problem and identify one that has the best objective value.
There are three major steps to that end:
You will be surprised to see the variety of practical problems that you can solve with what you will learn here!
Few more facts:
MIP is a powerful decision-making technology. And here are four features of MIP to support this claim: representativeness, robustness, tractability, optimality guarantee.
To recap, MIP is great because:
To answers this question, let’s have a look at the history of MIP theory and MIP solvers.
First, MIP is not a new technology. Here is quote from the
book
50 Years of Integer Programming 1958-2008, From the Early
Years to the State-of-the-Art
“In 1958, Ralph E. Gomory transformed the field of integer programming when he published a short paper that described his cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming.”
MIP tractability used to be a concern in the beginning.
However, there has been tremendous progress around
solving MIP. Here is a quote from a recent paper
by Dimitris Bertsimas and Angela King:
“In the period 1991–2015, algorithmic advances in Mixed-Integer Linear Optimization (MILO) coupled with hardware improvements have resulted in an astonishing 450 billion factor speedup in solving MILO problems”
The number 450 billion is very impressive, isn’t it? And this number continue to grow year after year as can be seen from improvement performance reports by commercial MIP solvers such as CPLEX and Gurobi.
For several decades, MIP has been transforming operation across industries, including airlines crew scheduling, sport scheduling, and the whole field of supply chain. However, mostly only those developing the MIP theory were using this technology for solving practical problems initially. Deep understanding of the theoretical and computational aspects of MIP used to be required for modeling and solving real-world problems.
This reality began to change in the 90’s when the body of literature on how to model and solve MIP increased. Around the same time, the commercial MIP solvers Xpress and CPLEX began to gain popularity. Few years later, in early 2000’s, two of the first open source MIP solvers, GLPK and COIN-OR CBC, were public released. Another big player in the commercial side, Gurobi, was founded in 2008.
With that, a much broader community began to adopt MIP to solve challenging problems in various industries. However, some specific modeling language, such as GAMS, AMPL, or AIMMS, would still be required solving MIP. This used to somehow limit the usage of MIP to the Operations Research community.
Another wave of democratization of the MIP technology came with the broad adoption of Python as a programming language for data science and analytics. Many Python interface for optimization packages, such as Pyomo, Mip, and PuLP, emerged. Gurobi, in particular, has put tremendous effort in making its optimization package easily accessible via gurobipy, the Gurobi-Python interface, along with comprehensive, well-structured documentation. CPLEX has also taken a similar path.
Now, any data scientist (and other analytics professionals) can much more easily leverage MIP technology for solving all sort of combinatorial problems. However, the myth that optimization is only for Operation Researchers still remains around.
Apart from the fact that MIP is a powerful technology on its own, and it’s accessible even by those outside of the Operations Research community, we claim that the combination of data science and MIP is a powerful one.
In many applications, part of the input data to MIP models comes from a data science team. Perhaps the most classic example is demand data. Data scientists use forecasting to predict demand and then the output from the forecasting algorithm (point forecast) becomes input to the MIP model. In this example, prediction and optimization are done in disconnected silos. we claim that this disconnection has created a gap between what we have been doing and what we could have been achieving with data analytics.
As an example, there has been a case where data scientists and operations researchers solved, in close collaboration, an important real-world problem in which they used MIP to discretize and maximize expected revenue over ten thousand probability curves generated by a machine learning algorithm.
Here is a quote from
Ed Rothberg, the CEO of Gurobi, taken from a two-minutes video:
“MIP complements other analytics techniques like machine learning quite nicely, we will see more and more companies building application that combines machine learning and optimization.”
In conclusion, there are big benefits in bringing MIP and data science (or machine learning) capabilities closer together.
This is a tricky question. And the answer highly depends on the level of expertise you want to achieve. Compared to Machine Learning, it might be fair to say that:
Notice that all these Machine Learning techniques are themselves application of optimization—and MIP is one kind of optimization.
For example, every time we try to fit a model to a data, we are searching for the parameters of the model that minimize error or maximize likelihood. So, this is an optimization problem, even though data scientists don’t typically see this way. Why don’t they? The answer is simple: when minimizing sum of square errors, there is a closed form solution for the best fitting parameters. The formula buries the optimization. Now, replace the linear model with an exponential model, as we would do to model the spreading of a contagious disease, for example. In this case, there is no closed formula and we need to use some explicit optimization approach, like a gradient descent algorithm.
Going back to the main question, there are several levels of expertise that one can achieve in optimization. This includes being able to:
Level 3 is the one that requires most practice because there is not a single recipe for MIP modeling. Level 4 is the most fun for most people. That’s when you hit the run button and follow the progress of the optimization solver by watching its log, like this one (notice the MIP Gap going to zero in last column):
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bou nd ItCnt Gap
* 0+ 0 6.11449e+07 5.06574e+ 07 17.15%
0 0 5.45123e+07 284 6.11449e+07 5.45123e+ 07 2230 10.85%
* 0+ 0 5.75671e+07 5.45123e+ 07 5.31%
* 0+ 0 5.69224e+07 5.45123e+ 07 4.23%
0 0 5.45151e+07 284 5.69224e+07 Cuts: 2 48 2773 4.23%
* 0+ 0 5.67861e+07 5.45151e+ 07 4.00%
0 0 5.45175e+07 284 5.67861e+07 Cuts: 2 43 3350 3.99%
0 0 5.45176e+07 284 5.67861e+07 Cuts: 1 42 3823 3.99%
* 0+ 0 5.59982e+07 5.45176e+ 07 2.64%
0 0 5.45178e+07 284 5.59982e+07 Cuts: 1 40 4397 2.64%
* 0+ 0 5.53996e+07 5.45178e+ 07 1.59%
* 0+ 0 5.51997e+07 5.45182e+ 07 1.23%
0 0 -1.00000e+75 0 5.51997e+07 5.45182e+ 07 4397 1.23%
* 0+ 0 5.47518e+07 5.45182e+ 07 0.43%
At the beginning, you will spend a lot of time around Level 3 and Level 4, which is the main focus of the Learning MIP project. Level 6 is where you find Operations Research professionals who hold a Ph.D. degree. Level 5 is also super fun, but require some more experience. To get to Level 6, you need to deeply understand the theory underling Levels 3-5. We can point directions for those interested on that. But first we focus only on the theory that is needed to make you a thoughtful practitioner.
Well done! So far, you have already learned that:
We hope you are ready and excited to start your MIP journey! Or move to the next level if MIP is not new to you.
Now it’s time to see practical examples and learn how to model and solve real-world optimization problems as a Mip Master! We recommend you start from the TicTech use case.
Before you get started, let’s introduce you to Mr. Mip, our role model for learning and applying the MIP technology. Mr. Mip is a consultant who is expert in using mathematical optimization and programming for solving decision-making problems. You will learn by observing Mr. Mip in action throughout the use cases. To take the most from this experience, you should focus on understanding how Mr. Mip thinks. He’s very systematic, so it will be easy to recognize his thinking pattern.
You will need a solver to solve MIP models. A MIP solver is basically a professional implementation of a branch and bound method combined with a cutting-plane method.
While there are many solvers available for solving MIP, we list only four of the most traditional solvers (follow this link for a more comprehensive list of optimization software). All of them are proprietary solvers except for CBC, which is open-source and part of the COIN-OR project. Free academic licenses are available for all the three proprietary solvers listed below.
If you are beginning and eligible for an academic license, Gurobi has very friendly and well-structured documentation. If you are not eligible for an academic license, you may want to start with CBC-PuLP. The good news is that the modeling syntax of these solvers are all very similar, meaning that if you learn how to use one solver, then it’s easy to switch to another solver.
The goal of Mip Master with the Learning MIP project is to democratize the MIP technology so it can be use beyond the Operation Research community.
Traditionally, MIP had been thought by starting with a comprehensive revision of the theory underlying the MIP technology. Specifically, students would spend a lot of time learning Linear Algebra, geometry of linear inequalities, the simplex algorithms, and so on. Only then students would start learning formulation. Implementation, the most fun part, tends to be the last component of traditional MIP-related courses.
We take a completely different approach. We focus first on the application and introduce the theory along the way as necessary, only after building the motivation for it. In fact, we start with formulation and implementation from the first use case, because we know that the whole learning experience will be much more meaningful and enjoyable this way.
We believe that this is the right approach, even for the Operation Research community, simply because this is how human brain works. You see a problem, you try to solve it with the tools you have available, and if you are not satisfied with the result, you go after more sophisticated tools. And by the time you recognize that more complex tools are needed, you already have the motivation and clarity it takes to grasp that underling theory.
If you have any question, comment, would like to learn more or contribute, feel free to open a new issue on GitHub, or reach out directly to Aster Santana on LinkedIn.