Short research Statement
Carla P. Gomes
In my research I establish connections between constraint programming methods and methods from operations research, with applications to large-scale optimization problems. My work spans the full range of theory to applications. In earlier work, I worked on the automatic generation of provably correct software --- essential in safety critical applications --- for scheduling nuclear power-plant maintenance. In more recent work, I study the application of randomization techniques for complete search methods, leading to the discovery of so-called heavy-tailed distributions in combinatorial search. Such distributions lead to unexpectedly large variations in runtimes. Randomized restart strategies can be used to cut off unsuccessful runs. This work has had a concrete impact on current practice. For example, restart techniques are now an integral part of practical constraint solvers, as used in state-of-the-art model checking tools for verification. They significantly increase the robustness of complete combinatorial methods. Combined with constraint learning techniques, randomization enables the scale-up of combinatorial complete solvers to practical problem instances with one million variables and five million constraint, compared to around two hundred variables with five hundred constraints in the early nineties. In other work, jointly with David Shmoys of Cornell University, I have shown how to boost the performance of complete backtrack search methods by using the information provided by randomized approximation methods, based on linear programming techniques and strong relaxation formulations with provable performance guarantees. Most recently, I am interested in studying the computational issues underlying combinatorial auctions, as used in E-commerce applications. Last year, I was Conference Chair of the main conference on Constraint Programming (CP-2002).
Detailed Research statement Postscript PDF