Constraints

1 August 2008

ECAI 2008

Filed under: Commentary — András Salamon @ 21:33
Tags: ,

I attended ECAI 2008 in Patras, Greece last week. The conference was rather large (perhaps even unwieldy), with over 30 workshops, seven concurrent tracks in the main conference, and more than 600 people attending. Due to the excellent turnout from the constraints community, most of my time was spent at talks about constraints and search, with a few talks from other fields to provide some perspective. It was quite easy to speak to people, perhaps because our submission (Cooper, Jeavons, Salamon: Hybrid tractable CSPs which generalize tree structure) unexpectedly received the best paper award. There was a large turnout at my talk, which was a bit daunting!

Before the main conference, several interesting papers were presented at the Workshop on Modeling and Solving Problems with Constraints (proceedings are available online).

Battiti, Campigotto: Penalties may have collateral effects. A MAX-SAT analysis

Paulo Campigotto argued that fiddling with clause weights to smooth out a MAX-SAT fitness surface doesn’t work except to nudge solutions along from a local minimum; there are simply too many side effects to use this technique globally.

Freuder, Wallace, Nordlander: Debugging Constraint Models with Metamodels and Metaknowledge

Richard Wallace discussed a system named Ananke, after the Goddess of Bonds (and therefore an appropriate deity for constraint satisfaction).  Given specific solutions that the user of the system expects, Ananke suggests ways to alter an overconstrained specification of a constraint problem so that those solutions become possible.  The idea is that this would help find constraints which unnecessarily disallow desired solutions.

Gent, Miguel, Rendl: Common Subexpression Elimination in Automated Constraint Modelling

Andrea Rendl talked about the Tailor system to translate high-level Essence’ specifications of constraint problems into models that can be run using existing constraint programming systems such as Minion.  In the translation, it is possible to detect common subexpressions, as a byproduct of parsing and with minimal overhead, resulting in more compact constraint programs and sometimes also much faster search.  Even where eliminating subexpressions doesn’t yield any improvement, there is essentially no cost to including it as part of the translation phase.

Makeeva, Szymanek: Revisiting the Generalized Among Constraint

The main point in this tightly argued talk by Polina Makeeva was that it can be faster to use AMONG (if carefully implemented) than to decompose into individual global constraints, since this allows sharing and reuse of information.  This kind of result would seem to argue against the traditional, loosely coupled view of constraints interacting purely through a set of domains.

Maher, Narodytska, Quimper, Walsh: Flow-Based Propagators for the SEQUENCE and Related Global Constraints

Nina Narodytska argued that for some global constraints one can use an Integer Linear Programming model if a graph model is not known, while some kinds of ILP models can be transformed into flow problems.  If both techniques are applied, one can sometimes find fast flow-based propagators.  An example is the SEQUENCE constraint, and an algorithm was presented to enforce domain consistency down a branch of the search tree in O(n^2) time, an O(\log n) factor improvement on the best previous algorithm.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: