Sixth Annual Workshop of
the ERCIM Working Group on Constraints

Theme: constraint solving techniques and modelling real-life problems

Prague, Czech Republic
June 18-20, 2001

Invited talks:

INTEGRATING OPERATIONS RESEARCH TECHNIQUES IN CONSTRAINT PROGRAMMING
Michela Milano (Bologna University, Italy)

The aim of the tutorial is to provide an overview on the integration directions of (exact) Mathematical Programming (MP) techniques, widely used in Operations Research (OR), and Constraint Programming (CP) for facing Combinatorial Optimization Problems.

The tutorial will start by providing preliminary notions on OR concepts: we will describe (Mixed) Integer Programming and Linear Programming, their geometrical properties, and solving algorithms; we will explain how relaxations can be exploited in branch and bound; cutting plane generation techniques in branch and cut will be presented, and finally column generation approaches for solving large scale problems are introduced.

In the second part, we focus on how these techniques have been exploited in CP to enhance its performances. We start from "solver integration" where each solver is in charge of solving the problem part or abstraction it is more suitable for. Then, we will concentrate on global constraints as a basis for developing such an integration. We show how to introduce Linear Programming and Cutting Planes techniques in global constraints, and we provide some examples of their use.

References to recent bibliography are provided. Open problems and research directions are finally discussed.


LARGE SCALE CONSTRAINT APPLICATIONS
Helmut Simonis (Parc Technologies Ltd, United Kingdom)

In this talk we present some large scale constraint applications which have been developed at COSYTEC and at IC-Parc/Parc Technologies. We show how the capabilities of the underlying tools (CHIP and Eclipse) shape the choice of the applications to be considered, and how, at the same time, experience with applications leads to the further development of the tools. Although CHIP and Eclipse are superficially quite similar, being constraint systems based on a Prolog kernel, they represent two very different design philosophies.

CHIP is centered on a finite domain solver with powerful, predefined global constraints. Modelling consists in finding the right combination of these constraints together with a clever search strategy. The typical applications for this tool are scheduling and resource allocation problems with constraints which are hard to satisfy. As an example we will discuss one large scale scheduling application for animal feed milling.

Eclipse is using a much faster kernel and enables the programmer to define new constraints and even constraint solvers quite easily. Modelling here consists in choosing the right hybrid combination of different solving techniques. This diversity on one side increases the scope of problems that can be tackled, but on the other side also puts more demands on the programmer. As examples we will discuss two applications currently being developed at Parc Technologies, one in the airline domain, the other a network optimization problem.

Accepted Papers:

Dynamic Global Constraints: A First View [ps.zip]
Roman Barták

Verification of Timed Automata Using Rewrite Rules and Strategies [ps.zip]
Emmanuel Beffara, Olivier Bournez, Hassem Kacem, Claude Kirchner

Solving Assembly Line Balancing Problems by Combining IP and CP [ps.zip]
Alexander Bockmayr and Nicolai Pisaruk

Constraint Propagation in Presence of Arrays [ps.zip]
Sebastian Brand

Variable and Value Ordering When Solving Balanced Academic Curriculum Problems [ps.zip]
Carlos Castro and Sebastian Manzano

CHR as grammar formalism: A first report [ps.zip]
Henning Christiansen

Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems
Maarten van Emden

CLP versus LS on Log-based Reconciliation Problems [ps.zip]
François Fages

Branching: the Essence of Constraint Solving [PDF]
Antonio Fernandez and Patricia Hill

Component Programming and Interoperability in Constraint Solver Design [PDF]
Frédéric Goualard

Enhancing Constraint Propagation with Composition Operators [ps.zip]
Laurent Granvilliers and Eric Monfroy

The "alldifferent" constraint: a survey [ps.zip]
Willem Jan van Hoeve

Assigning Satisfaction Values to Constraints: an Algorithm to Solve Dynamic Meta-Constraints [PDF]
Janet van der Linden

Interactive Timetabling [ps.zip]
Tomas Müller and Roman Barták

Solving Composed First-Order Constraints from Discrete-Time Robust Control [ps.zip]
Stefan Ratschan and Luc Jaulin

Soft Scheduling [ps.zip]
Hana Rudová

CLP Approaches to 2D Angle Placements [PDF]
Tomasz Szczygiel

© 2001 Roman Barták

Home | Call for papers | Papers | Program | Local information