By Mike Taptich
Linear Programming (LP) is one of many mathematical
You find yourself in a situation where you must allocate a limited set of resources among competing activities in the most efficient manner, given a number of restrictions.
While many engineering programs will dedicate entire courses to solving LPs, I plan to only present you with a few graphical examples that review two fundamentals of linear programing and optimization.
A constraint is a condition placed on a decision variable or combination of decision variables that must be satisfied. Constaints are what define the
In standard form, LP constraints may allow the linear combination of decision variables up to a point (i.e., less than or equal to) or hold these combinations to be equal to some value.
A one-dimensional example, R1:
A two-dimensional example, R2:
For each case, the feasible region is represented in red. Again, a solution to an LP is possible if a policy is chosen within this region.
Now, suppose that you are the sole controller over your family's household thermostat. Without knowing it, you may have been intuitively solving a constrained LP! Operating as the controller, you may decide on some dial setting (x) that will maintain the house at a respective temperature. The following are examples of constraints you may face under different LP objectives.
Your sister insists that you make the house as hot as possible, but she isn't in the mood to argue with your brother.
Your brother insists that you make the house as cold as possible, but your dad prefers that the air conditioning unit remains offline.
All conditions considered, you decide to choose the dial setting that is greatest from your current temperature setting.
In this last example, the feasible region or solution set was all the possible temperatures within your sister and father's preferential constraints. Given your final objective, you decide on the optimal policy of 78 degrees F. This choice is referred to as a
An infeasible solution implies that the feasible region is over-constrained and no solution is possible. In our previous examples, you would arrive at an infeasbile solution if your brother's maximum temperature preference required you to use the broken AC unit (i.e., colder than applying strictly heat).
An unbounded solution implies the solution space continues forever in at least one direction. In our previous examples, you would arrive at a unbounded solution if your thermostat could always increase the temperature in your house (i.e., approaches infinity possible solutions).
Did you notice that your optimal choice for the temperature dial always seemed to lie somewhere along a bound? Well, that is because unique solutions of LPs will never fall within the
To ellborate more on my last point, I have provided you with three additional examples: Problem 1, Problem 2, Problem 3. Now, drag the blue ball to the coordinate in the x-y space that optimizes each LP. Feel free to build your own problems, too.
(Hint: If you over-constrain your circle, click the feasile region and it will reappear.)
In each problem, you will find that the optimal policy, X* = (x*, y*), falls along the boundary of the feasible region. This makes sense if you think about your decision-making process in terms of your objective: why settle for less than you deserve!
Thus, X* is called an extreme point. These extreme points exists if and only if you cannot represent the point as a convex combination of points that fall within the feasible region. You may be asking yourself, "
In two dimensions (x,y), a convex combination of two points is simply a line drawn between them. Since extreme points by nature fall along the boundary of the
Extreme points and bounding are the fundamental building blocks used in algorithms that efficiently
Mike Taptich is a PhD student in the Energy, Civil Infrastructure, and Climate program at UC Berkeley. He is also a co-founder of the Visualizing Urban Data Idealab.