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.
Import the linear solver wrapper
Import the OR-Tools linear solver wrapper, an interface for MIP solvers and the Glop linear solver, as shown below.
Python
from ortools.linear_solver import pywraplp
C++
#include <iostream> #include "ortools/linear_solver/linear_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable;
C#
using System; using Google.OrTools.LinearSolver;
Declare the LP solver
MPsolver
is a wrapper for several different solvers, including Glop.
The code below declares the GLOP solver.
Python
solver = pywraplp.Solver.CreateSolver('GLOP')
C++
MPSolver solver("linear_programming_examples", MPSolver::GLOP_LINEAR_PROGRAMMING);
Java
MPSolver solver = MPSolver.createSolver("GLOP");
C#
Solver solver = Solver.CreateSolver("GLOP");
Note: If you install OR-Tools from source, there are other third-party solvers available. See the "Install from Source" section of the installation guide for your platform.
Create the variables
First, create variables x and y whose values are in the range from 0 to infinity.
Python
x = solver.NumVar(0, solver.infinity(), 'x') y = solver.NumVar(0, solver.infinity(), 'y') print('Number of variables =', solver.NumVariables())
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"); Console.WriteLine("Number of variables = " + solver.NumVariables());
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 constraint.
Python
# Constraint 0: x + 2y <= 14. solver.Add(x + 2 * y <= 14.0) # Constraint 1: 3x - y >= 0. solver.Add(3 * x - y >= 0.0) # Constraint 2: x - y <= 2. solver.Add(x - y <= 2.0) print('Number of constraints =', solver.NumConstraints())
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. solver.Add(x + 2 * y <= 14.0); // 3x - y >= 0. solver.Add(3 * x - y >= 0.0); // x - y <= 2. solver.Add(x - y <= 2.0); Console.WriteLine("Number of constraints = " + solver.NumConstraints());
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. solver.Maximize(3 * x + 4 * y)
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. solver.Maximize(3 * x + 4 * y);
Invoke the solver
The following code invokes the solver.
Python
status = 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();
C#
Solver.ResultStatus resultStatus = solver.Solve();
Display the solution
The following code displays the solution.
Python
if status == pywraplp.Solver.OPTIMAL: print('Solution:') print('Objective value =', solver.Objective().Value()) print('x =', x.solution_value()) print('y =', y.solution_value()) else: print('The problem does not have an optimal 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
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) { System.out.println("Solution:"); System.out.println("Objective value = " + objective.value()); System.out.println("x = " + x.solutionValue()); System.out.println("y = " + y.solutionValue()); } else { System.err.println("The problem does not have an optimal solution!"); }
C#
// Check that the problem has an optimal solution. if (resultStatus != Solver.ResultStatus.OPTIMAL) { Console.WriteLine("The problem does not have an optimal solution!"); return; } Console.WriteLine("Solution:"); Console.WriteLine("Objective value = " + solver.Objective().Value()); Console.WriteLine("x = " + x.SolutionValue()); Console.WriteLine("y = " + y.SolutionValue());
The complete programs
The complete programs are shown below.
Python
from ortools.linear_solver import pywraplp def LinearProgrammingExample(): """Linear programming sample.""" # Instantiate a Glop solver, naming it LinearExample. solver = pywraplp.Solver.CreateSolver('GLOP') # Create the two variables and let them take on any non-negative value. x = solver.NumVar(0, solver.infinity(), 'x') y = solver.NumVar(0, solver.infinity(), 'y') print('Number of variables =', solver.NumVariables()) # Constraint 0: x + 2y <= 14. solver.Add(x + 2 * y <= 14.0) # Constraint 1: 3x - y >= 0. solver.Add(3 * x - y >= 0.0) # Constraint 2: x - y <= 2. solver.Add(x - y <= 2.0) print('Number of constraints =', solver.NumConstraints()) # Objective function: 3x + 4y. solver.Maximize(3 * x + 4 * y) # Solve the system. status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print('Solution:') print('Objective value =', solver.Objective().Value()) print('x =', x.solution_value()) print('y =', y.solution_value()) else: print('The problem does not have an optimal solution.') print('\nAdvanced usage:') print('Problem solved in %f milliseconds' % solver.wall_time()) print('Problem solved in %d iterations' % solver.iterations()) LinearProgrammingExample()
C++
#include <iostream> #include "ortools/linear_solver/linear_solver.h" namespace operations_research { void LinearProgrammingExample() { MPSolver solver("linear_programming_examples", 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
package com.google.ortools.linearsolver.samples; import com.google.ortools.Loader; 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 final class LinearProgrammingExample { public static void main(String[] args) { Loader.loadNativeLibraries(); MPSolver solver = MPSolver.createSolver("GLOP"); 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(); if (resultStatus == MPSolver.ResultStatus.OPTIMAL) { System.out.println("Solution:"); System.out.println("Objective value = " + objective.value()); System.out.println("x = " + x.solutionValue()); System.out.println("y = " + y.solutionValue()); } else { System.err.println("The problem does not have an optimal solution!"); } System.out.println("\nAdvanced usage:"); System.out.println("Problem solved in " + solver.wallTime() + " milliseconds"); System.out.println("Problem solved in " + solver.iterations() + " iterations"); } private LinearProgrammingExample() {} }
C#
using System; using Google.OrTools.LinearSolver; public class LinearProgrammingExample { static void Main() { Solver solver = Solver.CreateSolver("GLOP"); // 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"); Console.WriteLine("Number of variables = " + solver.NumVariables()); // x + 2y <= 14. solver.Add(x + 2 * y <= 14.0); // 3x - y >= 0. solver.Add(3 * x - y >= 0.0); // x - y <= 2. solver.Add(x - y <= 2.0); Console.WriteLine("Number of constraints = " + solver.NumConstraints()); // Objective function: 3x + 4y. solver.Maximize(3 * x + 4 * y); Solver.ResultStatus resultStatus = solver.Solve(); // Check that the problem has an optimal solution. if (resultStatus != Solver.ResultStatus.OPTIMAL) { Console.WriteLine("The problem does not have an optimal solution!"); return; } Console.WriteLine("Solution:"); Console.WriteLine("Objective value = " + solver.Objective().Value()); Console.WriteLine("x = " + x.SolutionValue()); Console.WriteLine("y = " + y.SolutionValue()); Console.WriteLine("\nAdvanced usage:"); Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds"); Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations"); } }
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 (orLinearSolver::SetTimeLimit
in Python). The
sole argument is an int64 representing the number of milliseconds.