You've probably faced this scenario. Or not. But imagine you want to buy rice, beans and meat to cook, you know you need at least 1.5 kg of rice at 400 naira per kg but not more than 4kg, 1.5kg of beans at 800 naira per kg but not more than 3kg, and you are sure you need at least 1 kg of meat at 500 naira per kilo. Now, you also know that the total kg of food that satisfies you has to be at least 9.5 kg. How do you decide how to allocate your limited resources to ensure you are satisfied and still spend the least possible amount of money?
This is a typical example of an optimization problem we face daily. The solution to this is very simple and you don't need python for it, but it could be a very good example to introduce you to the concept before a more complex one like the type I faced at work which involved bond prices and calculating the probability of defaults.
Essentially optimization is the action of making the best or most effective use of a situation or resource.
So what am I going to try to do in this article?
I'll try to explain the scipy.optimize linprog module with a simple example?
Make it possible for you to perform your optimization without having to read through the whole documentation. (a bad practice sometimes though).
Give you an exercise to show you understand the application of the python library.
It is important to note, however, that the technical details of the library and methods used here are not gone into in detail. This article will help you if you simply want to understand the basics and use it as quickly as possible.
What python libraries are used for optimization?
Well, I found 3: the Scipy optimize library, the Pulp library, and the Apm python library. Am I going to talk about all 3? No way. I’ll talk about just the Scipy.optimize ( that’s the only one I know nearly enough to write anything about😂 )
Now scipy.optimize module is very large but I’ll show with examples, two modules that I found very useful and they are: the scipy.optimize.linprog and the Scipy.optimize.minimize libraries. This article will focus on the former and then I will write on the latter in part 2(or make a youtube video even).
scipy.optimize.linprog
Enough of the boring talk. Let’s jump in with an example. Remember the scenario presented at the beginning of this article. That is a typical one you can solve with Scipy.optimize. linprog. Let’s jump in.
Remember the scenario from the opening paragragh, What variable are we trying to optimize in that scenario? Simple right? The cost of purchasing those 3 items. what form of optimization are we doing here? we're minimizing the cost.
PS: It is worth noting at this point that optimization could be a minimization or a maximization of an objective function.
Let a be the number of kilos of rice, b the number of kilos of beans and c the number of kilos of meat. (a , b and c are the input variables.) The cost could then be represented as y. In mathematical form,
$$Y= 400a + 800b + 500c$$
The constraints are:
$$a>=1.5, a<=4, b>=1.5, b<=3 c>= 1, a+b+c>=9.5.$$
Y is described as the objective function you want to optimize. In this case, we are minimizing the cost of getting rice(a), beans(b) and meat(c). The code to get this done would be:
import scipy.optimize as sci
y = [400, 800, 500]
LHS = [[-1, -1, -1]]
RHS = [-9.5]
a_bounds = (1.5, 4)
b_bounds = (1.5, 3)
c_bounds = (1, None)
result = sci.linprog(y, A_ub = LHS, b_ub = RHS,
bounds= [a_bounds, b_bounds, c_bounds])
Let us walk through this line by line:
we first import the library as custom practice. once you have python installed, that part is pretty straightforward.
The next 6 lines are variable assignments so let us Take note of Line 8. This is where the linear programming(optimization method) is actually carried out. so I will walk through the different arguments you can see in that line.
we first call the sci.linprog method and call it 'result'. now the arguments within the bracket are thus:
y: the function to minimize notice that when defining y in line 2, the linprog method takes in the objective function as a sort of matrix with the coefficients of the input variables as the values in order.
A_ub: This takes the form of a list. this list is a list of the coefficients of the constraints. in our case, only one constraint as such exists that combines the 3 input variables a, b and c. notice that the signs are negative right? this is because the inequality on which this method is built on is the less than or equal to(<=) inequality. so if your constraint is a greater than or equal to(>=), it is necessary to convert it to the <= and the simple way to do this is to change the signs. I defined this as 'LHS' as seen in line 3.
b_ub: This is a list of the right-hand side of the constraints in A_ub above. notice that since we have only one constraint in A_ub, the list 'RHS' which represents b_ub has only one content in the list.
bounds: bounds is a list of the upper and lower boundaries for each input variable(a, b,c) hence the contents a_bounds, b_bounds and c_bounds represent tuples of the lower and upper limits of this variable respectively for example since rice must be at least 1.5kg and at most 4kg, the 'a_bounds' is a tuple (1.5, 4)
After line 8 is run, to see the respective answers for a, b and c, we call on the x method of the result. while to see the value of y after minimization in this case, we call the fun method of the result. see below:
result.x
result.fun
The result.x should return an array containing a, b and c in that order. in our case, ([4, 1.5, 4])
array([4. , 1.5, 4. ])
showing the kgs of rice, beans and meat that would result in the least cost involved in satisfying the conditions presented by the scenario.
result.fun should return 4799.99 which shows the least possible cost if we buy the kgs of rice, beans and meat indicated above.
Note: if we had to maximize an objective function, we simply perform a minimization on the negative of that function.
Quick Exercise
Now let us try a different exercise: Imagine we have to maximize an objective function
$$y = -3a+2.5b -c$$
with these constraints:
$$a-b>=0, 2a+b+c<=3$$
$$ a>=1, b<=3$$
This should be your code:
import scipy.optimize as sci
y = [3, -2.5, 1]
LHS = [[-1, 1, 0], [2, 1, 1]]
RHS = [0, 3]
a_bounds = (1, None)
b_bounds = (None, 3)
c_bounds = (None, None)
result = sci.linprog(y, A_ub = LHS, b_ub = RHS,
bounds= [a_bounds, b_bounds, c_bounds])
result.x
This should be your result:
array([ 3.43533771e+11, -2.60322260e+11, -2.06809962e+12])
Now in real applications like in the finance and engineering world, as I said, the objective function you want to optimize(minimize or maximize) may not be easily represented in a simple formula like y in the 2 examples here. It may most likely be a more complicated function with loops and sub-functions (in mathematical terms, it may not be easily represented as a matrix of coefficients). It is in cases like these that the second method of the scipy.optimize.minimize module comes in handy.
I hoped to discuss it in this article but this is getting too long. so, Did you like this article? should I make a video instead for the scipy.optimize.minimize module for optimization? let me know in the comments. If there are typos or scenarios not very clearly presented, let me know too. I have a lot on my plate and I had to rush to complete this.
see you soon.