Trends in Constraint Programming E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 663

Veröffentlichungsjahr: 2013

Beschreibung

This title brings together the best papers on a range of topics raised at the annual International Conference on Principles and Practice of Constraint Programming. This conference provides papers and workshops which produce new insights, concepts and results which can then be used by those involved in this area to develop their own work.

Leseprobe

Table of Contents

Introduction

PART I. The Past, Present and Future of Constraint Programming

Chapter 1. Constraint Programming as Declarative Algorithmics

1.1. The CHIP project

1.2. The Numerica project

1.3. The OPL project

1.4. The Comet project

1.5. The future of constraint programming

Chapter 2. Constraint Programming Tools

2.1. Introduction

2.2. Invited talks

2.3. System presentations

2.4. Panels

2.5. Conclusion

2.6. References

Chapter 3. The Next 10 Years of Constraint Programming

3.1. Pedro Barahona

3.2. Christian Bessiere

3.3. Peter Jeavons

3.4. Pedro Meseguer

3.5. Gilles Pesant

3.6. Francesca Rossi

3.7. Thomas Schiex

3.8. Christian Schulte

3.9. Meinolf Sellmann

3.10. Mark Wallace

3.11. Toby Walsh

3.12. Roland Yap

3.13. References

Chapter 4. Constraint Propagation and Implementation

4.1. Filtering algorithms for precedence and dependency constraints (by Roman Barták and Ondřej Čepek)

4.2. A study of residual supports in arc consistency (by Christophe Lecoutre and Fred Hemery)

4.3. Maintaining singleton arc consistency (by Christophe Lecoutre and Patrick Prosser)

4.4. Probabilistic singleton arc consistency (by Deepak Mehta and Marc van Dongen)

4.5. Simplification and extension of the SPREAD constraint (by Pierre Schaus, Yves Deville, Pierre Dupont and Jean-Charles Régin)

4.6. A new filtering algorithm for the graph isomorphism problem (by Sébastien Sorlin and Christine Solnon)

4.7. References

Chapter 5. On the First SAT/CP Integration Workshop

5.1. The technical program

5.2. The panel session

5.3. Summary, future directions and conclusion

5.4. References

Chapter 6. Constraint-Based Methods for Bioinformatics

6.1. On using temporal logic with constraints to express biological properties of cell processes (by François Fages)

6.2. Modeling biological systems in stochastic concurrent constraint programming (by Luca Bortolussi and Alberto Policriti)

6.3. Chemera: constraints in protein structural problems (by Pedro Barahona and Ludwig Krippahl)

6.4. Exploiting model checking in constraint-based approaches to the protein folding problem (by Elisabetta De Maria, Agostino Dovier, Angelo Montanari and Carla Piazza)

6.5. Global constraints for discrete lattices (by Alessandro Dal Palù, Agostino Dovier and Enrico Pontelli)

6.6. Counting protein structures by DFS with dynamic decomposition (by Sebastian Will and Martin Mann)

6.7. Suffix array and weighted CSPs (by Matthias Zytnicki, Christine Gaspin and Thomas Schiex)

6.8. Supertree construction with constraint programming: recent progress and new challenges (by Patrick Prosser)

6.9. References

PART II. Constraint Modeling and Reformulation

Introduction

Chapter 7. Improved Models for Graceful Graphs

7.1. Introduction

7.2. A direct model

7.3. The edge-label model

7.4. A combined model

7.5. Experimental results

7.6. Discussion

7.7. References

Chapter 8. The Automatic Generation of Redundant Representations and Channeling Constraints

8.1. Introduction

8.2. Representations

8.3. Alternative representations and channels

8.4. Refinement

8.5. Systematic generation of channeling constraints

8.6. Producing the best alternative for channeling

8.7. Conclusions and future work

8.8. References

PART III. Symmetry in Constraint Satisfaction Problems

Introduction

Chapter 9. GAPLex: Generalized Static Symmetry Breaking

9.1. Background and introduction

9.2. GAPLex

9.3. Empirical evaluation

9.4. Conclusions and future work

9.5. References

Chapter 10. Symmetry Breaking in Subgraph Pattern Matching

10.1. Background and definitions

10.2. Variable symmetries

10.3. Value symmetries

10.4. Experimental results

10.5. Local value symmetries

10.6. Conclusion

10.7. References

PART IV. Interval Analysis, Constraint Propagation and Applications

Introduction

Chapter 11. Modeling and Solving of a Radio Antenna Deployment Support Application

Outline of the chapter

11.1. Two simple models for the application

11.2. Introducing the distn constraint

11.3. Modeling the application with the distn constraint

11.4. Conclusion

11.5. References

Chapter 12. Guaranteed Numerical Injectivity Test via Interval Analysis

12.1. Interval analysis

12.2. Injectivity

12.3. ITVIA algorithm

12.4. Examples

12.5. Conclusion

12.6. References

Chapter 13. An Interval-based Approximation Method for Discrete Changes in Hybrid cc

13.1. An overview of Hybrid cc

13.2. The objective of the chapter

13.3. Background of interval arithmetic

13.4. The proposed method

13.5. Experimental results

13.6. Related work

13.7. Conclusion

13.8. References

PART V. Local Search Techniques in Constraint Satisfaction

Introduction

Chapter 14. Combining Adaptive Noise and Look-Ahead in Local Search for SAT

14.1. Implementation of the adaptive noise mechanism in G2WSAT

14.2. Look-Ahead for promising decreasing variables

14.3. Evaluation

14.4. Conclusion

14.5. References

Chapter 15. Finding Large Cliques using SAT Local Search

15.1. SAT-encoding the clique problem

15.2. Notes on the bitwise at-most-one encoding

15.3. Experiments

15.4. Conclusion

15.5. References

Chapter 16. Multi-Point Constructive Search for Constraint Satisfaction: An Overview

16.1. Background

16.2. Empirical study

16.3. Conclusion

16.4. References

Chapter 17. Boosting SLS Using Resolution

17.1. SLS solvers

17.2. Preprocessors

17.3. Empirical evaluation

17.4. Conclusion

17.5. References

Chapter 18. Growing COMET

18.1. Constraint-based local search

18.2. COMET

18.3. Modeling

18.4. Search

18.5. References

PART VI. Preferences and Soft Constraints

Introduction

References

Chapter 19. The Logic Behind Weighted CSP

19.1. Preliminaries

19.2. The inference rule — soundness and completeness

19.3. Global consistency in WCSP

19.4. Local consistency in WCSP

19.5. Conclusions

19.6. References

Chapter 20. Dynamic Heuristics for Branch and Bound on Tree-Decomposition of Weighted CSPs

20.1. Introduction

20.2. Preliminaries

20.3. Dynamic orders in O(exp(w + 1))

20.4. Bounded extensions of dynamic orders

20.5. Heuristics

20.6. Experimental study

20.7. Discussion and conclusion

20.8. References

PART VII. Constraints in Software Testing, Verification and Analysis

Introduction

Chapter 21. Extending a CP Solver with Congruences as Domains for Program Verification

21.1. Related work

21.2. Congruences as domains

21.3. Propagation of congruences as domains

21.4. Cooperation of congruences and intervals

21.5. Conclusion

21.6. References

Chapter 22. Generating Random Values Using Binary Decision Diagrams and Convex Polyhedra

22.1. BDD and convex polyhedra

22.2. The resolution algorithm

22.3. Choosing solutions

22.4. Available tools

22.5. Related work

22.6. Conclusion

22.7. References

Chapter 23. A Symbolic Model for Hash-Collision Attacks

23.1. Terms and subterms

23.2. Analysis of reachability properties of cryptographic protocols

23.3. Model of a collision-aware intruder

23.4. Conclusion

23.5. References

Chapter 24. Strategy for Flaw Detection Based on a Service-driven Model for Group Protocols

24.1. Protocol modeling and attack search

24.2. Verification results

24.3. Summary and future work

24.4. References

PART VIII. Constraint Programming for Graphical Applications

Chapter 25. Trends and Issues in using Constraint Programming for Graphical Applications

25.1. More powerful constraint-solving techniques

25.2. Better modeling and understanding of constraint systems by the end-user

25.3. Bridging the gap between the solver and the application semantics

25.4. Conclusion

25.5. References

Chapter 26. A Constraint Satisfaction Framework for Visual Problem Solving

26.1. The framework

26.2. Applications

26.3. Conclusion

26.4. References

Chapter 27. Computer Graphics and Constraint Solving: An Application to Virtual Camera Control

27.1. Overview

27.2. A semantic space partitioning approach

27.3. Numerical solving stage

27.4. Exploitation of semantic volumes

27.5. Results

27.6. Discussion

27.7. References

Index

First published in Great Britain and the United States in 2007 by ISTE Ltd

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE LtdISTE USA6 Fitzroy Square4308 Patrice RoadLondon W1T 5DXNewport Beach, CA 92663UKUSA

www.iste.co.uk

© ISTE Ltd, 2007

The rights of Frédéric Benhamou, Narendra Jussien and Barry O’Sullivan to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Trends in constraint programming/edited by Frédéric Benhamou, Narendra Jussien, Barry O’Sullivan.

p. cm.

Includes index.

ISBN 978-1-905209-97-2

1. Constraint programming (Computer science) I. Benhamou, Frédéric. II. Jussien, Narendra. III. O’Sullivan, B. (Barry)

QA76.612.T74 2007

005.1'16--dc22

2007009430

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 13: 978-1-905-209-97-2

Introduction 1

Significant advances in computing power since the 1960s have led to a wealth of research on problem solving in fields such as operations research, numerical analysis, symbolic computing, scientific computing, artificial intelligence and programming languages. Constraint programming is a discipline that gathers, exploits and unifies ideas shared by all of these domains to tackle decision support problems.

Over the last 15 years, constraint programming has become a leading technology for modeling and solving real-life combinatorial problems. It has been successfully used in fields such as production planning, scheduling, timetabling, rostering, supply-chain management, product configuration, diagnosis, molecular biology, robotics, computer security and industrial process control. More-over, in many application domains it is the technology of choice for solving highly complex problems.

Constraint programming is essentially a declarative paradigm: once the problem has been modeled as a constraint satisfaction problem, a constraint solver calculates a solution for it. The behavior of a constraint solver is guided by a strict separation of concerns, in which individual constraints are responsible for pruning the search space. It is the interaction between these individual behaviors that leads to an efficient search procedure by exploiting sophisticated search space exploration techniques and heuristics.

While the principles behind constraint programming are simple, its practical application can be quite complex. Real life problems are often computationally intractable, so intelligent algorithms and heuristics appropriate to the application domain being considered must be used. In addition, the ideal of fully declarative problem formulation that ensures an efficient search process has not yet been achieved. Constraint programming is therefore an active academic field of research: many research papers are presented not only in constraint programming conferences and journals but also within artificial intelligence and operations research fora.

This book presents trends in the field of constraint programming that not only try to improve the efficiency and utility of constraint-based methods, but also present a variety of important emerging application domains for constraint programming.

Purpose of this book

The International Conference on the Principles and Practice of Constraint Programming (CP) is the premier annual meeting dedicated to developments in the field of constraint programming. It is concerned with all aspects of computing with constraints, including algorithms, applications, environments, languages, models, and systems. Constraint programming is an ever-evolving field and each year the set of workshops that run alongside the conference represent the ongoing trends of the field. Very interesting insights, concepts and results are presented during these workshops.

The objective of this book is to complement the CP 2006 conference proceedings with a volume that reflects the current trends in the field as reflected by the workshop program, and collects these in a thematic way to provide a broad perspective on what is currently being studied in these areas. The organizers of each workshop have contributed either a single chapter reflecting the broad trends within the topic of their workshop, or a collection of short chapters presenting condensed versions of key contributions accompanied with an editorial comment.

The intended audience of this book comprises researchers and practitioners interested in all aspects of constraint programming. Research students should find the book useful as a guide to the topics that are considered to be at the cutting edge of constraint programming research.

Organization of the book

The book is organized into eight parts. Part I focuses on the past, present and future of constraint programming. This is the largest part of the book, comprising six chapters.

Chapter 1 is a transcript of a talk that Pascal Van Hentenryck delivered at CP 2006 when he was awarded the Association for Constraint Programming’s Research Excellence Award. The chapter presents the experiences of one of CP’s top researchers as he was involved in the development of a series of influential constraint programming systems.

Chapter 2 presents a synthesis of the first CP-Tools workshop, which collected together a variety of constraint programming systems, both commercial and non-commercial. The chapter also reports on two panel discussions: one focusing on technical awareness issues, the other considering future directions for the development of CP systems.

Chapter 3 presents a synthesis of the discussions held as part of the workshop on the subject of “The Next 10 Years of Constraint Programming”. During this workshop, over 120 people participated in breakout discussions; each breakout group was chaired by a discussion leader who acted as a facilitator of the discussion. This chapter compiles reports of the major points raised during this event summarized by these discussion leaders.

The remainder of Part I presents chapters that reflect trends in constraint propagation and implementation (Chapter 4), a major component of all constraint reasoning tasks; a chapter on the relationships between satisfiability and constraint programming (Chapter 5); and finally, a chapter on trends in bioinformatics and constraint programming (Chapter 6).

Fundamental issues in constraint programming are addressed in Parts II-IV, each part presenting a collection of papers from three workshops: modeling and reformulation, symmetry breaking, and interval constraint reasoning. The chapters on modeling and reformulation (Part II) address different aspects of the importance of modeling in constraint programming. Other complex issues associated with the constraint modeling problem arise when symmetries are present in the problem being solved. This issue is discussed in detail in Part III. Of course, not all constraint models are specified using finite domains. In Part IV we are given a flavor of the depth and rigor associated with continuous constraint modeling and solving.

Part V presents a selection of papers from the workshop on local search techniques in constraint programming. Local search, while incomplete, has been shown to be a key approach to problem solving that has the capability to tackle real-life problems that are too large for systematic solvers. The development of new local search algorithms continues to provide a very rich and practical domain for cutting-edge constraint programming research.

The importance of reasoning about preferences and soft constraints is considered in Part VI. Solving constraint satisfaction problems involving costs continues to be a very important and productive area of research, as reflected in the introduction to this part.

The two final parts of the book (Parts VII and VIII) focus on two important application domains for constraint programming: software verification, testing and analysis, and graphical applications, respectively. Software verification, testing and analysis is becoming more important with the emergence of safety critical systems and the high level of investment in the development of complex technical systems. Graphical applications provide a rich domain for exploiting constraints technology since it brings together human-computer interaction, visual problem solving, and hybrid finite and infinite domain constraint systems. Even though graphical applications of constraints date back to the 1960s, there remain significant challenges in this area.

Acknowledgements

This book would not have been possible without the coordinated efforts of many people. Firstly, we would like to express our thanks to the organizers of each of the CP 2006 workshops, all of whom participated in this project. Secondly, we would like to thank the individual authors of each of the parts, chapters and chapter sections. It is their scientific contributions to the future of constraint programming that we have set out to show-case in this book. Thirdly, the individual workshops would not have been possible without their hard working programme committees, who enabled the peer-review process that ensures scientific excellence.

Finally, we would like to record a very special mention of two special events that took place during the CP 2006 conference: the workshop on CP-Tools and the workshop on “The Next 10 Years of Constraint Programming”. These events enabled the industrial and research communities of constraints researchers and users to come together and take stock of what has been achieved by the community over the last decade, and to reflect upon where our community needs to go over the next 10 years. It was clear from the attendance at both events that these were welcomed and highly regarded.

Contributors

Anbulagan, L&C/NICTA and CSL/ANU, Australia; Carlos Ansótegui, DIEI, University of Lleida, Spain; Bonny Banerjee, Computer Sc. & Eng., Ohio State Univ, USA; Pedro Barahona, Universidade Nova de Lisboa, Portugal; Roman Barták, Charles University, Czech Republic; J. Christopher Beck, University of Toronto, Canada; Frédéric Benhamou, LINA/University of Nantes, France; Bruno Berstel, ILOG, MPI, France; Christian Bessiere, LIRMM/CNRS, France; Benjamin Blanc, CEA/LIST, France; Maria L. Bonet, LSI, Universitat Politècnica de Catalunya, Spain; Lucas Bordeaux, Microsoft Research, UK; Ondřej Čepek, Charles University and Institute of Finance and Administration, Czech Republic; B. Chandrasekaran, Computer Sc. & Eng., Ohio State Univ, USA; Yannick Chevalier, IRIT, France; Najah Chridi, LORIA-UHP, France; Marc Christie, LINA/University of Nantes, France; Alessandro Dal Palù, Univ. Parma, Matematica, Italy; Nicolas Delanoue, ISTIA/LISA, France; Yves Deville, UCLouvain, Belgium; Alastair Donaldson, University of Glasgow, UK; Agostino Dovier, Univ. Udine, DIMI, Italy; Pierre Dupont, UCLouvain, Belgium; François Fages, INRIA Rocquencourt, France; Alan M. Frisch, University of York, UK; Ian Gent, University of St. Andrews, UK; Arnaud Gotlieb, IRISA/INRIA, France; Peter Gregory, University of Strathclyde, UK; Youssef Hamadi, Microsoft Research, UK; Ivan Heckman, University of Toronto, Canada; Fred Hemery, CRIL, France; Michael Heusch, LINA/University of Nantes, France Hiroshi Hosobe, NII, Japan; Daisuke Ishii, Waseda University, Japan; Erwan Jahier, CNRS/VERIMAG, France; Luc Jaulin, ENSIETA/E3I2, France; Peter Jeavons, Oxford University Computing Laboratory, UK; Chris Jefferson, Oxford University, UK; Philippe Jégou, LSIS / UPCAM 3, France; Christophe Jermann, LINA/University of Nantes, France; Narendra Jussien, EMN/LINA, France; Tom Kelsey, University of St. Andrews, UK; Mounira Kourjieh, IRIT, France; Sébastien Lagrange, ISTIA/LISA, France; Michel Leconte, ILOG, France; Christophe Lecoutre CRIL, France; Jordi Levy, IIIA, CSIC, Spain; Chu Min Li, LaRIA — University of Picardie Jules Verne, France; Steve Linton, University of St. Andrews, UK; Felip Manyà, DIEI, University of Lleida, Spain; Joao Marques-Silva, University of Southampton, UK; Kim Marriott, Monash University, Australia; Bernadette Martínez-Hernández, University of York, UK; Pedro Meseguer, IIIA/CSIC, Spain; Deepak Mehta, University College Cork, Ireland; Claude Michel, I3S (UNSA/CNRS), France; Laurent Michel, CSE, University of Connecticut, USA; Ian Miguel, University of St Andrews, UK; Yehuda Naveh, IBM Haifa Research Lab, Israel; Samba Ndojh Ndiaye, LSIS/UPCAM 3, France; Robert Nieuwenhuis, Technical University of Catalonia, Spain; Jean-Marie Normand, LINA/University of Nantes, France; Barry O’Sullivan, 4C 2013 University College Cork, Ireland; Gilles Pesant, Polytechnique Montréal, Canada; Karen Petrie, Oxford University, UK; Duc Nghia Pham, SAFE/NICTA, Australia; Steve Prestwich, 4C — University College Cork, Ireland; Patrick Prosser, Glasgow University, UK; Jean-François Puget, ILOG, France; Pascal Raymond, CNRS/VERIMAG, France; Jean-Charles Régin, ILOG, Sophia-Antipolis, France; Andrea Roli, DEIS 2013 Univeristy of Bologna, Italy; Francesca Rossi, University of Padua, Italy; Abdul Sattar, SAFE/NICTA and IIIS/Griffith University, Australia; Pierre Schaus, UCLouvain, Belgium; Thomas Schiex, INRA Toulouse, France; Christian Schulte, KTH/ICT/ECS, Sweden; Meinolf Sellmann, Brown University, USA; John Slaney, L&C NICTA and CSL/ANU, Australia; Barbara M. Smith, 4C — University College Cork, Ireland; Christine Solnon, LIRIS, France; Sébastien Sorlin, LIRIS, France; Peter Stuckey, University of Melbourne, Australia; Cyril Terrioux, LSIS / UPCAM 3, France; Kazunori Ueda, Waseda University, Japan; M.R.C. Van Dongen, University College Cork, Ireland; Pascal Van Hentenryck, Brown University, USA; Laurent Vigneron, LORIA-UN2, France; Mark Wallace, Monash University, Australia; Toby Walsh, NICTA — University of New South Wales, Australia; Wanxia Wei, University of New Brunswick, Canada; Sebastian Will, ALU Freiburg, Bioinformatics, Germany; Roland Yap, National University of Singapore, Singapore; Stéphane Zampelli, UCLouvain, Belgium; Harry Zhang, University of New Brunswick, Canada.

1 Introduction written by Frédéric BENHAMOU, Narendra JUSSIEN and Barry O’SULLIVAN.

PART I

The Past, Present and Future of Constraint Programming

Edited by Frédéric BENHAMOU, Narendra JUSSIEN and Barry O’SULLIVAN

Chapter 1

Constraint Programming as Declarative Algorithmics1

It is a great honor to receive the second ACP award for research excellence in constraint programming. It is also a humbling experience as I reflect how lucky I have been to meet and work with so many talented people at many stages in my career. As William E. Woodward said, “in the queer mess of human destiny the determining factor is luck. For every important place in life, there are many men of fairly equal capacities. Among them, luck divides who shall accomplish the great work, who shall be crowned with laurel, and who should fall back in obscurity and silence”. Jean-Charles Régin expressed it a bit more bluntly when he once told me: “everything you did would have been contributed by someone else anyway.” It is obvious that I have been fortunate to be at the right place at the right time many times.

I became interested in research in Brittany. The University of Namur in Belgium had the excellent practice of sending students in their final year abroad for about 4 months. I went to the center for telecommunications (CNET) in Lannion to study software engineering. After two months, my fellow students and I had nothing left to work on, so we started looking for other opportunities in the center. I was told that there were two great researchers I should consider, one in concurrent programming and one in logic programming. Concurrent programming sounded more interesting so I went knocking at the door of this fellow several days in a row without success. I gave up and met Mehmet Dincbas the next day. Mehmet gave me papers and books to read, suggested all kinds of programming projects in logic programming, answered all my questions (and there were many) and spent considerable time explaining to me the grand challenges and the folklore of logic programming. As I was about to leave, he told me that he was joining Hervé Gallaire at the European Computer-Industry Research Centre (ECRC) and he asked me whether I was interested in coming along. I became the first PhD student at ECRC in August 1985 where I spent about 4.5 years on the CHIP project. I then joined Brown University in 1990 where I was recruited by Paris Kanellakis. I also had the opportunity to spend time at the University of Marseilles, at MIT, and at the University of Louvain, and to collaborate with Ilog.

In this chapter, I would like to reflect on some of the lessons I have learned in the last 20 years and to illustrate them using several research projects. These lessons are:

1) Find the missing link;

2) Build systems;

3) Be driven by applications;

4) Just do it; then clean up the mess;

5) Strive for the declarative ideal;

6) Find great people to work with.

I do not claim that these lessons are universal. I found them useful for the kind of research I engage in. I also did not invent them. I often learned them the hard way, but I keep coming back to them whenever I come down with the research blues. Finally, they are heavily influenced by the research vision promoted by Hervé Gallaire at ECRC.