My previous post https://www.letsai.in/post/solving-business-optimization-problems-using-excel-solver explained what is linear optimization (LP) or how business optimization problems can be converted to mathematical Linear Optimization problems and solved.
This post would talk about the different tools & libraries in python to achieve the same. Let us start by discussing what is a LP Solver ?
Solver
A Solver is an algorithm or a method to solve a LP problem. There are different ways or algorithms to solve the same problem. Some libraries have their own solver, while others provide interfaces to different popular solvers. For example, Google OR-Tools comes with its own solver, called GLOP (Google Linear Optimization Package). It is an open-source project created by Google. Other solvers are available such as SCIP (Solving Constraint Integer Problems), a popular solver created in 2005 and comes as its own server. We could also use popular commercial options like Gurobi and Cplex.
In Python, there are different libraries available for linear programming. Some of the popular ones being
1. SciPy
2. PuLP
3. Pyomo
4. Google OR-Tools
Libraries
Scipy
Within the Scipy library - linear programming modules are are available as scipy.optimize.linprog
Considerations
scipy linprog can only work with minimization problems
constraints must be expressed as <=
It cannot run with external solvers.
You need to design arrays and matrices for the model which may be tedious and error-prone, It doesn't facilitate model building.
For #2 - while this is a limitation - one way could be to transform the objective function to negative of it - that is to multiply the coefficients by -1. (reverse their sign)
PuLP
PuLP is a free, open-source and portable library which provides a simple API and programming syntax. It provides an interface to a number of popular solvers. PuLP's strength is its simplicity, less time to learn, and that it was made having "Pythonic" style of development in mind.
PuLP does not allow abstract models. It only allows concrete models. The rationale is that while abstract models are needed theoretically, but most practical problems are easily covered by PuLP's design. Also, it can only work with linear problems so as to maintain its simplicity.
Pyomo
Pyomo stands for Python Optimization Model Objects. It is used to solve large scale optimization problems as it can also support non-linear problems. Pyomo takes a different approach in the sense that it supports Abstract Modelling.
An abstract model has unspecified parameter values. The actual instantiation and assigning values to the instance of the model are deferred. The rationale is that in real-life systems these may keep changing and hence values should be picked up latest when needed. Pyomo can pick these values (as data) from various data sources even including spreadsheets, & databases.
Pyomo always uses a solver and does not come with its own solver. It can connect to various industry grade solvers including open source and commercial.
It supports an object-oriented style of building the optimization models.
Google OR-Tools
As the name suggests, OR Tools is a research project from Google Operations Research (OR) team.
OR-Tools comes comes with its own solver, called GLOP (Google Linear Optimization Package). It can also connect with other solvers like SCIP, Gurobi, CPLEX etc.
Notes
Real-life problems and their associated models may be very complex and generate a large number of parameters. These could take a very long time to solve. So we do have an option of stopping the solver after a certain time, so that we may get to solution, even if it is somewhat sub-optimal.
References:
Paper: PuLP: A Linear Programming Toolkit for Python, Mitchell et. all (2011)
Book: Pyomo — Optimization Modeling in Python, William Hart
Comments