Linear Programming Methods Are Underused

 
 
By Peter Coffee  |  Posted 2005-05-30 Email Print this article Print
 
 
 
 
 
 
 

Opinion: Linear programming offers a better way of solving problems.

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 peter_coffee@ziffdavis.com.

To read more Peter Coffee, subscribe to eWEEK magazine.
 
 
 
 
Peter Coffee is Director of Platform Research at salesforce.com, where he serves as a liaison with the developer community to define the opportunity and clarify developers' technical requirements on the company's evolving Apex Platform. Peter previously spent 18 years with eWEEK (formerly PC Week), the national news magazine of enterprise technology practice, where he reviewed software development tools and methods and wrote regular columns on emerging technologies and professional community issues.Before he began writing full-time in 1989, Peter spent eleven years in technical and management positions at Exxon and The Aerospace Corporation, including management of the latter company's first desktop computing planning team and applied research in applications of artificial intelligence techniques. He holds an engineering degree from MIT and an MBA from Pepperdine University, he has held teaching appointments in computer science, business analytics and information systems management at Pepperdine, UCLA, and Chapman College.
 
 
 
 
 
 
 

Submit a Comment

Loading Comments...
 
Manage your Newsletters: Login   Register My Newsletters























 
 
 
 
 
 
 
 
 
 
 
Rocket Fuel