Today, I am going to introduce you to one of the amazing tools offered by google - Google OR-Tools. A great tool when it comes to optimizations under constraints. Google OR-Tools let you solve some complex optimization problems under great ease. If you have ever been stucked into a problem which requires you to find an optimal solutions to a given equation then you must check onto this amazing tool for yourself. Let’s get started.
“OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions.” - Google
Some of the examples provided by google include :-
- Constraint Programming
- Vehicle Routing
- Linear or Mixed-Integer programming
- Graph Algorithms
For now, i am only familier with
Linear Programming. So, I am going to discuss this below.
Linear Programming deals with the optimization (maximization or minimization) of linear functions subject to linear constraints. There are various methods used to solve a linear programming problem, mentioned below:-
- Graphical method
- Simplex method
- M-method or method of penalties
- Dual Simplex method.
All the listed above are in order of increasing complexity and each of them was an improvement over the other.
Here, Simplex method, devised in 1947 is the most used method but some problems have proved it to take exponential time. After this many researchers such as Leonid Khachiyan in 1947(weakly polynomial alogorithm), Narendra karmarkar in 1984(interior point method) have decreased the time complexity of algorithms.
Note :- Interior point algorithms have proved efficient on very large linear programs.
Formulation of the problem
Before we begin with some hands-on to
Google OR-Tools let’s formulate a problem and understand some terminologies first.
A company manufacturers two types of cloth, using three different colours of wool. One yard length of type A cloth requires:- 4 oz of red wool, 5 oz of green wool and 3 oz of yellow wool. One yard length of type B cloth requires:- 5 oz of red wool, 2 oz of green wool and 8 oz of yellow wool. The wool available for manufacturer is:- 1000 oz of red wool, 1000 oz of green wool and 1200 oz of yellow wool. The manufacturer can earn a profit of:- $5 on one yard of type A cloth and $3 on one yard of type B cloth. Find the best combination of quantites of:- type A and type B cloth which gives him maximum profit by solving the Linear programming problem.
Seems a tough one, but it will look less complex if we look at the problem like:-
Now let’s formulate in terms of some equations :-
Here the motive of manufacturer is to obtain the quantities of
cloth B. So, let the quantities of
cloth Bbe A and B which are also called the decision variables for the problem.
We have some requirements of materials for each type of cloth which inturn are bounded by the availabilty of that material. So, Next we shall define our constraints :-
4A + 5B <= 1000 5A + 2B <= 1000 3A + 8B <= 1200
Additionaly, a L.P.P problem must have non negative decision variables.
A, B >= 0
Lastly, manufacturer wants to maximize profit. Therefore, we need to define a objective function(Z) :-
Z = 5A + 3B
The Glop Linear Solver
The primary OR-Tools linear optimization solver is Glop, Google’s linear programming system. It’s fast, memory efficient, and numerically stable. The next section shows how to use Glop to solve a simple linear problem in all of the supported languages. - Google
For the reference to installation, it is best to follow the guidelines mentioned at here
from __future__ import print_function from ortools.linear_solver import pywraplp def LinearProgrammingSolver(): # instantiate the solver with name LinearProgrammingSolver solver = pywraplp.Solver('LinearProgrammingSolver', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING) # define your decision variables A = solver.NumVar(0, solver.infinity(), 'A') B = solver.NumVar(0, solver.infinity(), 'B') # Define first constraint for :- 4A + 5B <= 1000 constraint0 = solver.Constraint(-solver.infinity(), 1000) constraint0.SetCoefficient(A, 4) constraint0.SetCoefficient(B, 5) # Define second constraint for :- 5A + 2B <= 1000 constraint1 = solver.Constraint(-solver.infinity(), 1000) constraint1.SetCoefficient(A, 5) constraint1.SetCoefficient(B, 2) # Define third constraint for :- 3A + 8B <= 1200 constraint2 = solver.Constraint(-solver.infinity(), 1200) constraint2.SetCoefficient(A, 3) constraint2.SetCoefficient(B, 8) # Define your objective function :- Z = 5A + 3B objective = solver.Objective() objective.SetCoefficient(A, 5) objective.SetCoefficient(B, 3) objective.SetMaximization() # Call the Solve() method for a solution solver.Solve() # Calculate the optimal solution opt_solution = 5 * A.solution_value() + 3 * B.solution_value() print('Number of variables =', solver.NumVariables()) print('Number of constraints =', solver.NumConstraints()) # The value of each variable in the solution. print('Solution:') print('x = ', A.solution_value()) print('y = ', B.solution_value()) # The objective value of the solution. print('Optimal objective value =', opt_solution) # Driver Function call LinearProgrammingSolver()
Number of variables = 2 Number of constraints = 3 Solution: x = 176.47058823529403 y = 58.82352941176477 Optimal objective value = 1058.8235294117644
For code you can refer to my colab notebook on github
I hope you understood how a linear programming problem is formulated and solved with this amazing tool provided by google. For more info you can always refer to documentation and tutorials by google.
Note :- The above example was taken from one of my favourite book named :- Higher Engineering Mathematics by Dr. B.S. Grewal.
Today, we learnt how to formulate a linear programming problem and solve it using Google OR-Tools. Thanks for a reading. I’ll be continuing on more problems that are solved by Google OR-Tools. So, if you are interested see you around. Bye!