Linear Programming Methods Are Underused

By Peter Coffee  |  Posted 2005-05-30

Lots of folks get all misty-eyed these days about the power of computers to help us express ourselves. The engineer in me recoils, though, from the use of so much power to wait for a user to think of something to say—as the 1GHz CPU of my laptop is waiting for me, right now, to get on with this column.

My own misty-eyed devotion is to the power that computers give us to make better decisions and make better use of resources. I therefore note this months passing of mathematician George Dantzig, principal developer of the methods of linear programming that are the foundation of modern planning.

To understand the essence of linear programming, imagine a factory thats equipped to make two types of chairs. One type is made of mostly cloth with leather trim; the other is made of mostly leather with cloth trim. Each chair needs labor from leather workers and cloth workers in proportion to its use of those materials. Each chairs cost is the sum of these four component costs, plus other common costs, all with what well assume to be linear relationships to the number of chairs produced—that is, making twice as many chairs consumes twice as much material and labor.

The profit to the factory can also be modeled as linear: The sum of the profits from each type of product, proportional to the quantities produced, minus the fixed costs of being in business.

There are limits, though, on the number of hours of labor available from each craft, based on the number of people who can work at any one time in each area of the factory. We could, if we wished, express this as a certain number of regular hours available at one cost and another number of overtime hours available at a higher cost. The "linear program" for this problem is then the statement of an "objective function" (overall profit) to be, in this case, maximized subject to these constraints.

This problem and other similar maximization and minimization problems can be diagrammed and solved with a pencil and a straightedge. We can also graphically determine which resources would be most valuable to increase, or which constraints it would be most worthwhile to loosen.

Its easy to imagine more realistic problems, though, involving dozens or even thousands of such variables and constraints. Dantzigs Simplex algorithm, which he devised in 1947, solves such problems reliably and efficiently; the algorithm therefore lets a planner examine many production-scheduling scenarios.

Dantzigs work was pivotal to the early adoption of computers by business and military planners. "Until computers started to be used for e-mail and the World Wide Web in the 80s and 90s, the single most important use of computers—the biggest user of computer time in the entire world—was running the Simplex algorithm to solve linear programming problems. No large organization can exist or stay in business without the Simplex algorithm," declared Stanford University professor Keith Devlin during National Public Radios May 21 report on Dantzigs death.

Its perhaps the most dubious achievement, then, of the desktop computing revolution that instead of running Simplex scenarios on mainframes to yield provably optimal solutions, we now throw at least as many CPU cycles at trial-and-error spreadsheet manipulations on PCs that may or may not be finding the best possible choices. In the process, people who could be using their expertise to conceive new production options, or investigating the accuracy of their assumptions, are instead using too much of their time to do what Dantzigs methods have been doing better for more than half a century.

You can do better. You can use the Solver add-in that comes with Excel or add a third-party spreadsheet enhancement such as Frontline Systems Premium Solver Platform; you can use the linear programming functions in an industrial-strength mathematical tool kit such as Wolfram Researchs Mathematica or The MathWorks Matlab and Optimization Toolbox. One way or another, you can rediscover whats been known for so long about the value of merely thinking about a problem clearly enough to program it—let alone solve it.

Technology Editor Peter Coffee can be reached at

To read more Peter Coffee, subscribe to eWEEK magazine.

Rocket Fuel