The Glop Linear Solver

Overview

The primary OR-Tools linear optimization solver is Glop, Google's linear programming system. It's fast, memory efficient, and numerically stable. To learn how to use Glop to solve a simple linear problem in all of the supported languages, see A simple linear optimization example.

Once you've taken a look at that section, you can move on to a more complicated linear optimization problem, the Stigler diet.

Using Glop with the OR-Tools linear solver wrapper

To use the Glop solver, you first declare it with the OR-Tools linear solver wrapper — a wrapper for several linear optimization libraries. The following sections show how to use a MIP solver in C++ and Python. (Doing so in Java or C# is similar to the C++ example.)

Using Glop in C++

To use Glop in C++:
  1. Declare the linear solver wrapper.
    void RunLinearExample(
      MPSolver::OptimizationProblemType optimization_problem_type) {
      MPSolver solver("LinearExample", optimization_problem_type);
  2. Call the solver wrapper with the argument GLOP_LINEAR_PROGRAMMING, which tells it to use Glop.
      RunLinearExample(MPSolver::GLOP_LINEAR_PROGRAMMING);
    The input is passed to the solver wrapper through the OptimizationProblemType method.

Using Glop in Python

To use Glop in Python:

  1. Declare the solver using the Python wrapper pywraplp.
    from ortools.linear_solver import pywraplp
    
    def main():
      # Instantiate a Glop solver, naming it LinearExample.
      solver = pywraplp.Solver('LinearExample',
                               pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
    Note that this also passes the argument GLOP_LINEAR_PROGRAMMING to the solver.
  2. Call the solver.
      solver.Solve()
    You don't need the GLOP_LINEAR_PROGRAMMING argument, as it's already bundled with the solver.
A simple linear optimization example shows examples of using Glop in all of the supported languages.

The Stigler diet

In this section, we show how to solve a classic problem called 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.

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 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.

The following sections present a Python program that solves the Stigler diet problem.

Data for the problem

The the following code creates a Python array data for the nutritional data table, and an array nutrients for the minimum nutrient requirements in any solution.

  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]]

Create the variables and define the objective

The following code creates the variables and defines the objective function for the problem.

  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()

The method MakeNumVar creates one variable, food[i], for each row of the table. As mentioned previously, the nutritional data is per dollar, so food[i] is the amount of money to spend on foodstuff i.

The objective function is the total cost of the food, which is the sum of the variables food[i].

The method SetCoefficient sets the coefficients of the objective function, which are all 1 in this case. Finally, the SetMinimization declares this to be a minimization problem.

Define the constraints

The constraints for Stigler diet require the total amount of the nutrients provided by all foods to be at least the minimum requirement for each nutrient. Next, we write these constraints as inequalities involving the arrays data and nutrients, and the variables food[i].

First, the amount of nutrient i provided by food j per dollar is data[j][i+3] (we add 3 to the column index because the nutrient data begins in the fourth column of data.) Since the amount of money to be spent on food j is food[j], the amount of nutrient i provided by food j is $$data[j][i+3] \cdot food[j]$$ Finally, since the minimum requirement for nutrient i is nutrients[i][1], we can write constraint i as follows: $$\sum_{j} data[j][i+3] \cdot food[j] \geq nutrients[i][1] \;\;\;\;\; (1)$$ The following code defines these constraints.

  # 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])
The Python method Constraint (corresponding to the C++ method MakeRowConstraint) creates the constraints for the problem. For each i,
Constraint(nutrients[i][1], solver.infinity)
creates a constraint in which a linear combination of the variables food[j] (defined next) is greater than or equal to nutrients[i][1]. The coefficients of the linear expression are defined by the method SetCoefficient as follows:
SetCoefficient(food[j], data[j][i+3]
This sets the coefficient of food[j] to be data[j][i+3].

Putting this all together, the code defines the constraints expressed in (1) above.

Declare the solver

The following code declares the solver for the problem.

  solver = pywraplp.Solver('SolveStigler',
                           pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
pywraplp is a Python wrapper for the C++ linear solver wrapper. The argument GLOP_LINEAR_PROGRAMMING tells the linear solver wrapper to use Glop.

Invoke the solver and display the results

The following code invokes the solver and displays the results.

  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.'

Glop solves the problem 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

Complete code for the program

The complete code for the Stigler diet program is shown below.

     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__':
  main()

Enviar comentarios sobre…