In this article, we’ll learn about the optimization problem and how to solve it in Python. The purpose of optimization is to select the optimal solution to a problem among a vast number of alternatives.
Also read: How To Write Android Apps In Python?
Optimization Problem
Let’s take a simple case scenario where optimization is employed. Suppose a bakery produces 1000 bread packets each day, and every packet contains 10 pieces of bread. To quantify production, every batch of bread is prepared with precise amounts of ingredients like wheat, yeast, etc.
In a certain financial quarter, the company decides to cut production costs while not compromising on the quality or sizing of bread. The management decides to reduce the diagonal length of each of its bread, by 1 inch, which is not much observable but has wide implications when applied to large-scale production.
So now, the requirement for the precise amount of wheat and yeast required for producing small-sized bread makes it an optimization problem. A well-optimized result can cut the input cost while keeping the size of the bread desirable.
This problematic piece of the task, like all optimization problems, needs a few of the essentials that are analogous for all the programming languages:
The solution – The amount you aim to improve.
The solution essential at this juncture is to cut costs as much as probable. You must state a method that estimates a viable result against the optimization problem while keeping the solution under desired limitations.
The method that computes the probable solution is known as the objective function. In the bread dimension problem, the objective function will tell how much wheat and yeast is going to be needed when a fresh batch of the bread of reduced size will get prepared.
The objective function is designed to provide the greatest value for any problem (“greatest” here means that value is either the highest or lowest, as needed by the problem), the bread dimension problem is of minimization, so the final result will provide the greatest value for the solution, meaning the lowest value.
The constraints are limitations of the objective function’s result, and it relies on the needs of the problem, which means, in a problem where the highest/lowest value is required, the constraints act as an end limit, which the solution cannot cross.
For instance, the minimum number of raw materials required to make a batch of bread will act as a constraint, which means every batch of bread requires a minimum limit of wheat and yeast. The minimization solution can’t estimate a result lower than that threshold.
A viable solution can meet all of the problem’s requirements but not necessarily be optimal. Identifying the goal and constraints is the very first part of solving an optimization problem.
Solving an optimization problem using python
Let’s resolve the optimization problem in Python. There are mainly three kinds of optimizations:
- Linear optimization
It is the procedure of searching outcomes for the finest conceivable solution from a set of parameters.
- Integer optimization
When parameters involved in the problem are more than one and involve integer or Boolean parameters then it becomes a problem solvable by Integer optimization.
- Constraint optimization
If the problem involves a very large set of parameters, and the solution is required to be found from that large set of constraints then it becomes a problem of Constraint optimization.
Below is an example of a maximization problem that will be solved by using integer optimization.
A maximization problem is one of a kind of integer optimization problem where constraints are provided for certain parameters and a viable solution is computed by converting those constraints into linear equations and then solving it out. We will be finding out a viable solution to the equations below.
Equations are: 3a+6b+2c <= 50
4a- 6b + 8c <= 45
3a + b – 5c <= 37
Here we need to maximize 3*a + 2*b + 2*c
The main stages towards resolving the maximization problem:
The essential procedures for setting up and addressing an issue are the same in each language:
- Import the libraries you’ll need.
- Make a declaration about the solver.
- Variable and parameter declaration.
- Label the method that will be used to achieve the goal.
- Invoke the solver and output the results.
The essential steps for this problem are:
Imports
from ortools.linear_solver import pywraplp
Declaration of solver
solver = pywraplp.Solver.CreateSolver('SCIP')
This is a method that will compute the problem using ortools.
SCIP: It is the argument used for the toolbox OR tools for solving mixed nonlinear problems.
Pywraplp: As ortools is based on c++, it requires a wrapper to work on python. Pywraplp is that wrapper.
Defining the variables and constraints
# a, b, and c are non-negative integer variables.
a = solver.IntVar(0.0, solver.infinity(), 'a')
b = solver.IntVar(0.0, solver.infinity(), 'b')
c = solver.IntVar(0.0, solver.infinity(), 'c')
Constraints will be defined as per the equations. For example, the first equation 3a+6b+2c <= 50 will be defined as:
cons_in1 = solver.Constraint(-solver.infinity(), 50)
cons_in1.SetCoefficient(vara, 3)
cons_in1.SetCoefficient(varb, 6)
cons_in1.SetCoefficient(varc, 2)
Objective function:
Our equation that needed to be maximized was 3*a + 2*b + 2*c. Below the code shows the steps to create an objective function for that equation.
obj_prog = solver.Objective()
obj_prog.SetCoefficient(vara, 3)
obj_prog.SetCoefficient(varb, 2)
obj_prog.SetCoefficient(varc, 2)
obj_prog.SetMaximization()
Calling the solver and printing the end result
solver.Solve()
# Print segment of program
print('Highest objective function value = %d' % solver.Objective().Value())
print()
for variable in [vara, varb, varc]:
print('%s = %d' % (variable.name(), variable.solution_value()))
Final Code:
from ortools.linear_solver import pywraplp
def Maximizationproblem():
solver = pywraplp.Solver.CreateSolver('SCIP')
vara = solver.IntVar(0.0, solver.infinity(), 'vara')
varb = solver.IntVar(0.0, solver.infinity(), 'varb')
varc = solver.IntVar(0.0, solver.infinity(), 'varc')
# 3*a + 6*b + 2*c <= 50
cons_in1 = solver.Constraint(-solver.infinity(), 50)
cons_in1.SetCoefficient(vara, 3)
cons_in1.SetCoefficient(varb, 6)
cons_in1.SetCoefficient(varc, 2)
# 4*a - 6*b + 8*c <= 45
cons_in2 = solver.Constraint(-solver.infinity(), 45)
cons_in2.SetCoefficient(vara, 4)
cons_in2.SetCoefficient(varb, -6)
cons_in2.SetCoefficient(varc, 8)
# 3*a + b - 5*c <= 37
cons_in3 = solver.Constraint(-solver.infinity(), 37)
cons_in3.SetCoefficient(vara, 3)
cons_in3.SetCoefficient(varb, 1)
cons_in3.SetCoefficient(varc, -5)
# [END constraints]
# [objective segment of program]
obj_prog = solver.Objective()
obj_prog.SetCoefficient(vara, 3)
obj_prog.SetCoefficient(varb, 2)
obj_prog.SetCoefficient(varc, 2)
obj_prog.SetMaximization()
# Calling solver
solver.Solve()
# Print segment of program
print('Highest objective function value = %d' % solver.Objective().Value())
print()
for variable in [vara, varb, varc]:
print('%s = %d' % (variable.name(), variable.solution_value()))
Maximizationproblem()
Output
Highest objective function value = 42
vara = 12
varb = 2
varc = 1
Process finished with exit code 0
Conclusion
In this article, we learned about the different types of optimizations and how those optimizations can be implemented in Python. We also learned about ortools and python wrappers. Further, we saw a complete working code that maximizes an equation from a set of three linear equations. This article will help in understanding optimization in python and create a foundation base for learners.
References
https://developers.google.com/optimization/introduction/python