Sudoku, Linear Optimization, and the Ten Cent Diet
Originally posted on the Google Research blog. Cross posted on
the Google Apps Developers
blog
In 1945, future Nobel laureate
George Stigler wrote an essay
in the Journal of Farm Economics titled
The Cost of Subsistence about a
seemingly simple problem: how could a soldier be fed for as little money as possible?
The “Stigler Diet” became a classic problem in the then-new field of
linear optimization, which
is used today in many areas of science and engineering. Any time you have a set of linear
constraints such as “at least 50 square meters of solar panels” or “the amount of paint should
equal the amount of primer” along with a linear goal (e.g., “minimize cost” or “maximize
customers served”), that’s a linear optimization problem.
At Google, our engineers work on plenty of optimization problems. One example is our
YouTube
video stabilization system, which uses linear optimization to eliminate the
shakiness of handheld cameras. A more lighthearted example is in the
Google Docs
Sudoku add-on, which instantaneously generates and solves Sudoku puzzles inside a
Google Sheet, using the
SCIP mixed integer
programming solver to compute the solution.
Today we’re proud to announce two new ways for everyone to solve linear optimization problems.
First, you can now solve linear optimization problems in Google Sheets with the
Linear
Optimization add-on written by Google Software Engineer Mihai Amarandei-Stavila. The
add-on uses Google Apps Script to send optimization problems to Google servers. The solutions
are displayed inside the spreadsheet. For developers who want to create their own applications
on top of Google Apps, we also provide an
API to
let you call our linear solver directly.
Second, we’re open-sourcing the linear solver underlying the add-on: Glop (the Google Linear
Optimization Package), created by
Bruno
de Backer with other members of the Google Optimization team. It’s available as part
of the
or-tools suite and we
provide a
few
examples to get you started. On that page, you’ll find the Glop solution to the
Stigler diet problem. (A Google Sheets file that uses Glop and the Linear Optimization add-on
to solve the Stigler diet problem is available
here.
You’ll need to
install
the add-on first.)
Stigler posed his problem as follows: given nine nutrients (calories, protein, Vitamin C, and
so on) and 77 candidate foods, find the foods that could sustain soldiers at minimum
cost.
The
Simplex algorithm
for linear optimization was two years away from being invented, so Stigler had to do his best,
arriving at a diet that cost $39.93 per year (in 1939 dollars), or just over ten cents per
day. Even that wasn’t the cheapest diet. In 1947, Jack Laderman used Simplex, nine
calculator-wielding clerks, and 120 person-days to arrive at the optimal solution.
Glop’s Simplex implementation solves the problem in 300 milliseconds. Unfortunately, Stigler
didn’t include taste as a constraint, and so the poor hypothetical soldiers will eat nothing
but the following, ever:
- Enriched wheat flour
- Liver
- Cabbage
- Spinach
- Navy beans
Is it possible to create an appealing dish out of these five ingredients? Google Chef Anthony
Marco took it as a challenge, and we’re calling the result
Foie Linéaire à la
Stigler:
This optimal meal consists of seared calf liver dredged in flour, atop a navy bean purée with
marinated cabbage and a spinach pesto.
Chef Marco reported that the most difficult constraint was making the dish tasty without
butter or cream. That said, I had the opportunity to taste our linear optimization solution,
and it was delicious.
Posted by Jon Orwant, Engineering Manager
