More than 20 years ago, Bob Bixby decided the world needed a better linear programming code. This wasn’t a particularly obvious decision. First, there were already existing linear programming codes. Second, linear programming implementation was not exactly a hot research topic. Third, Bixby was not particularly known in this area. A typical paper for Bixby would be “On Reid’s Characterization of the Ternary Matroids” (Abstract: In this paper the author proves a stronger version of a result of Ralph Reid characterizing the ternary matroids (i.e., the matroids representable over the field of 3 elements, GF(3))…). Hardly the sign of someone about to write a great linear programming solution code!
Fortunately, Bixby is really, really smart, so in short order, Bixby got a very good code together, and began to show the research issues involved in implementing linear programming. And the code got better and better, due in part to an eagerness to collect hard linear programming problems and to continuously improve the code based on them. You can read more about this history in the article Bob wrote for the 50th anniversary edition of Operations Research in 2002 in an article entitled “Solving Real-World Linear Programs: A Decade and More of Progress“.
CPLEX is now owned by ILOG, and ILOG is celebrating the 20th anniversary of CPLEX. They just put out a press release on the birthday. Yours truly has a part in the release, providing a quote, and, less obviously, an application:
United States Postal Service (USPS) has realized more than $10 million in savings to date by leveraging ILOG CPLEX for a strategic transportation management initiative. Developed by USPS and IBM, the Highway Corridor Analytic Program (HCAP) uses advanced technology to analyze USPS highway transportation scenarios and identify cost saving opportunities. HCAP model uses ILOG CPLEX to identify the best allocation of mail among transportation resources.
That is work I did with USPS, IBM Global Business Services, and Luis Zuluaga, now at the University of New Brunswick.
Happy Bday CPLEX!!! Though my mathematical aptitude led me to my first computer science classes in the gifted child program of the LAUSD, optimization in theory or practice is far beyond my meager abilities. CPLEX is now the world’s most widely used optimization software. Dr. Bixby should be proud of his baby.
I had no idea Ralph Reid was so “multi-talented.”
I assume all of Ralph’s matroids were oriented to the right.
Happy Birthday CPLEX!
I hope we will also be singing Happy Birthday to GuRoBi in 20 years, when I am routinely solving trillion variable LPs on my Exaflop cellphone.