Pedro Meseguer
The Sixteenth International Joint Conference on Artificial Intelligence was
held from July 31 to August 6 in Stockholm, Sweden. The city was very lively,
and attenders could enjoy some activities of the Water Festival. The conference
site, very central and close to the main pedestrian street, made it easy to
switch from work to pleasure. Regarding constraint programming, IJCAI offered
two forums. First, on Monday 2, the workshop on Non Binary Constraints, organized
by Jean-Charles Regin and Wim Nuijten. Second, the Technical Program included
4 sessions on Constraint Satisfaction, on Tuesday 3 and Wednesday 4. Below
I briefly summarize the contents of each one.
The Non Binary Constraints workshop gathered about 20 people with 7 presentations.
Jean-Charles Regin made an introduction summarizing the different papers.
He also warned about the possibility that constraint programming could move
towards operations research if several practical problems are not correctly
addressed by the constraint community. After the presentations, the possibility
of a future workshop was discussed, exploring different topics that could
be added to encourage participation. The seven papers presented at the workshop
are the following:
-- A Method for Efficient Representation and Scanning of Boolean Constraints,
by Skovgaard
-- Non-binary Constraints for Frequency Assignment, by Bater, Jeavons and
Cohen
-- A Framework for Constraint Programming Based Column Generation, by Junker,
Karish, Kohl, Vaaben, Fahle and Sellman
-- On Forward Checking for Non-binary Constraint Satisfaction, by Bessiere,
Meseguer, Freuder and Larrosa
-- Rewritting Numeric Constraint Satisfaction Problems for Consistency Algorithms,
by Lottaz
-- A Global Constraint Combining a Sum Constraint and Binary Inequalities,
by Regin and Rueher
--
Modelling the Golomb Ruler Problem, by Smith, Stergiou and Walsh
The paper by Skovgaard introduces a new method for efficient manipulation
of boolean constraints involving several variables. When checking a constraint,
this method derives new inferences. It tries to limit its memory usage. In
practice, this method can handle constraints up to 32 variables. Empirical
results on several classical problems are given.
The paper by Bater, Jeavons and Cohen considers the frequency assignment problem,
for which it provides two different modellings into binary and non-binary
constraints. Solved by methods that include local search, empirical results
show that solutions from the non-binary
formulation are of better quality than the corresponding ones from the binary
model. The paper by Junker, Karish, Kohl, Vaaben, Fahle and Sellman describes
a hybrid approach combining operations research and constraint programming
methods. It uses column generation (an OR method to avoid considering explicitly
all variables), allowing subproblems to
have non-linear constraints which are solved by constraint techniques. This
approach has been successfully applied to airline crew assignment. The paper
by Bessiere, Meseguer, Freuder and Larrosa generalizes the popular forward
checking algorithm, originally defined for binary
problems, into the non-binary case. Several generalizations are possible,
all fitting the binary definition. Their pruning capacity, complexities and
relation with the hidden representation are studied. The paper by Lottaz analyzes
the reformulation of numeric non-binary CSP into ternary constraints, which
may enhance the efficiency of relational consistency algorithms. Reformulation
into ternary form is possible if the introduction of auxiliary variables is
acceptable. A heuristic to introduce auxiliary variables is given. The paper
by Regin and Rueher considers the minimization of a sum of integer variables
under a set of inequalities. They generate a global constraint that includes
the function
to minimize. An algorithm to achieve interval consistency (weaker than arc-consistency)
in this set of constraints is provided. The paper by Smith, Stergiou and Walsh
discusses several ways to model the Golumb Ruler Problem as a CSP with quaternary
constraints, ternary and binary constraints, ternary and all-different constraints,
and binary constraints. It provides some theoretical results about arc-consistency
on these formulations. It contains a very interesting discussion on empirical
results, including implied constraints,
auxiliary variables and heuristics.
The IJCAI'99 Technical Program contained 12 papers on constraints,
distributed in the following sessions:
Constraint Satisfaction 1
-- A Comparison of Structural CSP Decomposition Methods, by Gottlob, Leone
and Scarcello
-- Solving Strategies for Highly Symmetrical CSPs, by Meseguer and Torras
-- Extending Consistent Domains of Numeric CSP, by Collavizza, Delobel and
Rueher
Constraint Satisfaction 2
-- The Difference All-Diference Makes, by Stergiou and Walsh
-- The Symmetric Alldiff Constraint, by Regin
-- Branch and Bound with Mini-Bucket Heuristics, by Kask and Dechter
Constraint Satisfaction 3
-- Improving Search Using Indexing: A Study with Temporal CSPs, by Mamoulis
and Papadias
-- A New Tractable Subclass of the Rectangle Algebra, by Balbiani, Condotta
and Fariñas del Cerro
-- Maximal Tractable Fragments of the Region Connection Calculus: A Complete
Analysis, by Renz
Constraint Satisfaction 4
-- Path Consistency on Triangulated Constraint Graphs, by Bliek and Sam-Haroud
-- A New Method to Index and Query Sets, by Hoffmann and Koehler
-- Constraint Propagation and Value Acquisition: Why Wer Should Do it Interactively,
by Cucchiara, Mello, Milano and Piccardi
In the first session, the paper by Gottlob, Leone and Scarcello considers
CSP decomposition methods into tractable classes because of their structure.
They present a new method called hypertree decomposition and compare it with
existing approaches, showing that the new method generalizes existing ones.
The paper by Meseguer and Torras presents two strategies to exploit symmetries
for CSP solving: a variable selection heuristic and a domain pruning procedure.
The benefits of these strategies are shown for the generation of BIBDs (Balanced
Incomplete Block Designs). The paper by Collavizza, Delobel and Rueher introduces
a new framework for extending consistent domains of numeric CSPs. They provide
an incremental algorithm to compute the maximal extension of the domain of
a variable.
In the second session, the paper by Stergiou and Walsh analyzes the all-different
constraint, showing that a search algorithm maintaining arc consistency on
the non binary representation dominates the equivalent algorithm on the binary
representation. Experimental results on quasigroups are provided. The paper
by Regin studies the symmetric all-different constraint, a special case of
the all-different constraint with applications to sport tournaments. Two arc-consistency
algorithms for this constraint are presented, including complexity analysis.
The paper by Kask and Dechter considers finding the most probable explanation
in bayesian networks. This problem is solved using branch and bound scheme,
using heuristics
generated by the mini-bucket approximation. Empirical results on random networks,
probabilistic decoding and medical diagnosis are given.
In the third session, the paper by Mamoulis and Papadias considers CSP with
a small number of variables and a huge number of values, problems which may
arise solving queries in temporal databases. They present an indexing scheme
for values which increases greatly the efficiency of standard forward checking.
The paper by Balbiani, Condotta and Farinas del Cerro studies rectangle algebra
in a 2-dimensional euclidean space. They identify a new tractable subset of
relations in this algebra, the strongly-preconvex relations. Global consistency
for these
relations can be achieved by path-consistency methods. The paper by Renz analyzes
consistency of disjunctions of jointly exhaustive and disjoint relations,
providing a method for proving tractability. Using this method, two new maximal
tractable subsets for the region connection calculus are identified. The known
maximal tractable subset of Allen's interval algebra is also derived.
In the fourth session, the paper by Bliek and Sam-Haroud introduces a new
algorithm called partial path consistency, which provides a pruning level
close to path consistency with a lower space complexity. This algorithm is
especially interesting for triangulated constraint graphs. The paper by Hoffmann
and Koehler considers the problem of recovering sets of a
large set of sets satisfying some query. They provide a data structure and
an algorithm allowing a compact representation of the large set of sets and
an efficient answering to subset and superset queries.
The paper by Cucchiara, Mello, Milano and Piccardi considers
a 3D visual object recognition problem. This problem is modelled as a CSP
in which not all values (image characteristics) of every domain are known
in advance. Value aquisition is costly, and it is obtained under request.
An interactive CSP framework is proposed, including interactive forward
checking algorithms. Empirical results are given.
In summary, constraints were very present at IJCAI-99. Contributions ranged
from theoretical studies to approaches motivated by practical applications.
On the theoretical side, tractability issues received most of the attention.
On the algorithmic side, the study of specific types of contraints and the
exploitation of constraint characteristics were considered. Finally, on the
application side, most of the effort was devoted to problem modelization and
very large problems.
Pedro Meseguer
Institut d'Investigació en Intelligència Artificial
Consejo Superior de Investigaciones Científicas
Campus UAB
08183 Bellaterra, Spain