David Levine has always tread a fine line between academia and industry. He entered the ICS Ph.D. program at UCI in 1987 after working at The Aerospace Corporation on projects for the Department of Energy. Those included fuel-saving programs for cars and trucks and early electric and hybrid vehicles, ranging from on-board control systems to very detailed drivetrain simulations. As those programs were winding down, he looked for opportunities in software research. UCI was a natural fit, and Professor Richard Taylor’s group a natural home. Levine worked on analysis and design of software for performance as part of the Arcadia research project.
After graduating with his Ph.D. and a stint with a spinoff out of the CS department at Washington University in St. Louis (WUSTL), Levine was hired by alumnus Douglas Schmidt to work in the Distributed Object Computing lab at WUSTL. A startup opportunity with other WUSTL computer science faculty came along, and Levine eventually crossed the line back into industry. April 2000 was not the ideal time to form a startup, but CombineNet has succeeded. The original goal was to find useful applications for combinatorial auctions, where a bid covers more than one item with a single price. This helps avoid the exposure problem of bidders ending up with items that are of no use because they don’t obtain complementary items.
CombineNet applies the concept to procurement; it produces an on-line procurement platform that supports very large bids and very complex analysis. “Items” in its events include a wide variety of products, ranging from raw materials for manufacturing processes to equipment to packaging to finished products. And they include services, such as transportation, legal and other professional, and facilities maintenance. In this age of outsourcing and virtual companies with a focus on supply chain, a transparent, robust and efficient procurement process is critical to success. Customers typically see a 5-40% reduction in procurement cost, 15-50% reduction in time spent, and a 45X ROI.
Both bid takers (buyers) and bidders (suppliers) benefit from being able to specify their needs and capabilities, with as little or as much precision as they like. So in contrast to usual auctions where bidders can only compete on price, there is much more opportunity to craft and update offers based on any of their parameters. This results in a much more collaborative environment than with usual auctions. And it relies on improving efficiency in production and delivery systems. A good example is that about 30% of truck traffic is empty backhauls; by bidding combinatorially on complementary routes, trucking companies can reduce that directly.
But deciding the winning bids requires complex analysis. As part of the Arcadia project at UCI, Levine worked on analysis and design of concurrent programs, along with Prof. Taylor, alumnus Michal Young, and staff programmers Kari Nies and Debra Brodbeck. They utilized static analysis, which required constructing a very large, typically, graph of all possible states of a concurrent program, called a state space. Levine built on that approach to analyze all possible combinations of offers in the bidding events at CombineNet. Searching through those offers builds a graph, called a search space, where each node is an assignment of values to decision variables. That representation lends itself to solution methods of Computer Science and Operations Research, along with some proprietary techniques. Those solution approaches have advanced to the point that customers can solve useful problems; assignments of values to on the order of 10 million variables is now routine. Levine notes that “we usually don’t have to explain to customers that we can or can’t solve their NP-complete problems. In fact, we almost always spend more time pulling data out of a database than actually solving the problem itself.”
Levine’s experiences with Arcadia and at Washington University left him at ease with distributed software. Not surprisingly, CombineNet’s initial deployment in 2000 was over the Internet. The company has provided Software as a Service since long before that term were invented. Levine notes that “When we started in 2000, I could act as sys admin. I wouldn’t do that now, just keeping up with platforms, standards, and security in the web world is more than a full time job now.”
One of Levine’s favorite projects at CombineNet has been for the Department of Agriculture, helping with the periodic procurement of grains and transportation from farms in the U.S. to worldwide destinations for the last four years. “It’s very gratifying to be a part of the delivery of food to those in need. And to do so as efficiently as possible, in order to help as many as possible.” said Levine.
Levine retains another UCI tie as one of the maintainers of the nmh mail user agent. nmh is a derivative of MH, which was designed and implemented starting in 1977 at RAND Corp., then further developed and maintained at UCI from 1982 to 1994. “I enjoy looking for ways to inject newer approaches and techniques into the older design and implementation” said Levine. His motivations for contributing to open-source projects are “the opportunities to engage in very focused technical debates, and to reach the compromises that are necessary at the end of the day. And while funding isn’t a constraint, the time invested by contributors certainly is.”
In addition, Levine likes to “keep his hands dirty” by actually working on software. “Software engineering, like other engineering disciplines, is about producing artifacts. It’s different from other engineering disciplines in that its artifacts aren’t physical, but more importantly, its tools and processes are also software, its own artifacts. One important lesson I learned from the Arcadia project is that robust and powerful techniques, tools, and processes are keys to successful development. The best way to produce and maintain quality software is to remain deeply involved with the entire development cycle.”
Levine attended Professor Taylor’s retirement celebration in June, along with 21 of his 28 other Ph.D. graduates as well as ISR staff – some of whom have been with the ICS Software group since the late 1980’s, before the establishment of ISR and even its predecessor the Irvine Research Unit in Software (IRUS). It provided a great opportunity to renew old friendships, make new ones, and rekindle professional relationships. Levine commented, “It was truly amazing to see such a vibrant, successful group of people all together in one small room.” We concur!
Levine may be contacted at firstname.lastname@example.org.