Overview
Linear optimization or linear programming is the name given to computing the best solution to a problem modeled as a set of linear relationships. These problems arise in many scientific and engineering disciplines. (The word "programming" is a bit of a misnomer, similar to how "computer" once meant "a person who computes." Here, "programming" refers to the arrangement of a plan, rather than programming in a computer language.)
Glop is Google's linear programming system, which we've open sourced. It's fast, memory efficient, and numerically stable.
A simple example
Let's take a closer look at the linear programming example from the section Running or-tools Programs. The example uses Glop to solve a simple system of linear inequalities.
- Maximize 3x + 4y subject to the following constraints:
-
x + 2y ≤ 14 3x – y ≥ 0 x – y ≤ 2
The constraints define the feasible region for the problem, which is the triangle and its interior, shown below. The linear programming problem is to find the maximum value of 3x + 4y over the feasible region.
Create the solver
The following code creates the solver for the problem.
from ortools.linear_solver import pywraplp
def main(_):
# Instantiate a Glop solver, naming it SolveSimpleSystem.
solver = pywraplp.Solver('SolveSimpleSystem',
pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
The program begins by importing pywraplp, a Python wrapper for
the underlying C++ code, and then uses it to create an instance of the solver
with the GLOP_LINEAR_PROGRAMMING option.
Define the variables
The following code defines the variables in the problem.
# Create the two variables in our system of equations, # and let them take on any value. x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x') y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')
In this case, both x and
y can take on any values between negative and positive
infinity. You can set finite limits for x or
y — for example,
x = solver.NumVar(-4, 6, 'x')
— but this is just as easily be done by defining constraints, as described in the
next section.
Define the constraints
The following code defines the constraints in the problem:
# Constraint 1: x + 2y <= 14. constraint1 = solver.Constraint(-solver.infinity(), 14) constraint1.SetCoefficient(x, 1) constraint1.SetCoefficient(y, 2) # Constraint 2: 3x - y >= 0. constraint2 = solver.Constraint(0, solver.infinity()) constraint2.SetCoefficient(x, 3) constraint2.SetCoefficient(y, -1) # Constraint 3: x - y <= 2. constraint3 = solver.Constraint(-solver.infinity(), 2) constraint3.SetCoefficient(x, 1) constraint3.SetCoefficient(y, -1)
Let's take a look at how the first constraint, x + 2
y ≤ 14
, is defined. First, the Constraint method
defines an inequality, constraint1, whose left hand side is ≤ 14.
constraint1 = solver.Constraint(-solver.infinity(), 14) # <= 14
Next, the SetCoefficient method sets the coefficients of
x and y in
the left hand side of the inequality constraint1:
constraint1.SetCoefficient(x, 1) # x constraint1.SetCoefficient(y, 2) # 2y
Define the objective
The following code defines the objective function for the problem — the function that you want to maximize. In this case, the objective function is 3x + 4y.
.# Define our objective: maximizing 3x + 4y. objective = solver.Objective() objective.SetCoefficient(x, 3) objective.SetCoefficient(y, 4) objective.SetMaximization()
The SetCoefficient method sets the coefficients of the objective function. The
SetMaximization method makes this a maximization problem.
Invoke the solver
The following code calls the solver and prints the solution.
# Solve the system.
status = solver.Solve()
opt_solution = 3 * x.solution_value() + 4 * y.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 = ', x.solution_value())
print('y = ', y.solution_value())
# The objective value of the solution.
print('Optimal objective value =', opt_solution)
The x and y values of the solution are given by x.solution_value() and
y.solution_value().
The entire program
Finally, here is the entire Python program and its output.
from __future__ import print_function
from google.apputils import app
from ortools.linear_solver import pywraplp
def main(_):
# Instantiate a Glop solver, naming it SolveSimpleSystem.
solver = pywraplp.Solver('SolveSimpleSystem',
pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
# Create the two variables in our system of equations,
# and let them take on any value.
x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')
y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')
# Constraint 1: x + 2y <= 14.
constraint1 = solver.Constraint(-solver.infinity(), 14)
constraint1.SetCoefficient(x, 1)
constraint1.SetCoefficient(y, 2)
# Constraint 2: 3x - y >= 0.
constraint2 = solver.Constraint(0, solver.infinity())
constraint2.SetCoefficient(x, 3)
constraint2.SetCoefficient(y, -1)
# Constraint 3: x - y <= 2.
constraint3 = solver.Constraint(-solver.infinity(), 2)
constraint3.SetCoefficient(x, 1)
constraint3.SetCoefficient(y, -1)
# Define our objective: maximizing 3x + 4y.
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 4)
objective.SetMaximization()
# Solve the system.
status = solver.Solve()
opt_solution = 3 * x.solution_value() + 4 * y.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 = ', x.solution_value())
print('y = ', y.solution_value())
# The objective value of the solution.
print('Optimal objective value =', opt_solution)
if __name__ == '__main__':
app.run()
Output
If you save the above program as Glop.py in the my_projects directory,
you can find the solution as follows:
$ python my_projects/Glop.py Number of variables = 2 Number of constraints = 3 Optimal objective value = 34.0 x = 6.0 y = 4.0
Here is a graph showing the solution:
The dashed green line in the graph is defined by setting the objective function, 3x + 4y, equal to the maximum value of 34. For any constant c greater than 34, the line 3x + 4y = c does not intersect the feasible region.
If you think about the geometry in the above graph, you will see that in any linear optimization problem, at least one vertex of the feasible region must be a solution. As a result, you can solve small problems like these, in which the feasible region has just a few vertices, by simply calculating the objective function at each of the vertices and seeing which has the largest (or smallest) value.
In Soving an Integer Problem, we show how to solve problems similar to the preceding example, in which the solutions are required to be integers.
A not so simple example
One classic linear programming problem is the Stigler diet, named for economics Nobel laureate George Stigler, who computed an inexpensive way to fulfill basic nutritional needs given a set of foods. He posed this as a mathematical exercise, not as eating recommendations, although the notion of computing optimal nutrition has of come into vogue recently.
The Stigler diet mandated that these minimums be met:
| Nutrient | Daily Recommended Intake |
| Calories | 3,000 Calories |
| Protein | 70 grams |
| Calcium | .8 grams |
| Iron | 12 milligrams |
| Vitamin A | 5,000 IU |
| Thiamine (Vitamin B1) | 1.8 milligrams |
| Riboflavin (Vitamin B2) | 2.7 milligrams |
| Niacin | 18 milligrams |
| Ascorbic Acid (Vitamin C) | 75 milligrams |
The set of foods Stigler evaluated was a reflection of the time (1944). The nutritional data below is per dollar, not per unit, so the objective is to determine how many dollars to spend on each foodstuff.
| Commodity | Unit | 1939 price (cents) | Calories | Protein (g) | Calcium (g) | Iron (mg) | Vitamin A (IU) | Thiamine (mg) | Riboflavin (mg) | Niacin (mg) | Ascorbic Acid (mg) |
| Wheat Flour (Enriched) | 10 lb. | 36 | 44.7 | 1411 | 2 | 365 | 0 | 55.4 | 33.3 | 441 | 0 |
| Macaroni | 1 lb. | 14.1 | 11.6 | 418 | 0.7 | 54 | 0 | 3.2 | 1.9 | 68 | 0 |
| Wheat Cereal (Enriched) | 28 oz. | 24.2 | 11.8 | 377 | 14.4 | 175 | 0 | 14.4 | 8.8 | 114 | 0 |
| Corn Flakes | 8 oz. | 7.1 | 11.4 | 252 | 0.1 | 56 | 0 | 13.5 | 2.3 | 68 | 0 |
| Corn Meal | 1 lb. | 4.6 | 36.0 | 897 | 1.7 | 99 | 30.9 | 17.4 | 7.9 | 106 | 0 |
| Hominy Grits | 24 oz. | 8.5 | 28.6 | 680 | 0.8 | 80 | 0 | 10.6 | 1.6 | 110 | 0 |
| Rice | 1 lb. | 7.5 | 21.2 | 460 | 0.6 | 41 | 0 | 2 | 4.8 | 60 | 0 |
| Rolled Oats | 1 lb. | 7.1 | 25.3 | 907 | 5.1 | 341 | 0 | 37.1 | 8.9 | 64 | 0 |
| White Bread (Enriched) | 1 lb. | 7.9 | 15.0 | 488 | 2.5 | 115 | 0 | 13.8 | 8.5 | 126 | 0 |
| Whole Wheat Bread | 1 lb. | 9.1 | 12.2 | 484 | 2.7 | 125 | 0 | 13.9 | 6.4 | 160 | 0 |
| Rye Bread | 1 lb. | 9.1 | 12.4 | 439 | 1.1 | 82 | 0 | 9.9 | 3 | 66 | 0 |
| Pound Cake | 1 lb. | 24.8 | 8.0 | 130 | 0.4 | 31 | 18.9 | 2.8 | 3 | 17 | 0 |
| Soda Crackers | 1 lb. | 15.1 | 12.5 | 288 | 0.5 | 50 | 0 | 0 | 0 | 0 | 0 |
| Milk | 1 qt. | 11 | 6.1 | 310 | 10.5 | 18 | 16.8 | 4 | 16 | 7 | 177 |
| Evaporated Milk (can) | 14.5 oz. | 6.7 | 8.4 | 422 | 15.1 | 9 | 26 | 3 | 23.5 | 11 | 60 |
| Butter | 1 lb. | 30.8 | 10.8 | 9 | 0.2 | 3 | 44.2 | 0 | 0.2 | 2 | 0 |
| Oleomargarine | 1 lb. | 16.1 | 20.6 | 17 | 0.6 | 6 | 55.8 | 0.2 | 0 | 0 | 0 |
| Eggs | 1 doz. | 32.6 | 2.9 | 238 | 1.0 | 52 | 18.6 | 2.8 | 6.5 | 1 | 0 |
| Cheese (Cheddar) | 1 lb. | 24.2 | 7.4 | 448 | 16.4 | 19 | 28.1 | 0.8 | 10.3 | 4 | 0 |
| Cream | 1/2 pt. | 14.1 | 3.5 | 49 | 1.7 | 3 | 16.9 | 0.6 | 2.5 | 0 | 17 |
| Peanut Butter | 1 lb. | 17.9 | 15.7 | 661 | 1.0 | 48 | 0 | 9.6 | 8.1 | 471 | 0 |
| Mayonnaise | 1/2 pt. | 16.7 | 8.6 | 18 | 0.2 | 8 | 2.7 | 0.4 | 0.5 | 0 | 0 |
| Crisco | 1 lb. | 20.3 | 20.1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Lard | 1 lb. | 9.8 | 41.7 | 0 | 0 | 0 | 0.2 | 0 | 0.5 | 5 | 0 |
| Sirloin Steak | 1 lb. | 39.6 | 2.9 | 166 | 0.1 | 34 | 0.2 | 2.1 | 2.9 | 69 | 0 |
| Round Steak | 1 lb. | 36.4 | 2.2 | 214 | 0.1 | 32 | 0.4 | 2.5 | 2.4 | 87 | 0 |
| Rib Roast | 1 lb. | 29.2 | 3.4 | 213 | 0.1 | 33 | 0 | 0 | 2 | 0 | 0 |
| Chuck Roast | 1 lb. | 22.6 | 3.6 | 309 | 0.2 | 46 | 0.4 | 1 | 4 | 120 | 0 |
| Plate | 1 lb. | 14.6 | 8.5 | 404 | 0.2 | 62 | 0 | 0.9 | 0 | 0 | 0 |
| Liver (Beef) | 1 lb. | 26.8 | 2.2 | 333 | 0.2 | 139 | 169.2 | 6.4 | 50.8 | 316 | 525 |
| Leg of Lamb | 1 lb. | 27.6 | 3.1 | 245 | 0.1 | 20 | 0 | 2.8 | 3.9 | 86 | 0 |
| Lamb Chops (Rib) | 1 lb. | 36.6 | 3.3 | 140 | 0.1 | 15 | 0 | 1.7 | 2.7 | 54 | 0 |
| Pork Chops | 1 lb. | 30.7 | 3.5 | 196 | 0.2 | 30 | 0 | 17.4 | 2.7 | 60 | 0 |
| Pork Loin Roast | 1 lb. | 24.2 | 4.4 | 249 | 0.3 | 37 | 0 | 18.2 | 3.6 | 79 | 0 |
| Bacon | 1 lb. | 25.6 | 10.4 | 152 | 0.2 | 23 | 0 | 1.8 | 1.8 | 71 | 0 |
| Ham, smoked | 1 lb. | 27.4 | 6.7 | 212 | 0.2 | 31 | 0 | 9.9 | 3.3 | 50 | 0 |
| Salt Pork | 1 lb. | 16 | 18.8 | 164 | 0.1 | 26 | 0 | 1.4 | 1.8 | 0 | 0 |
| Roasting Chicken | 1 lb. | 30.3 | 1.8 | 184 | 0.1 | 30 | 0.1 | 0.9 | 1.8 | 68 | 46 |
| Veal Cutlets | 1 lb. | 42.3 | 1.7 | 156 | 0.1 | 24 | 0 | 1.4 | 2.4 | 57 | 0 |
| Salmon, Pink (can) | 16 oz. | 13 | 5.8 | 705 | 6.8 | 45 | 3.5 | 1 | 4.9 | 209 | 0 |
| Apples | 1 lb. | 4.4 | 5.8 | 27 | 0.5 | 36 | 7.3 | 3.6 | 2.7 | 5 | 544 |
| Bananas | 1 lb. | 6.1 | 4.9 | 60 | 0.4 | 30 | 17.4 | 2.5 | 3.5 | 28 | 498 |
| Lemons | 1 doz. | 26 | 1.0 | 21 | 0.5 | 14 | 0 | 0.5 | 0 | 4 | 952 |
| Oranges | 1 doz. | 30.9 | 2.2 | 40 | 1.1 | 18 | 11.1 | 3.6 | 1.3 | 10 | 1998 |
| Green Beans | 1 lb. | 7.1 | 2.4 | 138 | 3.7 | 80 | 69 | 4.3 | 5.8 | 37 | 862 |
| Cabbage | 1 lb. | 3.7 | 2.6 | 125 | 4.0 | 36 | 7.2 | 9 | 4.5 | 26 | 5369 |
| Carrots | 1 bunch | 4.7 | 2.7 | 73 | 2.8 | 43 | 188.5 | 6.1 | 4.3 | 89 | 608 |
| Celery | 1 stalk | 7.3 | 0.9 | 51 | 3.0 | 23 | 0.9 | 1.4 | 1.4 | 9 | 313 |
| Lettuce | 1 head | 8.2 | 0.4 | 27 | 1.1 | 22 | 112.4 | 1.8 | 3.4 | 11 | 449 |
| Onions | 1 lb. | 3.6 | 5.8 | 166 | 3.8 | 59 | 16.6 | 4.7 | 5.9 | 21 | 1184 |
| Potatoes | 15 lb. | 34 | 14.3 | 336 | 1.8 | 118 | 6.7 | 29.4 | 7.1 | 198 | 2522 |
| Spinach | 1 lb. | 8.1 | 1.1 | 106 | 0 | 138 | 918.4 | 5.7 | 13.8 | 33 | 2755 |
| Sweet Potatoes | 1 lb. | 5.1 | 9.6 | 138 | 2.7 | 54 | 290.7 | 8.4 | 5.4 | 83 | 1912 |
| Peaches (can) | No. 2 1/2 | 16.8 | 3.7 | 20 | 0.4 | 10 | 21.5 | 0.5 | 1 | 31 | 196 |
| Pears (can) | No. 2 1/2 | 20.4 | 3.0 | 8 | 0.3 | 8 | 0.8 | 0.8 | 0.8 | 5 | 81 |
| Pineapple (can) | No. 2 1/2 | 21.3 | 2.4 | 16 | 0.4 | 8 | 2 | 2.8 | 0.8 | 7 | 399 |
| Asparagus (can) | No. 2 | 27.7 | 0.4 | 33 | 0.3 | 12 | 16.3 | 1.4 | 2.1 | 17 | 272 |
| Green Beans (can) | No. 2 | 10 | 1.0 | 54 | 2 | 65 | 53.9 | 1.6 | 4.3 | 32 | 431 |
| Pork and Beans (can) | 16 oz. | 7.1 | 7.5 | 364 | 4 | 134 | 3.5 | 8.3 | 7.7 | 56 | 0 |
| Corn (can) | No. 2 | 10.4 | 5.2 | 136 | 0.2 | 16 | 12 | 1.6 | 2.7 | 42 | 218 |
| Peas (can) | No. 2 | 13.8 | 2.3 | 136 | 0.6 | 45 | 34.9 | 4.9 | 2.5 | 37 | 370 |
| Tomatoes (can) | No. 2 | 8.6 | 1.3 | 63 | 0.7 | 38 | 53.2 | 3.4 | 2.5 | 36 | 1253 |
| Tomato Soup (can) | 10 1/2 oz. | 7.6 | 1.6 | 71 | 0.6 | 43 | 57.9 | 3.5 | 2.4 | 67 | 862 |
| Peaches, Dried | 1 lb. | 15.7 | 8.5 | 87 | 1.7 | 173 | 86.8 | 1.2 | 4.3 | 55 | 57 |
| Prunes, Dried | 1 lb. | 9 | 12.8 | 99 | 2.5 | 154 | 85.7 | 3.9 | 4.3 | 65 | 257 |
| Raisins, Dried | 15 oz. | 9.4 | 13.5 | 104 | 2.5 | 136 | 4.5 | 6.3 | 1.4 | 24 | 136 |
| Peas, Dried | 1 lb. | 7.9 | 20.0 | 1367 | 4.2 | 345 | 2.9 | 28.7 | 18.4 | 162 | 0 |
| Lima Beans, Dried | 1 lb. | 8.9 | 17.4 | 1055 | 3.7 | 459 | 5.1 | 26.9 | 38.2 | 93 | 0 |
| Navy Beans, Dried | 1 lb. | 5.9 | 26.9 | 1691 | 11.4 | 792 | 0 | 38.4 | 24.6 | 217 | 0 |
| Coffee | 1 lb. | 22.4 | 0 | 0 | 0 | 0 | 0 | 4 | 5.1 | 50 | 0 |
| Tea | 1/4 lb. | 17.4 | 0 | 0 | 0 | 0 | 0 | 0 | 2.3 | 42 | 0 |
| Cocoa | 8 oz. | 8.6 | 8.7 | 237 | 3 | 72 | 0 | 2 | 11.9 | 40 | 0 |
| Chocolate | 8 oz. | 16.2 | 8.0 | 77 | 1.3 | 39 | 0 | 0.9 | 3.4 | 14 | 0 |
| Sugar | 10 lb. | 51.7 | 34.9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Corn Syrup | 24 oz. | 13.7 | 14.7 | 0 | 0.5 | 74 | 0 | 0 | 0 | 5 | 0 |
| Molasses | 18 oz. | 13.6 | 9.0 | 0 | 10.3 | 244 | 0 | 1.9 | 7.5 | 146 | 0 |
| Strawberry Preserves | 1 lb. | 20.5 | 6.4 | 11 | 0.4 | 7 | 0.2 | 0.2 | 0.4 | 3 | 0 |
Since the nutrients have all been normalized by price, our objective is simply minimizing the sum of foods.
"""Glop example: the Stigler diet."""
from google.apputils import app
from ortools.linear_solver import pywraplp
def main(_):
# Commodity, Unit, 1939 price (cents), Calories, Protein (g), Calcium (g), Iron (mg), Vitamin A (IU), Thiamine (mg), Riboflavin (mg), Niacin (mg), Ascorbic Acid (mg)
data = [
['Wheat Flour (Enriched)', '10 lb.', 36, 44.7, 1411, 2, 365, 0, 55.4, 33.3, 441, 0],
['Macaroni', '1 lb.', 14.1, 11.6, 418, 0.7, 54, 0, 3.2, 1.9, 68, 0],
['Wheat Cereal (Enriched)', '28 oz.', 24.2, 11.8, 377, 14.4, 175, 0, 14.4, 8.8, 114, 0],
['Corn Flakes', '8 oz.', 7.1, 11.4, 252, 0.1, 56, 0, 13.5, 2.3, 68, 0],
['Corn Meal', '1 lb.', 4.6, 36.0, 897, 1.7, 99, 30.9, 17.4, 7.9, 106, 0],
['Hominy Grits', '24 oz.', 8.5, 28.6, 680, 0.8, 80, 0, 10.6, 1.6, 110, 0],
['Rice', '1 lb.', 7.5, 21.2, 460, 0.6, 41, 0, 2, 4.8, 60, 0],
['Rolled Oats', '1 lb.', 7.1, 25.3, 907, 5.1, 341, 0, 37.1, 8.9, 64, 0],
['White Bread (Enriched)', '1 lb.', 7.9, 15.0, 488, 2.5, 115, 0, 13.8, 8.5, 126, 0],
['Whole Wheat Bread', '1 lb.', 9.1, 12.2, 484, 2.7, 125, 0, 13.9, 6.4, 160, 0],
['Rye Bread', '1 lb.', 9.1, 12.4, 439, 1.1, 82, 0, 9.9, 3, 66, 0],
['Pound Cake', '1 lb.', 24.8, 8.0, 130, 0.4, 31, 18.9, 2.8, 3, 17, 0],
['Soda Crackers', '1 lb.', 15.1, 12.5, 288, 0.5, 50, 0, 0, 0, 0, 0],
['Milk', '1 qt.', 11, 6.1, 310, 10.5, 18, 16.8, 4, 16, 7, 177],
['Evaporated Milk (can)', '14.5 oz.', 6.7, 8.4, 422, 15.1, 9, 26, 3, 23.5, 11, 60],
['Butter', '1 lb.', 30.8, 10.8, 9, 0.2, 3, 44.2, 0, 0.2, 2, 0],
['Oleomargarine', '1 lb.', 16.1, 20.6, 17, 0.6, 6, 55.8, 0.2, 0, 0, 0],
['Eggs', '1 doz.', 32.6, 2.9, 238, 1.0, 52, 18.6, 2.8, 6.5, 1, 0],
['Cheese (Cheddar)', '1 lb.', 24.2, 7.4, 448, 16.4, 19, 28.1, 0.8, 10.3, 4, 0],
['Cream', '1/2 pt.', 14.1, 3.5, 49, 1.7, 3, 16.9, 0.6, 2.5, 0, 17],
['Peanut Butter', '1 lb.', 17.9, 15.7, 661, 1.0, 48, 0, 9.6, 8.1, 471, 0],
['Mayonnaise', '1/2 pt.', 16.7, 8.6, 18, 0.2, 8, 2.7, 0.4, 0.5, 0, 0],
['Crisco', '1 lb.', 20.3, 20.1, 0, 0, 0, 0, 0, 0, 0, 0],
['Lard', '1 lb.', 9.8, 41.7, 0, 0, 0, 0.2, 0, 0.5, 5, 0],
['Sirloin Steak', '1 lb.', 39.6, 2.9, 166, 0.1, 34, 0.2, 2.1, 2.9, 69, 0],
['Round Steak', '1 lb.', 36.4, 2.2, 214, 0.1, 32, 0.4, 2.5, 2.4, 87, 0],
['Rib Roast', '1 lb.', 29.2, 3.4, 213, 0.1, 33, 0, 0, 2, 0, 0],
['Chuck Roast', '1 lb.', 22.6, 3.6, 309, 0.2, 46, 0.4, 1, 4, 120, 0],
['Plate', '1 lb.', 14.6, 8.5, 404, 0.2, 62, 0, 0.9, 0, 0, 0],
['Liver (Beef)', '1 lb.', 26.8, 2.2, 333, 0.2, 139, 169.2, 6.4, 50.8, 316, 525],
['Leg of Lamb', '1 lb.', 27.6, 3.1, 245, 0.1, 20, 0, 2.8, 3.9, 86, 0],
['Lamb Chops (Rib)', '1 lb.', 36.6, 3.3, 140, 0.1, 15, 0, 1.7, 2.7, 54, 0],
['Pork Chops', '1 lb.', 30.7, 3.5, 196, 0.2, 30, 0, 17.4, 2.7, 60, 0],
['Pork Loin Roast', '1 lb.', 24.2, 4.4, 249, 0.3, 37, 0, 18.2, 3.6, 79, 0],
['Bacon', '1 lb.', 25.6, 10.4, 152, 0.2, 23, 0, 1.8, 1.8, 71, 0],
['Ham, smoked', '1 lb.', 27.4, 6.7, 212, 0.2, 31, 0, 9.9, 3.3, 50, 0],
['Salt Pork', '1 lb.', 16, 18.8, 164, 0.1, 26, 0, 1.4, 1.8, 0, 0],
['Roasting Chicken', '1 lb.', 30.3, 1.8, 184, 0.1, 30, 0.1, 0.9, 1.8, 68, 46],
['Veal Cutlets', '1 lb.', 42.3, 1.7, 156, 0.1, 24, 0, 1.4, 2.4, 57, 0],
['Salmon, Pink (can)', '16 oz.', 13, 5.8, 705, 6.8, 45, 3.5, 1, 4.9, 209, 0],
['Apples', '1 lb.', 4.4, 5.8, 27, 0.5, 36, 7.3, 3.6, 2.7, 5, 544],
['Bananas', '1 lb.', 6.1, 4.9, 60, 0.4, 30, 17.4, 2.5, 3.5, 28, 498],
['Lemons', '1 doz.', 26, 1.0, 21, 0.5, 14, 0, 0.5, 0, 4, 952],
['Oranges', '1 doz.', 30.9, 2.2, 40, 1.1, 18, 11.1, 3.6, 1.3, 10, 1998],
['Green Beans', '1 lb.', 7.1, 2.4, 138, 3.7, 80, 69, 4.3, 5.8, 37, 862],
['Cabbage', '1 lb.', 3.7, 2.6, 125, 4.0, 36, 7.2, 9, 4.5, 26, 5369],
['Carrots', '1 bunch', 4.7, 2.7, 73, 2.8, 43, 188.5, 6.1, 4.3, 89, 608],
['Celery', '1 stalk', 7.3, 0.9, 51, 3.0, 23, 0.9, 1.4, 1.4, 9, 313],
['Lettuce', '1 head', 8.2, 0.4, 27, 1.1, 22, 112.4, 1.8, 3.4, 11, 449],
['Onions', '1 lb.', 3.6, 5.8, 166, 3.8, 59, 16.6, 4.7, 5.9, 21, 1184],
['Potatoes', '15 lb.', 34, 14.3, 336, 1.8, 118, 6.7, 29.4, 7.1, 198, 2522],
['Spinach', '1 lb.', 8.1, 1.1, 106, 0, 138, 918.4, 5.7, 13.8, 33, 2755],
['Sweet Potatoes', '1 lb.', 5.1, 9.6, 138, 2.7, 54, 290.7, 8.4, 5.4, 83, 1912],
['Peaches (can)', 'No. 2 1/2', 16.8, 3.7, 20, 0.4, 10, 21.5, 0.5, 1, 31, 196],
['Pears (can)', 'No. 2 1/2', 20.4, 3.0, 8, 0.3, 8, 0.8, 0.8, 0.8, 5, 81],
['Pineapple (can)', 'No. 2 1/2', 21.3, 2.4, 16, 0.4, 8, 2, 2.8, 0.8, 7, 399],
['Asparagus (can)', 'No. 2', 27.7, 0.4, 33, 0.3, 12, 16.3, 1.4, 2.1, 17, 272],
['Green Beans (can)', 'No. 2', 10, 1.0, 54, 2, 65, 53.9, 1.6, 4.3, 32, 431],
['Pork and Beans (can)', '16 oz.', 7.1, 7.5, 364, 4, 134, 3.5, 8.3, 7.7, 56, 0],
['Corn (can)', 'No. 2', 10.4, 5.2, 136, 0.2, 16, 12, 1.6, 2.7, 42, 218],
['Peas (can)', 'No. 2', 13.8, 2.3, 136, 0.6, 45, 34.9, 4.9, 2.5, 37, 370],
['Tomatoes (can)', 'No. 2', 8.6, 1.3, 63, 0.7, 38, 53.2, 3.4, 2.5, 36, 1253],
['Tomato Soup (can)', '10 1/2 oz.', 7.6, 1.6, 71, 0.6, 43, 57.9, 3.5, 2.4, 67, 862],
['Peaches, Dried', '1 lb.', 15.7, 8.5, 87, 1.7, 173, 86.8, 1.2, 4.3, 55, 57],
['Prunes, Dried', '1 lb.', 9, 12.8, 99, 2.5, 154, 85.7, 3.9, 4.3, 65, 257],
['Raisins, Dried', '15 oz.', 9.4, 13.5, 104, 2.5, 136, 4.5, 6.3, 1.4, 24, 136],
['Peas, Dried', '1 lb.', 7.9, 20.0, 1367, 4.2, 345, 2.9, 28.7, 18.4, 162, 0],
['Lima Beans, Dried', '1 lb.', 8.9, 17.4, 1055, 3.7, 459, 5.1, 26.9, 38.2, 93, 0],
['Navy Beans, Dried', '1 lb.', 5.9, 26.9, 1691, 11.4, 792, 0, 38.4, 24.6, 217, 0],
['Coffee', '1 lb.', 22.4, 0, 0, 0, 0, 0, 4, 5.1, 50, 0],
['Tea', '1/4 lb.', 17.4, 0, 0, 0, 0, 0, 0, 2.3, 42, 0],
['Cocoa', '8 oz.', 8.6, 8.7, 237, 3, 72, 0, 2, 11.9, 40, 0],
['Chocolate', '8 oz.', 16.2, 8.0, 77, 1.3, 39, 0, 0.9, 3.4, 14, 0],
['Sugar', '10 lb.', 51.7, 34.9, 0, 0, 0, 0, 0, 0, 0, 0],
['Corn Syrup', '24 oz.', 13.7, 14.7, 0, 0.5, 74, 0, 0, 0, 5, 0],
['Molasses', '18 oz.', 13.6, 9.0, 0, 10.3, 244, 0, 1.9, 7.5, 146, 0],
['Strawberry Preserves', '1 lb.', 20.5, 6.4, 11, 0.4, 7, 0.2, 0.2, 0.4, 3, 0]];
# Nutrient minimums.
nutrients = [
['Calories (1000s)', 3],
['Protein (grams)', 70],
['Calcium (grams)', 0.8],
['Iron (mg)', 12],
['Vitamin A (1000 IU)', 5],
['Vitamin B1 (mg)', 1.8],
['Vitamin B2 (mg)', 2.7],
['Niacin (mg)', 18],
['Vitamin C (mg)', 75]]
# Instantiate a Glop solver, naming it SolveStigler.
solver = pywraplp.Solver('SolveStigler',
pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
# Declare an array to hold our nutritional data.
food = [[]] * len(data)
# Objective: minimize the sum of (price-normalized) foods.
objective = solver.Objective()
for i in range(0, len(data)):
food[i] = solver.NumVar(0.0, solver.infinity(), data[i][0])
objective.SetCoefficient(food[i], 1)
objective.SetMinimization()
# Create the constraints, one per nutrient.
constraints = [0] * len(nutrients)
for i in range(0, len(nutrients)):
constraints[i] = solver.Constraint(nutrients[i][1], solver.infinity())
for j in range(0, len(data)):
constraints[i].SetCoefficient(food[j], data[j][i+3])
# Solve!
status = solver.Solve()
if status == solver.OPTIMAL:
# Display the amounts (in dollars) to purchase of each food.
price = 0
num_nutrients = len(data[i]) - 3
nutrients = [0] * (len(data[i]) - 3)
for i in range(0, len(data)):
price += food[i].solution_value()
for nutrient in range(0, num_nutrients):
nutrients[nutrient] += data[i][nutrient+3] * food[i].solution_value()
if food[i].solution_value() > 0:
print "%s = %f" % (data[i][0], food[i].solution_value())
print 'Optimal annual price: $%.2f' % (365 * price)
else: # No optimal solution was found.
if status == solver.FEASIBLE:
print 'A potentially suboptimal solution was found.'
else:
print 'The solver could not solve the problem.'
if __name__ == '__main__':
app.run()
In 1944, Stigler calculated the best answer he could, noting with sadness:
"...there does not appear to be any direct method of finding the minimum of of a linear function subject to linear conditions."
He found a diet that cost $39.93 per year, in 1939 dollars. In 1947, Jack Laderman used the simplex method (then, a recent invention!) to determine the optimal solution. It took 120 man days of nine clerks on desk calculators to arrive at the answer.
Glop solves it on a typical computer in less than 300 milliseconds:
$ PYTHONPATH=src python stigler.py Wheat Flour (Enriched) = 0.029519 Liver (Beef) = 0.001893 Cabbage = 0.011214 Spinach = 0.005008 Navy Beans, Dried = 0.061029 Optimal annual price: $39.66
