______________________________________________________________________

Date:  Friday 23 August 2002
Time:  13:15
Venue: Room 111, House 1, MIC, Polacksbacken, Uppsala University
______________________________________________________________________

	   A Constraint-Based Architecture for Local Search

			Pascal Van Hentenryck

			   Brown University
		    Department of Computer Science
		    Providence, Rhode Island, USA
			   pvh@cs.brown.edu
		 http://www.cs.brown.edu/people/pvh/

Combinatorial optimization  problems are ubiquitous  in many practical
applications.    Yet  most   of  them   are  challenging,   both  from
computational complexity and programming standpoints.  Local search is
one of  the main  approaches to address  these problems.   However, it
often   requires  sophisticated   incremental   algorithms  and   data
structures,  and considerable experimentation.   This talk  proposes a
constraint-based,   object-oriented   architecture   to   reduce   the
development  time  of  local  search  algorithms  significantly.   The
architecture  consists  of  declarative  and search  components.   The
declarative  component  includes  invariants, which  maintain  complex
expressions incrementally, and  differentiable objects, which maintain
properties that can be queried  to evaluate the effect of local moves.
Differentiable  objects  are  high-level  modeling concepts,  such  as
constraints  and functions,  that capture  combinatorial substructures
arising in  many applications.  The search  component supports various
abstractions to specify heuristics and meta-heuristics.  We illustrate
the  architecture with  the language  Comet and  several applications,
such  as  car  sequencing  and  the progressive  party  problem.   The
applications indicate that the architecture allows for very high-level
modeling  of  local  search  algorithms,  while  preserving  excellent
performance.
______________________________________________________________________

Directions to MIC: http://www.its.uu.se/organisation/kartor/vag-mic.html
Directions inside MIC: http://www.its.uu.se/organisation/kartor/mic.html