On a preprocessing technique for quadratic binary optimization
Monday November 27, 2006
4:00 PM - 5130 Upson Hall
We present a polynomial time preprocessing method for quadratic binary optimization problems, aiming at deriving string bounds, fixing some of the variables, and decomposing the problem into several, possibly smaller instances. The method builds on several known results from the literature, combined with an efficient implementation.
We demonstrate its effectiveness on numerous problem classes, coming from various application areas.
(Joint work with P.L. Hammer and G. Tavares.)