[Back]

Program

See also the talk abstracts and slides below.

Talk Abstracts and Slides

Special Invited Talk

Rule-based Approach to Constraint Programming

Krzysztof R. Apt (CWI / University of Amsterdam / National University of Singapore)

Rules keep appearing as a means of expressing computation and information. Typical, relatively recent, examples are web-based reasoning, data mining and the concept of business rules.

In this lecture we show that at various levels of abstraction constraint programming (CP) can be viewed as an instance of rule-based programming. At each level this view sheds light on the essence of CP.

In particular, at the highest level it allows us to bring CP closer to the computation as deduction paradigm. At the lower levels it allows us to address the issues of efficiency of computations and of automatic generation of constraint propagation algorithms.

[slides]

Talks by Invited Speakers

ILOG Solver and the New Challenges of Constraint Programming

Laurent Perron (ILOG S.A.)

In this presentation, we will present the new challenges faced by the Constraint Programming optimization suite in ILOG. In particular, we will detail our current efforts to address new demands in accessibility, robustness and clean separation between the modeling and the solving of a problem.

[slides]

Computer-Aided Modelling of Constraint Satisfaction Problems

Christian Bessiere (LIRMM-CNRS, Montpellier)

Constraint programming is a technology which is now widely used to solve combinatorial problems in industrial applications. However, users of constraint programming need significant expertise in order to model their problem appropriately. The lack of availability of such expertise can be a significant bottleneck to the broader uptake of constraint technology in the real world. This presentation is concerned with automating as much as possible the burden of the formulation of constraint satisfaction problems. We will define the issue of model acquisition from sets of instances that can be examples of acceptable solutions or non-desirable assignments of the problem we would like to express. We will propose a decomposition of the 'model acquisition' task in elementary steps that will permit to draw a roadmap of some of the problems that need to be tackled. We will focus on the 'constraint acquisition' step by combining techniques from the fields of machine learning and constraint programming. Such an approach has the potential to be of assistance to a novice who is trying to build a model of her problem.

[slides]

Towards a Heterogeneous Constraint Solving System on the Grid

Mutsunori Banbara (Kobe University)
Shuji Ohnishi (Kobe University)
Katsumi Inoue (National Institute of Informatics)
Naoyuki Tamura (Kobe University)

Recent development of cooperative constraint solving systems suggests a successful direction to extend constraint programming to be more intelligent and more efficient. However, the entirely almost systems have supported only homogeneous constraint solvers and haven't run on the Grid computing environment.

In this talk, we describe an outline of our projects: HECS and g-HECS.

In HECS (HEterogeneous Constraint Solving) project, we have developed a constraint solving system, called HECS, that enables real-time collaboration among heterogeneous constraint solvers. Each solver runs separately on an individual thread and communicates with the others through shared blackboard. In addition to constraint solvers for finite domains of integers and boolean values, our system supports local-search-based solvers and a Mathematica interface.

The HECS system runs on any platform supporting Java and consists of five sub-systems: Cream, Calc/Cream, Multisat, Prolog Cafe, and Maglog. Cream is a Java class library of constraint programming for finite domains of integers and supports various optimization algorithms such as Simulated Annealing, Taboo Search, and etc. Calc/Cream is a constraint spreadsheet developed as an add-in package for OpenOffice.org Calc. Multisat is a parallel execution system for multiple SAT solvers. Prolog Cafe is a Prolog to Java translator system. Maglog is a Prolog-based framework for building mobile multi-agent systems.

It is well-known that constraint solving systems require much computational resource to solve large scaled problems. Grid computing is a hot topic on the recent network infrastructure and can be promising approach to get much computational resource for constraint solving. However, the HECS system does not run on the Grid.

g-HECS is a on-going project for developing a heterogeneous constraint solving system on the Grid. We have developed two experimental systems on Sun Grid Engine and Globus Toolkit respectively. In each system, constraint solvers are implemented using Cream. We use Job Shop Scheduling Problem as benchmarks. In performance, our systems on the Grid gave nice speedup compared with Cream on a single machine.

[slides]

SiLCC a Concurrent Constraint Language Based on Linear Logic

François Fages (INRIA Rocquencourt, Paris)

We shall present the semantics of concurrent constraint programming languages in linear logic and the system SiLCC we are currently implementing using GNU-Prolog compiling technology extended with concurrent and imperative features.

[slides]

LMNtal — From Concurrent Constraint Programming to Concurrent Hierarchical Graph Rewriting

Kazunori Ueda (Waseda University)

LMNtal (pronouned “elemental”) is a simple language model based on graph rewriting that uses logical variables to represent links and membranes to represent hierarchies. The two major goals of LMNtal are (i) to unify various computational models based on multiset rewriting and (ii) to serve as the basis of a truly general-purpose language covering various platforms ranging from wide-area to embedded computation. Another contribution of the model is it greatly facilitates programming with dynamic data structures.

LMNtal is an outcome of the attempt to unify two extensions of concurrent logic programming, namely concurrent constraint programming and Constraint Handling Rules, where our focus has been multiset rewriting rather than constraint handling. At the same time, LMNtal can be regarded as a hierarchical multiset rewriting language augmented with logical links, and many computational models including Petri Nets, Gamma, the pi-calculus, etc., can be encoded into LMNtal.

[slides]

Distributed Constraint Satisfaction: Foundation of Cooperation in Multi-Agent Systems

Makoto Yokoo (Kyushu University)

When there exist multiple agents in a shared environment, there usually exist constraints among possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. The research of Constraint Satisfaction Problems has a long and distinguished history in AI as a general framework that can formalize various application problems. Similarly, a distributed CSP is a fundamental problem for achieving the coordination among agents, and can formalize various application problems in Multi-agent Systems (e.g., distributed resource allocation problems, distributed scheduling problems, distributed interpretation tasks, and multi-agent truth maintenance tasks). This talk will explain the formal definition, algorithms, and MAS applications of distributed CSPs.

[slides]

Distributed Lagrangean Relaxation Method for Generalized Mutual Assignment Problems

Katsutoshi Hirayama (Kobe University)

Generalized assignment problems (GAPs) are typical NP-hard problems and have been studied for many years mainly in the operations research community. The goal of GAPs is to find an optimal assignment of jobs to agents such that the assignment satisfies all of the resource constraints imposed on individual agents. This work provides a distributed formulation of GAPs, generalized mutual assignment problems (GMAPs), to deal with the problems of task/job assignment in multi-agent systems. Then, we present a distributed lagrangean relaxation method that enables the agents to solve GMAPs without any global control mechanism nor globally accessible communication medium like shared memory. In the method we introduce a parameter that controls the range of ``noise'' mixed in with the increment/decrement in a lagrangean multiplier. This parameter can be used to make the agents quickly agree on a feasible solution with reasonably good quality. Furthermore, our experimental results imply that the parameter may also allow you to control a tradeoff between the quality of a solution and the cost of finding it.

[slides]

ILOG Plant PowerOps — An Adaptable Manufacturing Scheduling System

Filippo Focacci (ILOG S.A.)

ILOG Plant PowerOps is a new Advanced Planning and Scheduling (APS) product dedicated to production planning and detailed scheduling for the process industry. The product is based on advanced optimization, business rules and visualization technology available at ILOG, and capitalizes on the experience acquired on a variety of supply chain optimization projects. The presentation will be divided in two parts. In the first part I will give insights of some of the constraint-based scheduling and constrained local search methods that are applied in the scheduling engine of ILOG Plant PowerOps. In the second part a software demonstration will cover several typical use case scenarios in manufacturing for both production planners and production control personnel. I begin by demonstrating a graphical planning board, where the user can specify scheduling parameters and generate an optimal or near-optimal schedule. Finally I demonstrate a natural language maintenance and configuration interface from which users can adapt the software as business conditions and logic change.

[slides]

Application of Generic Constraint Solving Techniques for Insightful Engineering Design

Hiroyuki Sawada (National Institute of Advanced Industrial Science and Technology)

Engineering design is an intensive decision making process. As a design solution evolves, more and more design parameters are introduced to concretise the solution. The high number of design parameters very often pose great challenges for engineering designers to produce an optimal design solution, especially in the case of multidisciplinary design. With traditional computer aided design analysis tools, designers often use a trial and error approach based on numerical methods, which produces some analysis solution values without giving underlying relationships among design parameters. Designers hence cannot gain any insights into the design problem described by fundamental relationships of design parameters of incomplete design solutions. These insights are the key to an optimal design solution, as a better design solution can be generated by exploring alternative solutions using the insights into the important design parameters for further design decision making.

In my presentation, I will describe a new analytical and predictive design method to help designers in gaining important insights during design synthesis of an engineering design. This can avoid the problems of too many unnecessary iterations caused by sequential design process in which analysis and optimisation can only be carried out after a solution is completed.

To achieve the above aim, new constraint solving methods based on generic and rigorous principles of symbolic algebra have been derived. These methods have collectively overcome the difficulties of other constraint solving methods, in which analysis results are not guaranteed to be correct and conclusive, and they can be only generated through many trial and errors based on designers' individual knowledge and experience. The new methods have been integrated into a prototype system "DeCoSolver". Using the prototype system, these methods have been evaluated through case studies of multidisciplinary design problems, and have proven to be effective. The evaluation results illustrate DeCoSolver's ability in handling multidisciplinary design problems and helping designers in gaining insights and exploring design alternatives.

[slides]

The CO2 Project : Purpose, Results and Future Challenges

Laurent Zimmer (Dassault Aviation)

CO2 is a joint project between Dassault Aviation, LINA, ENSAM and ESTIA which is granted by the French Ministry of Economy, Finance and Industry. It adresses Engineering Design Problem Solving with Constraints and aims at developping for preliminary design issues both algorithms and methods which are mainly based on Interval Constraint Programming. The results are implemented into a software prototype called Constraint Explorer(CE)which gathers modelling and calculus abilities.

During the presentation I will give the main caracteristics of CE and I will describe various industrial case studies which have been processed during the project. These case studies will act as a guideline to successively present the field of preliminary engineering design, illustrate the capacities or the limits of the current tool and finally point out some research issues to overcome in the future.

[slides]

Koalog Constraint Solver: Fast Constraint Solving in Java

Yan Georget (Koalog)

In this talk, I will introduce Koalog Constraint Solver, a Java library for constraint programming.

Having justified the choice of the language (Java) and the form (library), I will discuss some architectural choices: genericity of the core engine, scheduling of the constraints, backtrackable references, ...

Then, I will briefly compare Koalog Constraint Solver with existing systems and give some performance results.

[slides]

Building “Problem Solving Engines” for Combinatorial Optimization

Toshihide Ibaraki (Kwansei Gakuin University)

We describe our attempts to build problem solving engines that cover a large portion of combinatorial optimization problems encountered in real world applications. For this, we select a list of standard problems, and develop their solvers which are based on local search and metaheuristics. As standard problems, we have chosen so far CSP (constraint satisfaction problem), RCPSP (recource constrained project scheduling problem), GAP (generalized assignment problem), VRP (vehicle routing problem), SCP (set covering problem), MAX-SAT (maximum satisfiability problem), 2PP (2-dimensional packing problem) and others. In this talk, we outline definitions of these problems, algorithmic contents of engines, and some computational results, putting emphasis on VRP and 2PP.

[slides]

Combination of Exact and Approximate Methods for SAT and MAX-SAT Problems

Frédéric Saubion (LERIA, University of Angers)

Several hybridizations of exact and approximate methods for the SAT and MAX-SAT problems have been studied [mazure98,borchers99,habet02] but they often combine two methods without any real interaction, since these methods are based on different search space representations. The aim of this paper is to propose a new resolution framework which introduces a third truth value "undefined" in order to unify exact and approximate methods and to improve the resolution efficiency. Using this resolution framework, we compare a classic Tabu Search algorithm with the hybridization of a Branch and Bound algorithm and a Tabu Search. Promising results are obtained and show the interest of this resolution framework.

[slides]

Algebraic Approaches for Constraint Solving

Yosuke Sato (Tokyo University of Science)

The notion of ideals in commutative and non-commutative rings is a fundamental and indispensable tool in almost all branches of contemporary mathematics. Especially polynomial ideals play important roles in many areas of computational mathematics such as constructive commutative algebra, computational algebraic analysis, geometric theorem proving and computational boolean algebra, etc. The theory of Gröbner bases introduced by B. Buchberger in 1965 enables us to have powerful computation tools for solving many problems of polynomial ideals.

In this whorkshop, we present how we can apply Gröbner bases to constraint solving on various domains such as real numbers, complex numbers, and boolean values. We begin with a quick review of the theory of Gröbner bases, then we show how we can solve many constraints using Gröbner bases. We do not get into detailed description of mathematical results, but give elementary and intuitive explanations as much as possible through many computation examples. If we have time, we also would like to introduce our recent results concerning parametric constraint solving.

[slides]

Local Consistency in Soft Constraints Networks

Thomas Schiex (INRA Toulouse)

Finite domains constraint programming solvers essentially rely on variants of constraint satisfaction local consistency algorithms that range from bound consistency (aka 2b-consistency) to dedicated constraint processing algorithms (for so-called global constraints).

In the past decade, the very notion of constraint satisfaction has been extended to take into account cost functions also known as soft constraints. Soft constraint networks properly extend constraint networks. Several proposals for defining and enforcing local consistency in soft constraint networks have been proposed in the last few years, some being inspired by a CP approach and other by a CSP approach. I will rapidly introduce and compare somem of these approaches and see how they can be integrated.

[slides]

Joint Project Sakura-SCooP: Presentation, Progress, Perspectives

Martine Ceberio (University of Texas at El Paso)

Sakura-SCooP is a joint project on Flexible Constraint Solving, between NII and LINA. It was defined about one year and a half ago, and actually started in early 2004. In this presentation, I will give a tour of this project, starting from its aim, through the perspectives we can draw from its expected achievements. I will in particular present the work currently carried out, and point out major issues you plan to address.

[slides]

Proving and Constraint Solving in Computational Origami

Tetsuo Ida (University of Tsukuba)
Dorin Tepeneu (University of Tsukuba)
Bruno Buchberger (Johannes Kepler University)
Judit Robu (Babes-Bolyai University)

Origami (paper folding) has a long tradition in Japan's culture and education. We are developing a computational origami system, based on symbolic computation system Mathematica, for performing and reasoning about origami on the computer. This system is based on the implementation of the six fundamental origami folding steps (origami axioms) formulated by Huzita. In this paper, we show how our system performs origami folds by constraint solving, visualizes each step of origami construction, and automatically proves general theorems on the result of origami construction using algebraic methods. We illustrate this by a simple example of trisecting an angle by origami. The trisection of an angle is known to be impossible by means of a ruler and a compass. The entire process of computational origami shows nontrivial combination of symbolic constraint solving, theorem proving and graphical processing. The talk is based on the paper presented at AISC (Artificial Intelligence and Symbolic Computation) 2004.

[slides 1, 2]

Musical Applications of Constraint Programming using a Local Search Algorithm

Charlotte Truchet (LINA, University of Nantes)

Constraint Programming (CP) allows to modelize and solve combinatory problems by specifying some partial information on variables, unknowns of the problem. We will present applications of CP to musical computer assisted composition. Working with contemporary composers at IRCAM (french Institute for Research and Coordination Acoustics / Music), we have modelized fourteen musical Constraint Satisfaction Problems (CSPs), either stated by contemporary composers, or of musical analysis and instrumentation. We will present the main features of these musical CSPs, for instance most of them are overconstrained. We will explain why we have chosen a local search algorithm to solve them. This algorithm, called Adaptive Search, has been proposed by P. Codognet and has been shown to be very efficient on classical CSPs. It is based on a projection of the cost functions at the variable's level. This allows to iteratively modify the variable with the "worst value" of the current configuration. Adaptive Search has been implemented as a library of OpenMusic, an environnement for computer assisted composition developed at IRCAM. The library takes advantage of the incompleteness of the resolution process by editing the local minima, thus giving approximate solutions to the overconstrained CSPs.

[slides]

A Static Depiction and Input Technique for 2D Animations

Shin Takahashi (University of Tsukuba)
Yoshikazu Kato (Tokyo Institute of Technology)
Etsuya Shibayama (Tokyo Institute of Technology)

One of the methods to create animations is to select and apply animation effects from animation libraries. For example, when we create 2D animations using Microsoft PowerPoint, we assign effects to objects and define their parameters, such as their path, speed, and time of movement. To do this, we use conventional interfaces like menus or dialog boxes.

However, the motion effects associated with each object are not displayed on the canvas explicitly, so the user can investigate the properties of each object only by opening a dialog box to see the animations that are associated with the object. Moreover, setting various parameters using menus and dialog boxes is time-consuming because the user must set each parameter individually.

We have therefore developed a method that uses effect lines to depict and set each effect and its parameters. Effect lines are a popular technique that is used in comics and cartoons. They depict information on the effects of an object, such as its speed, length of path, and degree of rotation. They enable us to set effects using simple pen-strokes. In addition, the effect lines can be combined. That is, the effects that each set of effect lines have are merged. This feature makes effect lines flexible for users to create various animations. We have developed a prototype animation authoring system. Using this system, the user can create various animations with effect lines.

Effect lines can be naturally understood in our declarative constraint-based framework for creating animations [Takahashi et al.1998]. They can be regarded as transitional operations that change one picture to the next picture in our framework. We will also talk about the interpretation of effect lines in our framework, and the future directions derived from the interpretation.

Reference
[Takahashi et al.1998] Shin Takahashi, Satoshi Matsuoka, Ken Miyashita, Hiroshi Hosobe, and Tomihisa Kamada. “A Constraint-Based Approach for Visualization and Animation.” Constraints: An International Journal, Vol.3, No.1, Kluwer Academic Publishers, pp. 61-86, 1998.

[slides]

From Eviss to Viola: Visual Parser Generators based on Extended Constraint Multiset Grammars

Jiro Tanaka (University of Tsukuba)

We are working for visual paring in these years. We have developed the series of visual parser generators, such as Eviss, VIC and Rainbow, based on Extended Constraint Multiset Grammars (ECMG). The visual parser generators generate a spatial parser by defining ECMG of a visual language. The generated spatial parser can analyze the figures and execute the specified actions.

We propose yet another visual parser generator Viola, which can define Extended Constraint Multiset Grammars graphically and execute a visual system on the same screen. By using Viola, the user can define various visual systems interactively. It becomes possible to define grammars using graphically and construct visual systems dynamically, while checking the grammar at the execution time.

[slides]

Constraint Solvers for Graphical User Interface Applications

Hiroshi Hosobe (National Institute of Informatics)

Constraints have been playing an important role in the graphical user interface field since its infancy. A prime use of constraints in this field is to automatically maintain geometric layouts of graphical objects. To facilitate the construction of constraint-based graphical user interface applications, researchers have proposed various constraint satisfaction methods and constraint solvers. This talk first briefly outlines these technologies, and then presents several constraint solvers that have been or are being developed by the speaker.

[slides]

Exploiting Structure in Numerical CSPs Solving

Christophe Jermann (LINA, University of Nantes)

We present a technique, called inter-block backtracking (IBB), which improves interval solving of decomposed numerical constraint satisfaction problems (NCSPs). This technique, introduced in 1998 by Bliek et al., handles a NCSP previously decomposed into a set of (small) KxK sub-problems, called blocks. A (global) solution is obtained by combining the (partial) solutions computed in the different blocks. The approach seems particularly suitable for improving interval solving techniques.

We present and discuss different variants of IBB which differ in their backtracking and filtering strategies. Interesting variants of IBB which use interval solving methods are compared on a sample of 8 NCSPs issued from computer-aided design. We show that limiting the scope of the filtering to the blocks is very fruitfull. For all the tested instances, IBB gains several orders of magnitude as compared to a global solving.

[slides]

An Efficient and Safe Framework for Handling Numerical Constraint Systems and for Solving Optimization Problems

Michel Rueher (I3S, University of Nice)
(With Yahia Lebbah and Claude Michel)

We first recall the principles of Quad, a global constraint that works on a tight and safe linear relaxation of quadratic subsystems of constraints. Then, we introduce a generalisation of Quad to polynomial constraint systems. We also introduce a method to get safe linear relaxations and we show how to compute safe bounds of the variables of the linear constraint system. Different linearisation techniques are investigated to limit the number of generated constraints. QuadSolver, a new branch and prune algorithm that combines Quad, local consistencies and interval methods is introduced.

QuadSolver has been evaluated on a variety of benchmarks ranging from kinematics, mechanics and robotics. On these benchmarks, it outperforms classical interval methods as well as CSP solvers and it compares well with state-of-the-art optimisation solvers.

In a second step we show how QuadSolver can be used to tackle optimization problems. The use of interval methods provides computational proofs of existence and location of global optima. These methods find the global optimum and provide bounds on its value and location. Efficient global optimization systems like BARON use linear relaxations to compute a lower bound of the objective function, and local search methods to obtain an upper bound of the optima. However, systems like BARON are not safe and may provide wrong solutions. We introduce here an efficient and safe framework to find a global optimum and bounds on its value. Local search methods are combined with QuadSolver to compute a safe upper bound. A lower bound is computed on a linear relaxation of the constraint system and the objective function. This computation is based on a safe and rigorous use of linear programming techniques.

[slides]

Bayesian Estimation Using Interval Analysis

Luc Jaulin (E3I2, ENSIETA)

Parameter set estimation deals with characterizing a (preferably small) set which encloses the actual parameter vector of a parametric model from measurement data. In the context of bounded-error estimation, the measurement error is assumed to be bounded and the feasible set for the parameter vector can be written as the solution set of a constraint satisfaction problem (CSP) for which interval constraint propagation methods have been shown to be particularly efficient. In a probabilistic context, the error is not anymore described by membership intervals, but by probability density functions (pdf). The Bayes rule then makes it possible to obtain the posterior pdf for the parameter vector. The set estimation in such a probabilistic context is often called Bayesian estimation. The set to be estimated becomes the optimal confidence region and corresponds to the smallest set, in the parameter space, which contains the parameter vector with a given probability. This set cannot be described by a CSP and existing interval methods cannot be used without a serious adaptation. The goal of the presentation is to show that interval methods can be used to deal with set estimation even in a probabilistic context. This could help to make interval analysis more attractive to the Bayesian estimation community, most of who almost ignore interval computation, except maybe for its ability to deal with global optimization in a guaranteed way.

[slides]