[Intelligence Seminar] OR Seminar on Friday, Dec 10th

[Dana Houston]

While this seminar is not part of the Intelligence Seminar series, it is
on a related subject and may be of interest to the Intelligence Seminar
audience.

Name:  Gilles Pesant, Ecoly Polytechnique Montreal

Date:  Friday, December 10, 2010

Time:  1:30 to 3:00 pm
Location:  Room 151 Posner Hall
Title:  Counting-Based Branching Heuristics in Constraint Programming

Abstract:  Constraint Programming (CP) is a powerful technique to solve
combinatorial problems. It applies sophisticated inference to reduce
the search space and a combination of variable- and value-selection
heuristics to guide the exploration of that search space. Like Integer
Programming, one states a model of the problem at hand in mathematical
language and also builds a search tree through problem decomposition.
But there are important differences: CP works directly on discrete
variables instead of relying mostly on a continuous relaxation of the
model; the modeling language offers many high-level primitives
representing common combinatorial substructures of a problem; each of
these primitives (constraints) may have its own specific algorithm to
help solve the problem; one does not branch on fractional variables but
instead on indeterminate variables, which currently can take several
possible values (variables are not necessarily fixed to a particular
value at a node of the search tree); even though CP can solve
optimization problems, it is primarily designed to handle feasibility
problems.

Until recently, the only visible effect of the inference applied from
the constraints had been on the domains of the variables, projecting a
constraint's set of solutions on each of the variables. Accordingly,
most branching heuristics in CP rely on information at the level of
individual variables, essentially looking at the cardinality of their
domain or at the number of constraints on them. Constraints play a
central role in CP because they encapsulate powerful specialized
inference algorithms but firstly because they bring out the underlying
structure of combinatorial problems. That exposed structure can also be
exploited during search. Information about the number of solutions to a
constraint can help a search heuristic focus on critical parts of a
problem or on promising solution fragments.

This talk describes recent efforts in using solution-counting
information about constraints to guide heuristic branching within a
Constraint Programming framework, in order to find solutions to
combinatorial problems in a more transparent yet efficient way. We
present some of the counting algorithms developed for several of the
most common combinatorial substructures and propose simple counting-
based branching heuristics. Empirical evidence is given on several
problem domains in support of such branching heuristics compared to
other state-of-the-art heuristics in CP.

The seminar has been posted at the following address:
http://server1.tepper.cmu.edu/Seminars/seminar.asp?sort=1&short=Y

Please take the time to schedule a meeting with the speaker on an
individual basis.  When you are at the seminar site, proceed to this
seminar announcement.  To add yourself for a meeting, click on
View/Edit Schedule link and then click on the Edit Schedule link.
Enter the name portion of your e-mail address (the @andrew.cmu.edu part
is not needed) and click Update at bottom of page.