Getting Better Answers Faster: Providence Software Startup Dynadec Goes Way Beyond the Traveling Salesman Problem
Say you’re running an oil company and you operate dozens of offshore drilling platforms. You have a fleet of gas-guzzling helicopters to transport the hundreds of technicians who commute every day from the shore to their rig or from one rig to another—but the numbers traveling and their destinations change every day depending on what work needs to be done. How do you get everyone where they need to go while minimizing the number of helicopters deployed and the distance they have to travel?
It’s a classic problem in what computer scientists call “optimization.” To solve it, you could employ a staff of fleet planners to come up with a new helicopter manifest every night—or you could just hand the problem over to a computer. Dynadec, a new Brown University spinoff in Providence, RI, hopes to commercialize software tools that can help companies handle urgent but mind-bending problems like this one.
The company’s core software platform, called Comet, is the brainchild of Pascal Van Hentenryck, a professor in the Optimization Laboratory at Brown’s renowned Department of Computer Science. Now the startup’s chief technology officer, Van Hentenryck is one of the originators of “constraint programming,” a school of software design that emerged in the 1990s. Constraint programming is built around a form of logic that seeks general answers (within a certain range of values or constraints) rather than specific numerical solutions to mathematical problems.
Comet uses constraint programming, along with a form of constraint-based search and a kitchen sink’s worth of other techniques, to come up with cost-saving answers to data-rich problems. In situations like the oil-rig helicopter scheduling problem—or, say, the question of how best to deploy a staff of power-line repair technicians to restore electrical service after a storm—Comet doesn’t try to find the best solution possible, Hentenryck explains. That would take too long. Instead, it aims for a “good enough” solution—or at least one that’s better than what humans could come up with on their own.
In a context such as electrical grid management, “You may have to make a decision in 30 seconds or less,” says Hentenryck. “In that time, you don’t care if the decision is optimal; you care about getting the best solution in the time frame.”
Dynadec, which was in stealth mode until June 9, is already working with customers on pilot projects in areas like vehicle routing, employee scheduling, and inventory management. The company has raised an undisclosed amount of venture funding from Providence-based Liberty Capital Partners and a group of private investors. I interviewed Hentenryck by phone last week. An edited transcript follows.
Xconomy: Tell me briefly about your career path and what led you to launch a company around your optimization techniques.
Pascal Van Hentenryck: I did my PhD in Europe on a new approach to optimization. After my PhD, I worked at European Computer-Industry Research Center on a very different way of approaching optimization problems that was much more combinatorial and less based on traditional math programming techniques. After that I joined Brown and continued to do that kind of work for about 10 years, and some of the products I developed were licensed to ILOG, which was bought by IBM and has been very successful commercially.
Around 2000 we perceived a fundamental change in technology that would affect the optimization world tremendously. I’m talking about the telecom industry, which was really changing the way the world was functioning. You have much more access to data and you can monitor almost all of your activities in real time and know where everything is in your company. So what we decided to do was take a new approach to exploiting that wealth of information.
Instead of doing long-term planning like the airlines typically do—where they schedule where their planes will be a year in advance—we wanted to … Next Page »