On a preprocessing technique for quadratic binary optimization

Endre Boros 

Rutgers - Professor

 
M
onday  November 27, 2006
4:00 PM -  5130 Upson Hall

Abstract:

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.)