Francois Margot, Associate Professor of Operations Research
Carnegie Mellon University
Date: Friday, September 28, 2007
Time: 1:30 to 3:00 pm
Location: Room 388 Posner Hall
Title: Testing Cut Generators for ILP
Abstract:
This talk describes recent work on the testing of cut generators for integer linear programming. The goal of this work is to build experiments that can be used for comparing slight variants of a cut generator. Cut generators should be compared along several dimensions, for example the precision (what is the likelihood of a feasible solution to be cut?), the strength (are the cuts obtained stronger or weaker?), the speed of the generator, and the speed of the reoptimization after cuts are added. While generation and reoptimization speeds are relatively easy to test, both precision and strength are more difficult to evaluate. Results for testing several variants of Gomory cut generators and several variants of Reduce-and-Split cut generators are presented.
The approach followed is in the spirit of the empirical analysis of algorithms advocated by Hooker and McGeoch, among others. The object of empirical analysis of algorithms is to use experiments to suggest hypotheses about the behavior of algorithms. Hypotheses are then tested using controlled experiments, well-grounded in statistical analysis.
