Constraint Programming at IJCAI-99

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