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 do some optimization that could be used day-to-day, operationally, to address a different class of problems [in areas like] on-demand logistics, on-demand resource allocation. We did a lot of research to try to scale the technology and find the right techniques to address these problems with under the time constraints that people have.
What that research has been about, in the last seven years, has been finding new ways to deal with uncertainty, and changing optimization from long-term planning to making very quick, high-quality decisions. The work was funded by the NSF and the ONR for a long time, but it was not finding its way into a commercial product. I wanted to seize the opportunity, so I took it to the technology licensing office at Brown.
X: Were they helpful?
PVH: Yes, I think they have been very helpful. They took a couple of months and analyzed the technology, and they founded the company with me and invested the initial capital. So they were very helpful. They really said, “Okay, this looks like a great opportunity.”
X: I’m curious how you take a philosophy of optimization and build a viable product and a company around it.
PVH: That’s a good point. Let me answer in two stages. The first thing I would like to say is, optimization has been widely used, but I don’t think it’s reached its potential. You need, first, a good platform, a good tool, and the platform we have is that. But you also need a lot of expertise in how to use the platform for solving these problems, which are some of the most difficult problems in computer science. You typically have to explore a very large search space in an intelligent manner. So you need both the technology and the modeling expertise. We are not trying to sell technology. We’re trying to be a solutions company and develop sophisticated solutions for a variety of areas like resource allocation, so that people can develop applications faster and specialize them for their own companies.
X: Okay, well, there are companies that move things around in the real world like airlines and then there are companies that make software to help them manage that—ITA Software here in Cambridge would be an example. I can see how an optimization platform might be interesting to ITA, but how many big companies that are doing things on the ground even have the expertise to know that they have an “optimization” problem?
PVH: I think we see two different channels for our products. One is the one you just mentioned—companies like ITA. There are a couple of companies we are talking to that would benefit from integrating our solution into their technology. But you’d be surprised how many really major corporations in the U.S. have very limited optimization technology in place. We’re not talking to the IT departments, we’re talking to the operational people. They know what problems they have to get solved, and what they want is a solution to the problem they have right now. The airlines, for example, have been users of optimization for a long time, but it’s a limited form that is not very resistant to disruption; when something happens, they are not very good at reacting. That’s a great opportunity for us. Where things are dynamic and uncertain, that is where we want to focus and fill a need which is not filled.
X: So you’re going after some very big problems—but how do you narrow that down to an addressable market?
PVH: When I created the company, I knew I didn’t have the basic expertise to transform it into a successful business. I don’t have the skills. So that is what we have been trying to do first—build a management team that has the skills to find the market and make the right choices for the technology. And one of the first things we have been doing over the last three months has been to decide where we need to focus, where we know the technology is going to do best. Routing, scheduling, and workforce management are three areas that are very dynamic, typically operating under uncertainty, so we know that the technology matches very well with these areas.
The key right now is to try to focus the company and execute. We tell people that what we want to do is build a pilot system, and show you what we can do. And if you like that, we can engage in a long-term relationship. We can quickly demonstrate the value of the company to these partners, and then they can decide if it is useful to them. So we have pilot programs of four to six weeks where we take a piece of a problem and show them what we can do. It’s very convincing.
X: It sounds like, for now, you’re more of a services or consulting company than a software company.
PVH: At the first stage, we will engage customers in these three particular areas, and in the next stage, over the next two years, we will be focusing on developing the [Comet] application in response to their needs. Currently, we are engaging customers so we can get the input of the problems they have, but it’s mostly for refining and making sure that the applications that we will be showing in some years will be what the market wants. We want to be a software company, and the way to do that is to bootstrap using customer relationships. We are already working with between four and eight really interested prospects, and when I say interested, that means they are willing to pay for the pilot and collect all the data we need and give us that data. Most of them are in those three areas of routing, scheduling, and workforce management, with some in a little more extreme parts of those areas.
X: You must be an engineering-heavy company right now. How are you staffing up the company—are you recruiting graduates from your lab at Brown?
PVH: One of the things I have been trained to do is work over the long term with people. Some of the scientists who are at Dynadec are either former PhD students of mine or colleagues of mine, and that’s the way we try to recruit—we try to recruit people we trust that have a very broad and deep background and are open to new technologies and who we know are team players. This is a critical issue and one of the areas we are putting a lot of effort into, reaching the right people. It’s a very exciting opportunity for young PhDs. They can see some of their research being applied to complex and dynamic problems in the real world, which is getting harder and harder to do in academia.
X: Are you on leave from Brown while you build the company?
PVH: Exactly. I’m on sabbatical right now and I have been talking to Brown about taking leave or having the company buy some or all of my research time from Brown. This is a full-time job. But Brown is very cooperative and they understand what you have to do to build a startup.
X: Why did you decide to base the company in Providence?
PVH: We did it here because it was very convenient. We are close to Brown. As you probably know, the computer science department at Brown is truly outstanding, and we hope that some of the exceptional undergraduates and graduate students will join us. It’s also very convenient for me.
X: Is Rhode Island a good place to build a technology startup?
PVH: Rhode Island is in need of more high-tech companies. There are some advantages from a tax standpoint [to locate in Rhode Island], and it’s great for the state to keep some of the talent here and to build a company in the state where the technology was developed. Many of the investors in the company are from Rhode Island, and they want ot keep it and build it here in the community.
X: Who are the investors?
PVH: Most of the investors are local business people here. I know Jim Gladney of Liberty Capital because our children went to school together. I went to see Jim, and he decided to invest and brought many of the people he knew. And also Brown invested, and we have invested personally, too. And we have some super angel investors in Rhode Island.
X: Okay, now for the question I’ve been putting off—the technology question. What is different about Dynadec’s approach to optimization? What kinds of problems can you uniquely solve?
PVH: Let me answer in two steps, at as high a level as possible. The applications that we will target have two components—an optimization component and a component of decision making under uncertainty.
From an optimization standpoint, what we need are techniques that can find high-quality solutions quickly. You may have to make a decision in 30 seconds or less. In that time, you don’t care if the decision is optimal; you care about getting the best solution in the time frame. The technologies we are working with are not based on proving mathematically that you have found the best solution, they are based on finding a high-quality solution quickly. It uses constraint programming based on local searches, and trying to expose as much of the structure of the problem as possible and use it either to explore the search space quickly or focus on the important parts of the search space quickly. We also have a platform which hybridizes several different techniques, which you typically need in these cases.
The second part is dealing with uncertainty. If you want to solve a problem once and for all—if you model all of the uncertainties and try to find the best policy forever—that is very difficult. The problem is too hard. We want to dynamically make decisions that solve the problem we have today, and use predictive information to guide decisions.
The combination of those two things gives us a high-quality solution. We are trying to solve the problems we have today using predictive models and optimization using the information we’ve gathered.
X: That may be a bit too high-level. Can you give some examples?
PVH: Imagine you have a repair technician who repairs machines for a company, and these machines are taken out of operation with a certain frequency. You want to service them as quickly as possible so they get back into operation and maximize your revenue. We would collect information about which machines are broken and when, and with what frequency do they break, and where are they located. To schedule the technician in an optimal fashion, we’d want to give you some idea of which machines will break today, and you can use those scenarios to decide which technician should go where.
We are working with Los Alamos [National Laboratory] on a different problem related to disaster recovery. Los Alamos has a very powerful tool to predict the effects of earthquakes or hurricanes. They give us scenarios, and we can help them predict which power lines are going to break, and if they fix these lines, what the network will look like. We help you decide how you should position your resources to restore power most quickly after a disaster. These things are changing over time, of course—so five minutes later we may have another set of scenarios. A lot of this is done manually right now, and the companies we are talking to see that there is an opportunity to get much better, higher-quality solutions most of the time. There will always be a human in the loop who will see the different sets of possible solutions, but we are basically automating the decision process.
X: Do you ever run into resistance from people who feel that there’s an important gut-instinct aspect to the kinds of decisions you’re talking about? People who are reluctant to turn over these critical decisions to software?
PVH: We run into that all the time. Some people have prior experience with optimization technology that couldn’t solve their problems, so they’re very skeptical. Other people say “Yes, but how do we know this really is a good solution?” The way we address that issue is by saying, “Okay, let us show you what we can do.” We show them pilot solutions that actually do better than manual. We show them the data. And we try to explain how the decisions are done; we typically build a visualization that removes some of the “magic,” that tells them this is why we are doing this right now.
But none of this will remove the need for a human in the loop, because the model is never a complete characterization of real life. People want to be involved in the loop because they see things the system hasn’t seen and which is not modeled completely or accurately.
X: Would you go even farther and say that there may be certain application areas—say, high-reliability, highly dangerous environments like nuclear plants or aircraft carriers—where it’s inappropriate to rely too much on optimization software?
PVH: That’s a tough one. Let me tell you my take on this. Some of the applications of this technology will be in areas like controlling the electrical grid. And typically, what they do now is, there is always a human making the final decisions, but they use a lot of different software to help the human choose. Software can help the human understand what’s going on and predict what the future can be.
We would enter the picture by telling you what the future can be. When you’re trying to manage risk, you give recommendations to people and eventually they have to make the decisions. I think if you see a lot of different recommendations produced using different tools and they all agree, that would give you some extra confidence. This is a decision support system—that’s how I see it.
When we ask customers about this, what is actually a big surprise to me is that most of them seem to believe that humans, not software, are the main source of errors.
X: What sorts of milestones do you hope to achieve this year?
PVH: I think getting engaged with some major customers, building the right technical team, and laying out the first steps of the applications that we will be developing in the next two years are the critical milestones for us. So building a set of very convincing customer solutions is one of the main priorities.