Optimization and Linear Programming
Optimization; a word that we all use in our daily lives. But what is it essentially? How to optimize anything programmatically? All of your answers will be answered in the following paragraphs.
What is Optimization?
We all try to make the most out of the finite resources we have in our everyday life. It is essentially the way of life. Everything around us, from electric appliances to our mechanical cars, uses optimization.
Holistically, it is a math problem. Optimization is the process of finding the maximum or minimum value of a given objective by controlling a set of decisions in a constrained environment. Here, the objective can be anything, for instance, traveling to specific cities under limited funds or finding the best stocks to invest in to maximize profits. The applications are endless!
One of the simplest ways to optimize is using linear programming (LP). Several simplifying assumptions allow you to handle some very complex optimization problems. Analysts are bound to come across applications and problems to be solved by linear programming.
Introduction to Linear Programming
Linear programming is essentially a subset of optimization. In linear programming or linear optimization, we attempt to find an optimal value for a linear objective function for a system of linear constraints using a variety of decision variables.
Linear programming can be used to solve a problem when the goal of the problem is to maximize some value, and there is a linear system of inequalities defines the constraints on the problem.
Constraint ~ Constraints are defined as inequalities whose values determine how variables have their values. Linear programming requires that all constraints be linear inequalities.
Objective Function ~ The objective function is a means to maximize (or minimize) something. This something is a numeric value. In the real world, it could be the cost of a project, a production quantity, profit value, or even materials saved from a streamlined process. With the objective function, you are trying to arrive at a target for output, profit, resource use, etc
Objective Function coefficient ~ The amount by which the objective function value would change when one unit of a decision variable is altered is given by the corresponding objective function coefficient.
Decision Variables ~ These are the unknown quantities that are expected to be estimated as an output of the Linear Programming problem solution.
To understand things better, let us look at a simple optimization problem.
Suppose we want to maximize the function z = f(x,y)-> z = x + 2y
Subject to the following constraints:
- 2x + y ≤ 20
- 4x + 5y ≤ 10
- x + 2y ≥ -2
x ≥ 0
y ≥ 0
We need to determine the independent variables, in this case, x and y, which are known as the decision variables. The function of the decision variables to be maximized or minimized — in this case, z — is called the objective function, the cost function, or just the goal. The inequalities we need to satisfy are called inequality constraints.
Let us try to visualize the problem:
Here, the equation -2x + y ≤ 20 is represented by red line, -4x + 5y ≤ 10 by blue line and -x + 2y ≥ -2 by yellow line. After applying the last two inequalities, the bounded area represented by grey color gives us the universe of all feasible solutions. Now, our aim could either be to MAXIMIZE or MINIMIZE the objective function. The feasible solution that corresponds to maximal z is the optimal solution (the intersection of the red and blue lines in this case). If you were trying to minimize the objective function instead, then the optimal solution would correspond to its feasible minimum (origin).
Infeasible Linear Programming Problem — Infeasibility refers to a linear programming problem that does not have a solution. It usually occurs when no solution can satisfy all constraints simultaneously.
Unbounded Linear Programming Problem — An unbounded linear programming problem is one whose feasible region is not bounded and whose solution is not finite. Essentially, this means that one of your variables isn’t constrained and can reach positive or negative infinity, meaning that the objective is also infinite.
Python library for Linear Programming
There are many implementations of python libraries for linear programming. Most valuables of them are:
- PuLP and/or Pyomo. PuLP is an LP modeler written in Python. Pyomo is a Python-based, open-source optimization modeling language with a diverse set of optimization capabilities.
- CVXOPT is written by Lieven Vandenberghe and some of his collaborators. CVXOPT is a free software package for convex optimization based on the Python programming language.
- Or-tools Google’s software suite for combinatorial optimization. This is an open-source, fast, and portable software suite for solving combinatorial optimization problems.
- Scipy.optimize.linprog is the Python library to minimize a linear objective function subject to linear equality and inequality constraints.
To get started, one can come up with a problem try optimizing it programmatically. The best way to learn is to start doing. I will link some resources below and I wish you all the best!
Resources:
I hope the article above helps you with understanding the whole chaos that is around this topic. For now, let’s end it here. Reach out to me on Twitter if you want to give feedback or have any queries.
Peace 👋
