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. The next section shows how to use Glop to solve a simple linear problem in all of the supported languages.

Note. To run the program below, you need to install OR-Tools.

A simple example

Here's a simple example of a linear programming problem.

Maximize 3x + 4y subject to the following constraints:

x + 2y	≤	14
3x – y	≥	0
x – y	≤	2

Both the objective function, 3x + 4y, and the constraints are given by linear expressions, which makes this a linear problem.

The constraints define the feasible region, which is the triangle shown below, including its interior.

The following sections explain how to solve the problem.

Create the variables

First, create variables x and y whose values are in the range from 0 to infinity.

Python

x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')
y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')

C++

const double infinity = solver.infinity();
// x and y are non-negative variables.
MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");
LOG(INFO) << "Number of variables = " << solver.NumVariables();

Java

double infinity = java.lang.Double.POSITIVE_INFINITY;
// x and y are continuous non-negative variables.
MPVariable x = solver.makeNumVar(0.0, infinity, "x");
MPVariable y = solver.makeNumVar(0.0, infinity, "y");
System.out.println("Number of variables = " + solver.numVariables());

C#

Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");

Define the constraints

Next, define the constraints on the variables. Give each constraint a unique name (such as constraint0), and then define the coefficients for the constaint.

Python

# Constraint 0: x + 2y <= 14.
constraint0 = solver.Constraint(-solver.infinity(), 14)
constraint0.SetCoefficient(x, 1)
constraint0.SetCoefficient(y, 2)

# Constraint 1: 3x - y >= 0.
constraint1 = solver.Constraint(0, solver.infinity())
constraint1.SetCoefficient(x, 3)
constraint1.SetCoefficient(y, -1)

# Constraint 2: x - y <= 2.
constraint2 = solver.Constraint(-solver.infinity(), 2)
constraint2.SetCoefficient(x, 1)
constraint2.SetCoefficient(y, -1)

C++

// x + 2*y <= 14.
MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 14.0);
c0->SetCoefficient(x, 1);
c0->SetCoefficient(y, 2);

// 3*x - y >= 0.
MPConstraint* const c1 = solver.MakeRowConstraint(0.0, infinity);
c1->SetCoefficient(x, 3);
c1->SetCoefficient(y, -1);

// x - y <= 2.
MPConstraint* const c2 = solver.MakeRowConstraint(-infinity, 2.0);
c2->SetCoefficient(x, 1);
c2->SetCoefficient(y, -1);
LOG(INFO) << "Number of constraints = " << solver.NumConstraints();

Java

// x + 2*y <= 14.
MPConstraint c0 = solver.makeConstraint(-infinity, 14.0, "c0");
c0.setCoefficient(x, 1);
c0.setCoefficient(y, 2);

// 3*x - y >= 0.
MPConstraint c1 = solver.makeConstraint(0.0, infinity, "c1");
c1.setCoefficient(x, 3);
c1.setCoefficient(y, -1);

// x - y <= 2.
MPConstraint c2 = solver.makeConstraint(-infinity, 2.0, "c2");
c2.setCoefficient(x, 1);
c2.setCoefficient(y, -1);
System.out.println("Number of constraints = " + solver.numConstraints());

C#

// x + 2y <= 14.
Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 14.0);
c0.SetCoefficient(x, 1);
c0.SetCoefficient(y, 2);

// 3x - y >= 0.
Constraint c1 = solver.MakeConstraint(0.0, double.PositiveInfinity);
c1.SetCoefficient(x, 3);
c1.SetCoefficient(y, -1);

// x - y <= 2.
Constraint c2 = solver.MakeConstraint(double.NegativeInfinity, 2.0);
c2.SetCoefficient(x, 1);
c2.SetCoefficient(y, -1);

Define the objective function

The following code defines the objective function, 3x + 4y, and specifies that this is a maximization problem.

Python

# Objective function: 3x + 4y.
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 4)
objective.SetMaximization()

C++

// Objective function: 3x + 4y.
MPObjective* const objective = solver.MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 4);
objective->SetMaximization();

Java

// Maximize 3 * x + 4 * y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 4);
objective.setMaximization();

C#

// Objective function: 3x + 4y.
Objective objective = solver.Objective();
objective.SetCoefficient(x, 3);
objective.SetCoefficient(y, 4);
objective.SetMaximization();

Declare the solver

The following code declares the solver. MPsolver is a wrapper for several different solvers, including Glop. Appending GLOP_LINEAR_PROGRAMMING tells the solver to use Glop.

Python

solver = pywraplp.Solver('LinearProgrammingExample',
                         pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

C++

MPSolver solver("LinearExample", MPSolver::GLOP_LINEAR_PROGRAMMING);

Java

MPSolver solver = new MPSolver(
    "LinearProgrammingExample", MPSolver.OptimizationProblemType.GLOP_LINEAR_PROGRAMMING);

C#

MPSolver solver = new MPSolver("LinearProgrammingExample", "GLOP_LINEAR_PROGRAMMING");

Invoke the solver

The following code invokes the solver.

Python

solver.Solve()

C++

const MPSolver::ResultStatus result_status = solver.Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
  LOG(FATAL) << "The problem does not have an optimal solution!";
}

Java

final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
  System.err.println("The problem does not have an optimal solution!");
  return;
}

C#

solver.Solve();

Display the solution

The following code displays the solution.

Python

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)

C++

LOG(INFO) << "Solution:";
LOG(INFO) << "Optimal objective value = " << objective->Value();
LOG(INFO) << x->name() << " = " << x->solution_value();
LOG(INFO) << y->name() << " = " << y->solution_value();

Java

// The value of each variable in the solution.
System.out.println("Solution");
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());

// The objective value of the solution.
System.out.println("Optimal objective value = " + solver.objective().value());

C#

Console.WriteLine("Number of variables = " + solver.NumVariables());
Console.WriteLine("Number of constraints = " + solver.NumConstraints());
// The value of each variable in the solution.
Console.WriteLine("Solution:");
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());
// The objective value of the solution.
Console.WriteLine("Optimal objective value = " +
                solver.Objective().Value());

The complete programs

The complete programs are shown below.

Python

from __future__ import print_function
from ortools.linear_solver import pywraplp



def LinearProgrammingExample():
    """Linear programming sample."""
    # Instantiate a Glop solver, naming it LinearExample.
    solver = pywraplp.Solver('LinearProgrammingExample',
                             pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

    # Create the two variables and let them take on any value.
    x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')
    y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')

    # Constraint 0: x + 2y <= 14.
    constraint0 = solver.Constraint(-solver.infinity(), 14)
    constraint0.SetCoefficient(x, 1)
    constraint0.SetCoefficient(y, 2)

    # Constraint 1: 3x - y >= 0.
    constraint1 = solver.Constraint(0, solver.infinity())
    constraint1.SetCoefficient(x, 3)
    constraint1.SetCoefficient(y, -1)

    # Constraint 2: x - y <= 2.
    constraint2 = solver.Constraint(-solver.infinity(), 2)
    constraint2.SetCoefficient(x, 1)
    constraint2.SetCoefficient(y, -1)

    # Objective function: 3x + 4y.
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 4)
    objective.SetMaximization()

    # Solve the system.
    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)


LinearProgrammingExample()

C++

#include <iostream>
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void LinearProgrammingExample() {
  MPSolver solver("LinearExample", MPSolver::GLOP_LINEAR_PROGRAMMING);

  const double infinity = solver.infinity();
  // x and y are non-negative variables.
  MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
  MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");
  LOG(INFO) << "Number of variables = " << solver.NumVariables();

  // x + 2*y <= 14.
  MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 14.0);
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 2);

  // 3*x - y >= 0.
  MPConstraint* const c1 = solver.MakeRowConstraint(0.0, infinity);
  c1->SetCoefficient(x, 3);
  c1->SetCoefficient(y, -1);

  // x - y <= 2.
  MPConstraint* const c2 = solver.MakeRowConstraint(-infinity, 2.0);
  c2->SetCoefficient(x, 1);
  c2->SetCoefficient(y, -1);
  LOG(INFO) << "Number of constraints = " << solver.NumConstraints();

  // Objective function: 3x + 4y.
  MPObjective* const objective = solver.MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 4);
  objective->SetMaximization();

  const MPSolver::ResultStatus result_status = solver.Solve();
  // Check that the problem has an optimal solution.
  if (result_status != MPSolver::OPTIMAL) {
    LOG(FATAL) << "The problem does not have an optimal solution!";
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Optimal objective value = " << objective->Value();
  LOG(INFO) << x->name() << " = " << x->solution_value();
  LOG(INFO) << y->name() << " = " << y->solution_value();
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::LinearProgrammingExample();
  return EXIT_SUCCESS;
}

Java

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Simple linear programming example.*/
public class LinearProgrammingExample {
  static {
    System.loadLibrary("jniortools");
  }

  public static void main(String[] args) throws Exception {
    MPSolver solver = new MPSolver(
        "LinearProgrammingExample", MPSolver.OptimizationProblemType.GLOP_LINEAR_PROGRAMMING);

    double infinity = java.lang.Double.POSITIVE_INFINITY;
    // x and y are continuous non-negative variables.
    MPVariable x = solver.makeNumVar(0.0, infinity, "x");
    MPVariable y = solver.makeNumVar(0.0, infinity, "y");
    System.out.println("Number of variables = " + solver.numVariables());

    // x + 2*y <= 14.
    MPConstraint c0 = solver.makeConstraint(-infinity, 14.0, "c0");
    c0.setCoefficient(x, 1);
    c0.setCoefficient(y, 2);

    // 3*x - y >= 0.
    MPConstraint c1 = solver.makeConstraint(0.0, infinity, "c1");
    c1.setCoefficient(x, 3);
    c1.setCoefficient(y, -1);

    // x - y <= 2.
    MPConstraint c2 = solver.makeConstraint(-infinity, 2.0, "c2");
    c2.setCoefficient(x, 1);
    c2.setCoefficient(y, -1);
    System.out.println("Number of constraints = " + solver.numConstraints());

    // Maximize 3 * x + 4 * y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 4);
    objective.setMaximization();

    final MPSolver.ResultStatus resultStatus = solver.solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.err.println("The problem does not have an optimal solution!");
      return;
    }

    // The value of each variable in the solution.
    System.out.println("Solution");
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    // The objective value of the solution.
    System.out.println("Optimal objective value = " + solver.objective().value());
  }
}

C#

using System;
using Google.OrTools.LinearSolver;

public class LinearProgrammingExample
{
  static void Main()
  {
      MPSolver solver = new MPSolver("LinearProgrammingExample", "GLOP_LINEAR_PROGRAMMING");
      // x and y are continuous non-negative variables.
      Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
      Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");

      // x + 2y <= 14.
      Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 14.0);
      c0.SetCoefficient(x, 1);
      c0.SetCoefficient(y, 2);

      // 3x - y >= 0.
      Constraint c1 = solver.MakeConstraint(0.0, double.PositiveInfinity);
      c1.SetCoefficient(x, 3);
      c1.SetCoefficient(y, -1);

      // x - y <= 2.
      Constraint c2 = solver.MakeConstraint(double.NegativeInfinity, 2.0);
      c2.SetCoefficient(x, 1);
      c2.SetCoefficient(y, -1);

      // Objective function: 3x + 4y.
      Objective objective = solver.Objective();
      objective.SetCoefficient(x, 3);
      objective.SetCoefficient(y, 4);
      objective.SetMaximization();

      solver.Solve();

      Console.WriteLine("Number of variables = " + solver.NumVariables());
      Console.WriteLine("Number of constraints = " + solver.NumConstraints());
      // The value of each variable in the solution.
      Console.WriteLine("Solution:");
      Console.WriteLine("x = " + x.SolutionValue());
      Console.WriteLine("y = " + y.SolutionValue());
      // The objective value of the solution.
      Console.WriteLine("Optimal objective value = " +
                      solver.Objective().Value());
    }
}

Optimal solution

The program returns the optimal solution to the problem, as shown below.

Number of variables = 2
Number of constraints = 3
Solution:
x = 6.0
y = 4.0
Optimal objective value = 34.0

Here is a graph showing the solution:

The dashed green line is defined by setting the objective function equal to its optimal value of 34. Any line whose equation has the form 3x + 4y = c is parallel to the dashed line, and 34 is the largest value of c for which the line intersects the feasible region.

If you think about the geometry in the above graph, in any linear optimization problem at least one vertex of the feasible region must be an optimal solution. As a result, you can find an optimal solution by traversing the vertices of the feasible region until there is no more improvement in the objective function. This is the idea behind simplex algorithm, the most widely-used method for solving linear optimization problems.

To learn more about solving linear optimization problems, see The Glop linear solver.

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 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 __future__ import print_function
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()

Setting time limits

You can set a time limit for Glop (or other linear solvers wrapped via OR-tools) with the LinearSolver::set_time_limit() method (or LinearSolver::SetTimeLimit in Python). The sole argument is an int64 representing the number of milliseconds.