CP98 -- Program Monday, October 26 8:00 Registration Registration desk 8:45 Opening Auditorium 9:00 Invited Lecture: Open Constraint Programming Joxan Jaffar Auditorium Session chair: Michael Maher 10:30 Coffee-Break Session S1 Sesssion chair: Peter Stuckey Auditorium 11:00 Early Projection in CLP(R) Andreas Fordan, Roland Yap 11:30 Error-Correcting Source Code Yasuhiro Ajiro, Kazunori Ueda, Kenta Cho 12:00 Compiling Semiring-based Constraints with clp(FD,S) Yan Georget, Philippe Codognet 12:30 Lunch Session S2 Session chair: Barbara Smith Auditorium 14:00 Global Constraints for Partials CSPs:A Case-Study of Resource and Due Date Constraints Philippe Baptiste, Claude Le Pape 14:30 Constraints for Object Recognition in Aerial Images- Handling of Unobserved Features Thomas H. Kolbe 15:00 Fuzzifying the Constraint Hierarchies Framework R. W. L. Kam, J. H. M. Lee 15:30 Anytime Lower Bounds for Constraint Violation Minimization Problems Bertrand Cabon, Simon de Givry, Gerard Verfaillie 16:00 Coffee-Break Tutorials (in parallel) 16:30 From Constraint Programming to Hybrid Problem-Solving Algorithms Claude Le Pape and Mark Wallace Room Fermi Session chair: Jimmy Lee Branch-and-infer: A unifying framework for integer linear programming and finite domain constraint programming Alexander Bockmayr and Thomas Kasper Room Pacinotti Session chair: Win Nuijten 19:00 Welcome reception Gallery Tuesday, October 27 9:00 Invited Lecture: Heuristics for constraint satisfaction Patrick Prosser Auditorium Session chair: Jean-Francois Puget 10:30 Coffee-Break Session S3 Auditorium Session chair: Yves Caseau 11:00 A Tableau Based Constraint Solving Toolkit for Interactive Graphical Applications Kim Marriott, Sitt Sen Chok, Alan Finlay 11:30 Stable Solutions for Dynamic Constraint Satisfaction Problems Richard J. Wallace and Eugene C. Freuder 12:00 A Polynomial Time Local Propagation Algorithm for General Dataflow Constraint Problems Gilles Trombettoni 12:30 Lunch Session S4 Auditorium Session chair: Kim Marriott 14:00 Suggestion Strategies for Constraint-Based Matchmaker Agents Eugene C. Freuder and Richard J. Wallace 14:30 Constraint-based Problem Decomposition for a Key Configuration Problem Ulrich Junker 15:00 Constraint Techniques for Solving the Protein Structure Prediction Problem Rolf Backofen 15:30 A Generic Model and Hybrid Algorithm for Hoist Scheduling Problems Robert Rodosek and Mark Wallace 16:00 Coffee-Break Tutorials (in parallel) 16:30 Distributed Constraint Satisfaction: Foundation and Applications Makoto Yokoo Room Fermi Session chair: Philippe Codognet Principles and Methods for Automated Reasoning: Variable Elimination versus Search Rina Dechter Room Pacinotti Session chair: Ian Gent 18:00 Posters (see list of posters later in the booklet) Gallery Wednesday, October 28 9:00 Invited Lecture: Constructing Constraints Peter Jeavons Auditorium Session chair: Francesca Rossi 10:30 Coffee-Break Session S5 Auditorium Session chair: Alexander Bockmayr 11:00 A unified framework for interval constraints and interval arithmetic T.J. Hickey, M.H. van Emden, H. Wu 11:30 Constraint Representation for Propagation Warwick Harvey and Peter J. Stuckey 12:00 A Note on Partial Consistencies over Continuous Domains Helene Collavizza, Francois Delobel, Michel Rueher 12:30 Lunch 14:30 Excursion to Lucca and dinner at Villa Mansi Thursday, October 29 Session S6 Auditorium Session chair: Alex Brodsky 9:00 On Completion of Constraint Handling Rules Slim Abdennadher and Thom Fruehwirth 9:30 Safe Datalog Queries with Linear Constraints. Peter Revesz 10:00 Introducing External Functions in Constraint Query Languages Barbara Catania, Alberto Belussi, Elisa Bertino 10:30 Coffee-Break Session S7 Auditorium Session chair: Makoto Yokoo 11:00 Consistency Techniques in Ordinary Differential Equations Yves Deville, Micha Janssens, Pascal Van Hentenryck 11:30 Combining Topological and Qualitative Size Constraints for Spatial Reasoning Alfonso Gerevini and Jochen Renz 12:00 Using Graph Decomposition for Solving Continuous CSPs Christian Bliek, Bertrand Neveu, Gilles Trombettoni 12:30 Lunch Session S8 Auditorium Session chair: Helmut Simonis 14:00 SALSA: a language for search algorithms F. Laburthe, Y. Caseau 14:30 Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems Paul Shaw 15:00 Non-systematic Search and Learning: An empirical study E Thomas Richards and Barry Richards 15:30 Random Constraint Satisfaction: theory meets practice Ewan MacIntyre, Patrick Prosser, Barbara Smith, and Toby Walsh 16:00 Coffee-Break Session S9 Auditorium Session chair: Maurizio Gabbrielli 16:30 Optimized Q-pivot for exact linear solvers David-Olivier Azulay, Jean-Francois Pique 17:00 Linear concurrent constraint programming over reals Vincent Schachter Telecommunication application contest: winner award and presentation 17:30 Optimal placement of base stations in wireless indoor telecommunications Thom Fruewirth and Pascal Brisset Friday, October 30 9:00 -- 10:30 Workshops (in parallel, see later in the booklet) 10:30 -- 11:00 Coffee-Break 11:00 -- 12:30 Workshops 12:30 Lunch 14:00 -- 16:00 Workshops 16:00 -- 16:30 Coffee-Break 16:30 -- 18:00 Workshops List of posters (Tuesday, October 28, from 18:00 to 19:00, in the gallery) Generation of Test Patterns for Differential Diagnosis of Digital Circuits Francisco Azevedo and Pedro Barahona Combine & Conquer: Genetic Algorithm and CP for Optimization Nicolas Barnier, Pascal Brisset Some Experiments on Learning Soft Constraints. Alessandro Biso, Francesca Rossi and Alessandro Sperduti. Scheduling Multi-Capacitated Resources under Complex Temporal Constraints Amedeo Cesta, Angelo Oddi, and Stephen F. Smith Implementing Global Constraints with Index-Sets and Constraint Templates Yves Colombani Generating feasible schedules for a pick-up and delivery problem Eric Domenjoud, Claude Kirchner and Jianyang Zhou An impartial efficiency comparison of FD constraint systems Antonio J. Fernandez, Pat Hill Optimizing with constraints: a case study in scheduling maintenance of electric power units Daniel Frost and Rina Dechter Some Surprising Regularities in the Behavior of Stochastic Local Search Holger H. Hoos and Thomas Stuetzle Modelling CSP Solution Algorithms with Petri Decision Nets Stephan Pontow A Framework for Assertion-Based Debugging in CLP G. Puebla, F. Bueno, M. Hermenegildo Parallel Execution Models for Constraint Propagation A. Ruiz-Andino, J. Ruz, L. Araujo, F. Saez Using Blocks for Constraint Satisfaction B. Seybold, F. Metzger, G. Ogan, K. Simon Adaptive Solving of Equations over Rational Trees Armin Wolf Satellite workshops (in parallel, all day Friday, October 30) W1: Modelling and Computing with Concurrent Constraint Programming Organizers: Andreas Podeslki, Vijay Saraswat, Kazunori Ueda Room Galilei Concurrent Constraint Programming (CCP) is a simple and elegant formalism for modelling concurrent, parallel, and distributed computation. This workshop is intended to be a forum for discussion on the practical aspects of CCP. W2: Large Scale Combinatorial Optimization and Constraints Organizers: Mark Wallace, Yves Caseau, Eric Jacquet-Lagreze, Helmut Simonis, Gilles Pesant Auditorium Solving large scale combinatorial optimization and constraint problems may require a variety of techniques to solve successfully. This workshop explores the integration of hybrid algorithms for complex optimization problems, combining diverse techniques such as constraint propagation, Lagrangean relaxation, linear programming, randomised search, etc. W3: Constraint Problem Reformulation Organizers: Jeremy Frank, Mihaela Sabin Room Pacinotti The precise representation/formulation of a constraint problem plays an important role in solving constraint problems. This workshop focuses on reformulating constraint problems to take advantage of efficient techniques developed for a variety of constraint problem domains. W4: Constraints in Bioinformatics/Biocomputing Organizers: David Gilbert, Rolf Backofen, Geoff Barton, Ingvar Eidhammer, Christine Gaspin, Roland Yap Aula B Bioinformatics is the development and application of methods in mathematics and informatics for approaching problems in molecular biology. Biocomputing uses architectures and behaviors inspired from biology as models for computation. The theme of this workshop is the use of constraint programming technology in these two areas; this is the second workshop on this very exciting and rapidly expanding area. W5: Set Constraints and Constraint-based Program Analysis Organizers: Alexander Aiken, Harald Ganzinger, Nevin Heintze, Fritz Henglein, Joxan Jaffar, Bruno Legeard, David McAllester, Leszek Pacholski, Jens Palsberg, Andreas Podelski, Jean-Francois Puget, Jakob Rehof, Sophie Tison Room Fermi Constraints, particularly set constraints, have recently become important in their application to problems in type and program analysis. Many algorithmic and conceptual advances in type inference and program analysis make direct or indirect use of set constraints. This workshop provides a discussion forum for researchers working on all aspects of set constraints and program analysis (e.g., for debugging) based on constraint reasoning in general. E-mail connection Several PCs with Internet connection are available from Monday morning to Thursday afternoon. Social Program Welcome reception, in the gallery (Monday afternoon, from 19:00 to 20:00). Guided excursion to the city of Lucca (Wednesday afternoon, from 15:00 to 19:00). Lucca, which is one of the most beautiful and well maintained cities in Tuscany, is just a 30 minute bus trip from Pisa. We will leave from the conference site at 14:30 and spend the afternoon touring the ancient walls, churches, and streets of Lucca. Dinner at Villa Mansi (Wednesday evening, from 19:30 to 11:30). Villa Mansi is a magnificent villa built in the 16th century, with impressive paintings and an enchanting park. The villa is just a 20 minute bus ride from Lucca. We will leave Lucca at 19:00 to reach the villa and have dinner there. Additional tickets Additional lunch and dinner tickets can be obtained at the reception desk. A lunch ticket costs 30.000 Lira, and a dinner ticket costs 100.000 Lira. Dinner tickets include the excursion to Lucca. Facilities Fax and Xerox copies can be made inside the congress center with a charge. Just ask the reception desk for information about this or any other need you may have. Contact points If you need to be contacted or reached at the Congress Center, you may use the following address/phone/fax: Palazzo dei Congressi di Pisa Via Matteotti n.1 56100 Pisa Tel: +39-50-598139/203 Fax: +39-50-598112