Speaker: John Hooker, Professor of Operations Research
Title: Duality in Optimization and Constraint Satisfaction
Date: Friday, October 13, 2006
Time: 1:30 to 3:00 pm
Place: Room 384 Posner Hall
In this talk I attempt to unify the various duals that have been developed in optimization and constraint satisfaction. I show that they can be classified as inference duals, relaxation duals, or both. They include linear programming, surrogate, Lagrangean, superadditive, and constraint duals, as well as duals defined by resolution and filtering algorithms. Inference duals give rise to nogood-based search methods (such as Benders decomposition) and sensitivity analysis, while relaxation duals provide bounds. This analysis shows that duals may be more closely related than they appear, as are surrogate and Lagrangean duals. It also reveals common structure between solution methods, such as Benders decomposition and Davis-Putnam-Loveland methods with clause learning. It provides a framework for devising new duals and solution methods.
