The 2014 Informs Computing Society prize is awarded to Jim Ostrowski, Jeff Linderoth, Fabrizio Rossi, and Stefano Smriglio for their work on dealing with symmetry in combinatorial optimization problems. Symmetry constitutes one of the “last frontiers” of integer programming, as it is easily observed that even moderate size problem instances with a large amount of symmetry routinely defeat all general purpose solvers. Symmetry, as is well-known, produces large branch-and-bound trees. Furthermore, formulations of combinatorial problems with a high degree of symmetry also tend to yield very weak relaxations whose bounds do not improve much (or at all) even after a large amount of branching.The awarded work encompasses a family of elegant techniques which branch on combinatorial objects not directly obvious from a problem formulation. This careful enumeration not only avoids the direct cost of enumeration, but by capturing structure of the problem quickly leads to improved bounds. On the computational side, the work also incorporates innovative high-throughput computing techniques. These efforts proved successful at obtaining optimal solutions to previously unsolved instances as well as improved bounds, thus covering a nice span from theory to implementation. Finally, the work may prove influential in the development of commercial integer programming software. Please see the following papers for details.
- Orbital Branching, Mathematical Programming, 126:147-178, 2011.
- Constraint Orbital Branching, IPCO 2008: Lecture Notes in Computer Science, Vol. 5035, Springer, 225-239, 2008.
- Solving Large Steiner Triple Covering Problems, Operations Research Letters, 39:127-131, 2011.