John Hooker

How to Relax

Relaxation is a theme that occurs in many problem solving methods. It is often associated with optimization, but relaxation plays an equally important role in finite-domain constraint programming and other discrete methods. This talk surveys a wide variety of relaxation methods, including linear relaxation and cutting planes, Lagrangean relaxation, the domain store and related relaxations, state space relaxation, relaxations in decomposition methods, as well as nonserial dynamic programming, mini buckets, and other relaxations based on simplifying the primal graph. Recognizing the role of relaxation can suggest improvements based on strengthening the relaxation. Consistency

maintenance, for example, in effect strengthens relaxations. Other approaches include the use of such knowledge compilation devices as and/or trees and multivalued decision diagrams, and the solution of a relaxation dual problem.