Solving linear optimization problems in python

LP Solvers In

<ol><li>Google OR-Tools</li><li>SciPy, </li><li>beginner-friendly PuLP, </li><li>exhaustive Pyomo,</li><li>CBC </li><li>Scip</li><li>Gurobi</li><li>Cplex</li></ol>

List Of Tools 

<ul><li>quite user-friendly, </li><li> several prepackaged solvers, </li><li>by far the most stars on GitHub.</li><li>CBC, an open-source MIP solver OR SCIP </li><li>COMMON interfaces to use the same model with different solvers. </li><li>GLOP (Google Linear Optimization Package). FOSS + written in C++</li></ul>

Google Or-tools 

<h2 data-selectable-paragraph="">A guide to mathematical optimization with Google OR-Tools</h2><figure><img alt="" src="https://miro.medium.com/max/500/1*Epu8_DseKreL6x_vp-uQyQ" width="692" height="389"><figcaption class="ku kv fv ft fu kw kx bo b bp bq br" data-selectable-paragraph="" dir="ltr">Image by author, emojis by <a class="au ky" href="https://openmoji.org/" rel="noopener ugc nofollow" dir="ltr">OpenMoji</a> (<a class="au ky" href="https://creativecommons.org/licenses/by-sa/4.0/#" rel="noopener ugc nofollow" dir="ltr">CC BY-SA 4.0</a>)</figcaption></figure>Linear programming is a technique to optimize any problem with multiple variables and constraints. It’s a simple but powerful tool every data scientist should master.Imagine you are a strategist recruiting an army. You have:<UL><LI>Three resources: 🌾food, 🪵wood, and 🪙gold</LI><LI>Three units: 🗡️swordsmen, 🏹bowmen, and 🐎horsemen.</LI></UL>Horsemen are stronger than bowmen, who are in turn stronger than swordsmen. The following table provides the cost and power of each unit:<figure><img alt="" src="https://miro.medium.com/max/500/1*dtvvedKDJWpB9zgnMoIYh" width="692" height="170"><figcaption dir="auto">Image by author</figcaption></figure>Now we have 1200 🌾food, 800 🪵wood, and 600 🪙gold. How should we maximize the power of our army considering these resources?We could simply find the unit with the best power/cost ratio, take as many of them as possible, and repeat the process with the other two units. But this “guess and check” solution might not even be optimal…Now imagine we have millions of units and resources: the previous greedy strategy is likely to completely miss the optimal solution. It is possible to use a machine learning algorithm (e.g., a genetic algorithm) to solve this problem, but we have no guarantee that the solution will be optimal either.Fortunately for us, there is a method that can solve our problem in an optimal way: linear programming (or linear optimization), which is part of the field of <a href="https://en.wikipedia.org/wiki/Operations_research" rel="noopener ugc nofollow" dir="ltr">operations research</a> (OR). In this article, we’ll use it to find the best numbers of swordsmen, bowmen, and horsemen to build the army with the highest power possible.<h1 data-selectable-paragraph="">🧠 I. Solvers</h1>In Python, there are different libraries for linear programming such as the multi-purposed SciPy, the beginner-friendly PuLP, the exhaustive Pyomo, and many others.Today, we are going to use <a href="https://developers.google.com/optimization" rel="noopener ugc nofollow" dir="ltr">Google OR-Tools</a>, which is quite user-friendly, comes with several prepackaged solvers, and has by far the most stars on <a href="https://github.com/google/or-tools" rel="noopener ugc nofollow" dir="ltr">GitHub</a>. You can run the code from this tutorial with the following <a href="https://colab.research.google.com/drive/1dbrFJwFv80kgUi13MfPO3KyumG-SVIHG?usp=sharing" rel="noopener ugc nofollow" dir="ltr">Google Colab notebook</a>.If the installation doesn't work, please restart the kernel and try again: it can fail sometimes. ¯\_(ツ)_/¯All these libraries have a hidden benefit: they act as interfaces to use the same model with different solvers. Solvers like <a href="https://www.gurobi.com/" rel="noopener ugc nofollow" dir="ltr">Gurobi</a>, <a href="https://www.ibm.com/analytics/cplex-optimizer" rel="noopener ugc nofollow" dir="ltr">Cplex</a>, or <a href="https://www.scipopt.org/" rel="noopener ugc nofollow" dir="ltr">SCIP</a> have their own APIs, but the models they create are tied to a specific solver.OR-Tools allows us to use an abstract (and quite pythonic) way of modeling our problems. We can then choose one or several solvers to find an optimal solution. The model we built is thus highly reusable!<figure><img alt="" src="https://miro.medium.com/max/500/1*RcFaacJfUxkLQu9ZJLxSM" width="692" height="346"><figcaption dir="auto">Image by author</figcaption></figure>OR-Tools comes with its own linear programming solver, called GLOP (Google Linear Optimization Package). It is an open-source project created by Google’s Operations Research Team and written in C++.Other solvers are available such as SCIP, an excellent non-commercial solver created in 2005 and updated and maintained to this day. We could also use popular commercial options like Gurobi and Cplex. However, we would need to install them on top of OR-Tools and get the appropriate licenses (which can be quite costly). For now, let’s try GLOP.<h1 data-selectable-paragraph="">🧮 II. Variables</h1>We created an instance of the OR-Tools solver using GLOP. Now, how to use linear programming? The first thing we want to define is the variables we want to optimize.In our example, we have three variables: the number of 🗡️swordsmen, 🏹bowmen, and 🐎horsemen in the army. OR-Tools accepts three types of variables:<UL><LI><code dir="ltr">NumVar</code> for continuous variables;</LI><LI><code dir="ltr">IntVar</code> for integer variables;</LI><LI><code dir="ltr">BoolVar</code> for boolean variables.</LI></UL>We’re looking for round numbers of units, so let’s choose <code dir="ltr">IntVar</code>. We then need to specify lower and upper bounds for these variables. We want at least 0 unit, but we don't really have an upper bound. So we can say that our upper bound is infinity (or any big number we will never reach). It can be written as:<figure><img alt="" src="https://miro.medium.com/max/500/1*tmTB9WDjSVhRdyI41hVzs" width="692" height="138"></figure>Let’s translate it into code. Infinity is replaced by <code dir="ltr">solver.infinity()</code> in OR-Tools. Other than that, the syntax is quite straightforward:<h1 data-selectable-paragraph="">⛓️ III. Constraints</h1>We defined our variables, but the constraints are just as important.Perhaps counter-intuitively, adding more constraints helps the solver to find an optimal solution faster. Why is this the case? Think of the solver as a tree: constraints help it trim branches and reduce the search space.In our case, we have a limited number of resources we can use to produce units. In other words, we can’t spend more resources than we have: for instance, the 🌾food spent to recruit units cannot be higher than 1200. The same is true with 🪵wood (800) and 🪙gold (600).According to our table, units have the following costs:<UL><LI>1 swordsman = 🌾60 + 🪵20;</LI><LI>1 bowman = 🌾80 + 🪵10 + 🪙40;</LI><LI>1 horseman = 🌾140 + 🪙100.</LI></UL>We can write one constraint per resource as follows:<figure><img alt="" src="https://miro.medium.com/max/500/1*hx6WLhDzOyxIH1lfuWE7-" width="692" height="102"></figure>In OR-Tools, we simply add the constraints to our solver instance with <code dir="ltr">solver.Add()</code>.<h1 data-selectable-paragraph="">🎯 IV. Objective</h1>Now that we have our variables and constraints, we want to define our goal (or objective function).In linear programming, this function has to be linear (like the constraints), so of the form ax + by + cz + d. In our example, the objective is quite clear: we want to recruit the army with the highest power. The table gives us the following power values:<UL><LI>1 swordsman = 💪70;</LI><LI>1 bowman = 💪95;</LI><LI>1 horseman = 💪230.</LI></UL>Maximizing the power of the army amounts to maximizing the sum of the power of each unit. Our objective function can be written as:<figure><img alt="" src="https://miro.medium.com/max/500/1*ayqxaO_0VU2XKkNV3XkOR" width="692" height="21"></figure>In general, there are only two types of objective functions: maximizing or minimizing. In OR-Tools, we declare this goal with <code dir="ltr"><a href="https://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#Solver.Maximize" rel="noopener ugc nofollow" dir="ltr">solver.Maximize()</a></code> or <code dir="ltr"><a href="https://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#Solver.Minimize" rel="noopener ugc nofollow" dir="ltr">solver.Minimize()</a></code>.And we’re done! There are three steps to model any linear optimization problem:<OL><LI>Declaring the variables to optimize with lower and upper bounds;</LI><LI>Adding constraints to these variables;</LI><LI>Defining the objective function to maximize or to minimize.</LI></OL>Now that is clear, we can ask the solver to find an optimal solution for us.<h1 data-selectable-paragraph="">🥇 V. Optimize!</h1>Calculating the optimal solution is done with <code dir="ltr"><a href="https://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#Solver.Solve" rel="noopener ugc nofollow" dir="ltr">solver.Solve(</a>)</code> . This function returns a status that can be used to check that the solution is indeed optimal.Let's print the highest total power we can get with the best army configuration.<PRE>================= Solution ================= Solved in 87.00 milliseconds in 2 iterations Optimal power = 1800.0 💪power Army: - 🗡️Swordsmen = 6.0000000000000036 - 🏹Bowmen = 0.0 - 🐎Horsemen = 5.999999999999999</PRE>Great! The solver found an optimal solution: our army has a total power of 💪1800 with 6 🗡️swordsmen and 6 🐎horsemen (sorry bowmen!).Let’s unpack this result:<UL><LI>The solver decided to take the maximum number of 🐎horsemen (6, since we only have 🪙600 and they each cost 🪙100);</LI><LI>The remaining resources are spent in 🗡️swordsmen: we have 1200 – 6*140 = 360🌾food left, which is why the solver chose 6 🗡️swordsmen</LI><LI>We can deduce that the horsemen are the best unit and the bowmen are the worst one because they haven’t been chosen at all.</LI></UL>Okay, but there’s something quite weird: these numbers are not round, even though we specified that we wanted integers (IntVar). So what happened?Unfortunately, answering this question requires a deep dive into linear programming… To keep things simple in this introduction, let’s say it’s because of GLOP. Solvers have characteristics we have to take into account, and GLOP doesn’t handle integers. This is another proof that building reusable models is more than just convenient.We’ll explain why GLOP has this strange behavior and how to fix it in a <a rel="noopener" href="https://towardsdatascience.com/integer-programming-vs-linear-programming-in-python-f1be5bb4e60e" dir="ltr">more advanced tutorial</a>.<h1 data-selectable-paragraph="">Conclusion</h1>We saw through this example the five main steps of any linear optimization problem:<OL><LI>Choosing a solver: in our case, we selected GLOP for convenience.</LI><LI>Declaring variables: the parameters to optimize were the number of swordsmen, bowmen, and horsemen.</LI><LI>Declaring constraints: each of these units has a cost. The total cost could not exceed our limited resources.</LI><LI>Defining objective: the criterion to maximize was the total power of this army. It could have been something else, like the number of units.</LI><LI>Optimizing: GLOP found an optimal solution to this problem in less than a second.</LI></OL><figure><img alt="" src="https://miro.medium.com/max/500/1*vLGio9N2GVYwVX5u_IN2n" width="692" height="1230"><figcaption dir="auto">Image by author</figcaption></figure>This is the main benefit of linear programming: the algorithm gives us a guarantee that the solution that was found is optimal (with a certain error). This guarantee is powerful, but comes at a cost: the model can be so complex that the solver takes years (or more) to find an optimal solution. In this scenario, we have two options:<UL><LI>We can stop the solver after a certain time (and probably obtain a suboptimal answer);</LI><LI>We can use a metaheuristic like a genetic algorithm to calculate an excellent solution in a short amount of time.</LI></UL>In the next article, we’ll talk about the different types of optimization problems and generalize our approach to an entire class of them.I hope you enjoyed this introduction! Feel free to share it and spread the knowledge about linear optimization. Don’t forget to <a href="https://mlabonne.github.io/blog/" rel="noopener ugc nofollow" dir="ltr">check my blog</a> and <a href="https://twitter.com/maximelabonne" rel="noopener ugc nofollow" dir="ltr">follow me on Twitter</a> where I post summaries of these articles. Cheers!

Linear programming optimization in python for factory support chain use cases

Linear programming is a technique to optimize any problem with multiples variables and constraints. It is a simple tool every data scientist should master.

productivity

Productivity

problemsolving

Problem Solving

computerscience

Computer Science

artificialintelligence

Artificial Intelligence

scienceandnature

Science & Nature

A guide to mathematical optimization with Google OR-Tools

Linear programming is a technique to optimize any problem with multiple variables and constraints . It’s a simple but powerful tool every data scientist should master .

Imagine you are a strategist recruiting an army . You have:

<ul><li>Three resources : 🌾food , 🪵wood , and 🪙gold </li><li>Three units : 🗡️swordsmen , 🏹bowmen , and 🐎horsemen . </li> </ul>

Horsemen are stronger than bowmen , who are in turn stronger than swordsmen . The following table provides the cost and power of each unit :

Now we have 1200 🌾food , 800 🪵wood , and 600 🪙gold . How should we maximize the power of our army considering these resources?

We could simply find the unit with the best power/cost ratio , take as many of them as possible , and repeat the process with the other two units. But this “guess and check” solution might not even be optimal …

Now imagine we have millions of units and resources : the previous greedy strategy is likely to completely miss the optimal solution . It is possible to use a machine learning algorithm (e.g., a genetic algorithm) to solve this problem, but we have no guarantee that the solution will be optimal either .

Fortunately for us, there is a method that can solve our problem in an optimal way : linear programming (or linear optimization), which is part of the field of <a href="https://en.wikipedia.org/wiki/Operations_research">operations research </a>(OR). In this article, we’ll use it to find the best numbers of swordsmen, bowmen, and horsemen to build the army with the highest power possible .

In Python, there are different libraries for linear programming such as the multi-purposed SciPy , the beginner-friendly PuLP , the exhaustive Pyomo , and many others.

Today, we are going to use <a href="https://developers.google.com/optimization">Google OR-Tools </a>, which is quite user-friendly , comes with several prepackaged solvers , and has by far the most stars on <a href="https://github.com/google/or-tools">GitHub </a>. You can run the code from this tutorial with the following <a href="https://colab.research.google.com/drive/1dbrFJwFv80kgUi13MfPO3KyumG-SVIHG?usp=sharing">Google Colab notebook </a>.

If the installation doesn't work, please restart the kernel and try again : it can fail sometimes. ¯\_(ツ)_/¯

All these libraries have a hidden benefit : they act as interfaces to use the same model with different solvers . Solvers like <a href="https://www.gurobi.com/">Gurobi </a>, <a href="https://www.ibm.com/analytics/cplex-optimizer">Cplex </a>, or <a href="https://www.scipopt.org/">SCIP </a>have their own APIs, but the models they create are tied to a specific solver .

OR-Tools allows us to use an abstract (and quite pythonic) way of modeling our problems. We can then choose one or several solvers to find an optimal solution. The model we built is thus highly reusable !

OR-Tools comes with its own linear programming solver , called GLOP (Google Linear Optimization Package). It is an open-source project created by Google’s Operations Research Team and written in C++.

Other solvers are available such as SCIP , an excellent non-commercial solver created in 2005 and updated and maintained to this day. We could also use popular commercial options like Gurobi and Cplex . However, we would need to install them on top of OR-Tools and get the appropriate licenses (which can be quite costly). For now, let’s try GLOP.

We created an instance of the OR-Tools solver using GLOP. Now, how to use linear programming? The first thing we want to define is the variables we want to optimize .

In our example, we have three variables: the number of 🗡️swordsmen , 🏹bowmen , and 🐎horsemen in the army. OR-Tools accepts three types of variables:

<ul><li><code>NumVar </code>for continuous variables; </li><li><code>IntVar </code>for integer variables; </li><li><code>BoolVar </code>for boolean variables. </li> </ul>

We’re looking for round numbers of units , so let’s choose <code>IntVar </code>. We then need to specify lower and upper bounds for these variables. We want at least 0 unit, but we don't really have an upper bound . So we can say that our upper bound is infinity (or any big number we will never reach). It can be written as:

Let’s translate it into code. Infinity is replaced by <code>solver.infinity() </code>in OR-Tools. Other than that, the syntax is quite straightforward :

We defined our variables, but the constraints are just as important.

Perhaps counter-intuitively, adding more constraints helps the solver to find an optimal solution faster . Why is this the case? Think of the solver as a tree: constraints help it trim branches and reduce the search space .

In our case, we have a limited number of resources we can use to produce units . In other words, we can’t spend more resources than we have : for instance, the 🌾food spent to recruit units cannot be higher than 1200 . The same is true with 🪵wood (800) and 🪙gold (600).

According to our table, units have the following costs:

<ul><li>1 swordsman = 🌾60 + 🪵20; </li><li>1 bowman = 🌾80 + 🪵10 + 🪙40; </li><li>1 horseman = 🌾140 + 🪙100. </li> </ul>

We can write one constraint per resource as follows:

In OR-Tools, we simply add the constraints to our solver instance with <code>solver.Add() </code>.

Now that we have our variables and constraints, we want to define our goal (or objective function ).

In linear programming, this function has to be linear (like the constraints), so of the form ax + by + cz + d . In our example, the objective is quite clear: we want to recruit the army with the highest power . The table gives us the following power values:

<ul><li>1 swordsman = 💪70; </li><li>1 bowman = 💪95; </li><li>1 horseman = 💪230. </li> </ul>

Maximizing the power of the army amounts to maximizing the sum of the power of each unit . Our objective function can be written as:

In general, there are only two types of objective functions: maximizing or minimizing . In OR-Tools, we declare this goal with <code><a href="https://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#Solver.Maximize">solver.Maximize() </a> </code>or <code><a href="https://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#Solver.Minimize">solver.Minimize() </a> </code>.

And we’re done! There are three steps to model any linear optimization problem :

<ol><li>Declaring the variables to optimize with lower and upper bounds; </li><li>Adding constraints to these variables; </li><li>Defining the objective function to maximize or to minimize. </li> </ol>

Now that is clear, we can ask the solver to find an optimal solution for us.

Calculating the optimal solution is done with <code><a href="https://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#Solver.Solve">solver.Solve( </a>) </code>. This function returns a status that can be used to check that the solution is indeed optimal .

Let's print the highest total power we can get with the best army configuration .

Great! The solver found an optimal solution: our army has a total power of 💪1800 with 6 🗡️swordsmen and 6 🐎horsemen (sorry bowmen!).

<ul><li>The solver decided to take the maximum number of 🐎horsemen (6, since we only have 🪙600 and they each cost 🪙100); </li><li>The remaining resources are spent in 🗡️swordsmen : we have 1200 – 6*140 = 360🌾food left, which is why the solver chose 6 🗡️swordsmen </li><li>We can deduce that the horsemen are the best unit and the bowmen are the worst one because they haven’t been chosen at all. </li> </ul>

Okay, but there’s something quite weird: these numbers are not round , even though we specified that we wanted integers (IntVar). So what happened?

Unfortunately, answering this question requires a deep dive into linear programming … To keep things simple in this introduction, let’s say it’s because of GLOP . Solvers have characteristics we have to take into account, and GLOP doesn’t handle integers . This is another proof that building reusable models is more than just convenient.

We’ll explain why GLOP has this strange behavior and how to fix it in a <a href="https://towardsdatascience.com/integer-programming-vs-linear-programming-in-python-f1be5bb4e60e">more advanced tutorial </a>.

We saw through this example the five main steps of any linear optimization problem:

<ol><li>Choosing a solver : in our case, we selected GLOP for convenience. </li><li>Declaring variables : the parameters to optimize were the number of swordsmen, bowmen, and horsemen. </li><li>Declaring constraints : each of these units has a cost. The total cost could not exceed our limited resources. </li><li>Defining objective: the criterion to maximize was the total power of this army. It could have been something else, like the number of units. </li><li>Optimizing : GLOP found an optimal solution to this problem in less than a second. </li> </ol>

This is the main benefit of linear programming: the algorithm gives us a guarantee that the solution that was found is optimal (with a certain error). This guarantee is powerful, but comes at a cost: the model can be so complex that the solver takes years (or more) to find an optimal solution. In this scenario, we have two options:

<ul><li>We can stop the solver after a certain time (and probably obtain a suboptimal answer); </li><li>We can use a metaheuristic like a genetic algorithm to calculate an excellent solution in a short amount of time . </li> </ul>

In the next article, we’ll talk about the different types of optimization problems and generalize our approach to an entire class of them.

I hope you enjoyed this introduction! Feel free to share it and spread the knowledge about linear optimization . Don’t forget to <a href="https://mlabonne.github.io/blog/">check my blog </a>and <a href="https://twitter.com/maximelabonne">follow me on Twitter </a>where I post summaries of these articles. Cheers!

Introduction to Linear Programming in Python

LP Solvers In

List Of Tools

Google Or-tools

CURATED BY

CURATOR'S NOTE

Related collections

More like this