logo资料库

Handbook of Constraint Programming.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：14.79M 资料格式：pdf 举报 版权申诉
第1页 / 共977页
第2页 / 共977页
第3页 / 共977页
第4页 / 共977页
第5页 / 共977页
第6页 / 共977页
第7页 / 共977页
第8页 / 共977页
资料共977页，剩余部分请下载后查看
    Title Page
    Copyright Page
    Foreword
    Editors
    Contributors
    Contents
    Part I: Foundations
    Chapter 1 Introduction
    1.1 Purpose of the Handbook
    1.2 Structure and Content
    1.3 Future Research
    Chapter 2 Constraint Satisfaction: An Emerging Paradigm
    2.1 The Early Days
    2.2 The Constraint Satisfaction Problem: Representation and Reasoning
    2.3 Conclusions
    Chapter 3 Constraint Propagation
    3.1 Background
    3.2 Formal Viewpoint
    3.3 Arc Consistency
    3.4 Higher Order Consistencies
    3.5 Domain-Based Consistencies Stronger than AC
    3.6 Domain-Based Consistencies Weaker than AC
    3.7 Constraint Propagation as Iteration of Reduction Rules
    3.8 Specific Constraints
    Chapter 4 Backtracking Search Algorithms
    4.1 Preliminaries
    4.2 Branching Strategies
    4.3 Constraint Propagation
    4.4 Nogood Recording
    4.5 Non-Chronological Backtracking
    4.6 Heuristics for Backtracking Algorithms
    4.7 Randomization and Restart Strategies
    4.8 Best-First Search
    4.9 Optimization
    4.10 Comparing Backtracking Algorithms
    Chapter 5 Local Search Methods
    5.1 Introduction
    5.2 Randomised Iterative Improvement Algorithms
    5.3 Tabu Search and Related Algorithms
    5.4 Penalty-Based Local Search Algorithms
    5.5 Other Approaches
    5.6 Local Search for Constraint Optimisation Problems
    5.7 Frameworks and Toolkits for Local Search
    5.8 Conclusions and Outlook
    Chapter 6 Global Constraints
    6.1 Notation and Preliminaries
    6.2 Examples of Global Constraints
    6.3 Complete Filtering Algorithms
    6.4 Optimization Constraints
    6.5 Partial Filtering Algorithms
    6.6 Global Variables
    6.7 Conclusion
    Chapter 7 Tractable Structures for Constraint Satisfaction Problems
    7.1 Background
    7.2 Structure-Based Tractability in Inference
    7.3 Trading Time and Space by Hybrids of Search and Inference
    7.4 Structure-Based Tractability in Search
    7.5 Summary and Bibliographical Notes
    Chapter 8 The Complexity of Constraint Languages
    8.1 Basic Definitions
    8.2 Examples of Constraint Languages
    8.3 Developing an Algebraic Theory
    8.4 Applications of the Algebraic Theory
    8.5 Constraint Languages Over an Infinite Set
    8.6 Multi-Sorted Constraint Languages
    8.7 Alternative Approaches
    8.8 Future Directions
    Chapter 9 Soft Constraints
    9.1 Background: Classical Constraints
    9.2 Specific Frameworks
    9.3 Generic Frameworks
    9.4 Relations among Soft Constraint Frameworks
    9.5 Search
    9.6 Inference
    9.7 Combining Search and Inference
    9.8 Using Soft Constraints
    9.9 Promising Directions for Further Research
    Chapter 10 Symmetry in Constraint Programming
    10.1 Symmetries and Group Theory
    10.2 Definitions
    10.3 Reformulation
    10.4 Adding Constraints Before Search
    10.5 Dynamic Symmetry Breaking Methods
    10.6 Combinations of Symmetry Breaking Methods
    10.7 Successful Applications
    10.8 Symmetry Expression and Detection
    10.9 Further Research Themes
    10.10 Conclusions
    Chapter 11 Modelling
    11.1 Preliminaries
    11.2 Representing a Problem
    11.3 Propagation and Search
    11.4 Viewpoints
    11.5 Expressing the Constraints
    11.6 Auxiliary Variables
    11.7 Implied Constraints
    11.8 Reformulations of CSPs
    11.9 Combining Viewpoints
    11.10 Symmetry and Modelling
    11.11 Optimization Problems
    11.12 Supporting Modelling and Reformulation
    Part II: Extensions, Languages, and Applications
    Chapter 12 Constraint Logic Programming
    12.1 History of CLP
    12.2 Semantics of Constraint Logic Programs
    12.3 CLP for Conceptual Modeling
    12.4 CLP for Design Modeling
    12.5 Search in CLP
    12.6 Impact of CLP
    12.7 Future of CLP and Interesting Research Questions
    Chapter 13 Constraints in Procedural and Concurrent Languages
    13.1 Procedural and Object-Oriented Languages
    13.2 Concurrent Constraint Programming
    13.3 Rule-Based Languages
    13.4 Challenges and Opportunities
    13.5 Conclusion
    Chapter 14 Finite Domain Constraint Programming Systems
    14.1 Architecture for Constraint Programming Systems
    14.2 Implementing Constraint Propagation
    14.3 Implementing Search
    14.4 Systems Overview
    14.5 Outlook
    Chapter 15 Operations Research Methods in Constraint Programming
    15.1 Schemes for Incorporating OR into CP
    15.2 Plan of the Chapter
    15.3 Linear Programming
    15.4 Mixed Integer/Linear Modeling
    15.5 Cutting Planes
    15.6 Relaxation of Global Constraints
    15.7 Relaxation of Piecewise Linear and Disjunctive Constraints
    15.8 Lagrangean Relaxation
    15.9 Dynamic Programming
    15.10 Branch-and-Price Methods
    15.11 Benders Decomposition
    15.12 Toward Integration of CP and OR
    Chapter 16 Continuous and Interval Constraints
    16.1 From Discrete to Continuous Constraints
    16.2 The Branch-and-Reduce Framework
    16.3 Consistency Techniques
    16.4 Numerical Operators
    16.5 Hybrid Techniques
    16.6 First Order Constraints
    16.7 Applications and Software packages
    16.8 Conclusion
    Chapter 17 Constraints over Structured Domains
    17.1 History and Applications
    17.2 Constraints over Regular and Constructed Sets
    17.3 Constraints over Finite Set Intervals
    17.4 Influential Extensions to Subset Bound Solvers
    17.5 Constraints over Maps, Relations and Graphs
    17.6 Constraints over Lattices and Hierarchical Trees
    17.7 Implementation Aspects
    17.8 Applications
    17.9 Further Topics
    Chapter 18 Randomness and Structure
    18.1 Random Constraint Satisfaction
    18.2 Random Satisfiability
    18.3 Random Problems with Structure
    18.4 Runtime Variability
    18.5 History
    18.6 Conclusions
    Chapter 19 Temporal CSPs
    19.1 Preliminaries
    19.2 Constraint-Based Formalisms for Reasoning About Time
    19.3 Efficient Algorithms for Temporal CSPs
    19.4 More Expressive Queries for Temporal CSPs
    19.5 First-Order Temporal Constraint Languages
    19.6 The Scheme of Indefinite Constraint Databases
    19.7 Conclusions
    Chapter 20 Distributed Constraint Programming
    20.1 Definitions
    20.2 Distributed Search
    20.3 Improvements and Variants
    20.4 Distributed Local Search
    20.5 Open Constraint Programming
    20.6 Further Issues
    20.7 Conclusion
    Chapter 21 Uncertainty and Change
    21.1 Background and Definitions
    21.2 Example: Course Scheduling
    21.3 Uncertain Problems
    21.4 Problems that Change
    21.5 Pseudo-dynamic Formalisms
    21.6 Challenges and Future Trends
    21.7 Summary
    Chapter 22 Constraint-Based Scheduling and Planning
    22.1 Constraint Programming Models for Scheduling
    22.2 Constraint Programming Models for Planning
    22.3 Constraint Propagation for Resource Constraints
    22.4 Constraint Propagation on Optimization Criteria
    22.5 Heuristic Search
    22.6 Conclusions
    Chapter 23 Vehicle Routing
    23.1 The Vehicle Routing Problem
    23.2 Operations Research Approaches
    23.3 Constraint Programming Approaches
    23.4 Constraint Programming in Search
    23.5 Using Constraint Programming as a Subproblem Solver
    23.6 CP-VRP in the Real World
    23.7 Conclusions
    Chapter 24 Configuration
    24.1 What Is Configuration?
    24.2 Configuration Knowledge
    24.3 Constraint Models for Configuration
    24.4 Problem Solving for Configuration
    24.5 Conclusion
    Chapter 25 Constraint Applications in Networks
    25.1 Electricity Networks
    25.2 Water (Oil) Networks
    25.3 Data Networks
    25.4 Conclusion
    Chapter 26 Bioinformatics and Constraints
    26.1 What Biologists Want from Bioinformatics
    26.2 The Central Dogma
    26.3 A Classification of Problem Areas
    26.4 Sequence Related Problems
    26.5 Structure Related Problems
    26.6 Function Related Problems
    26.7 Microarrays
    Index
    FOUNDATIONS OF ARTIFICIAL INTELLIGENCE
    Foundations of Artificial Intelligence Series Editors J. Hendler H. Kitano B. Nebel Cover picture by Helmut Simonis AMSTERDAM–BOSTON–HEIDELBERG–LONDON–NEW YORK–OXFORD ELSEVIER PARIS–SAN DIEGO–SAN FRANCISCO–SINGAPORE–SYDNEY–TOKYO
    Handbook of Constraint Programming Edited by Francesca Rossi University of Padova Italy Peter van Beek University of Waterloo Canada Toby Walsh National ICTA Australia & University of New South Wales Australia AMSTERDAM–BOSTON–HEIDELBERG–LONDON–NEW YORK–OXFORD ELSEVIER PARIS–SAN DIEGO–SAN FRANCISCO–SINGAPORE–SYDNEY–TOKYO
    Elsevier Radarweg 29, PO Box 211, 1000 AE Amsterdam, The Netherlands The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, UK First edition 2006 Copyright © 2006 Elsevier B.V. All rights reserved No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means electronic, mechanical, photocopying, recording or otherwise without the prior written permission of the publisher Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone (+44) (0) 1865 843830; fax (+44) (0) 1865 853333; email: permissions@elsevier.com. Alternatively you can submit your request online by visiting the Elsevier web site at http://elsevier.com/locate/permissions, and selecting Obtaining permission to use Elsevier material Notice No responsibility is assumed by the publisher for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions or ideas contained in the material herein. Because of rapid advances in the medical sciences, in particular, independent verification of diagnoses and drug dosages should be made Library of Congress Cataloging-in-Publication Data A catalog record for this book is available from the Library of Congress British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library ISBN-13: 978-0-444-52726-4 ISBN-10: 0-444-52726-5 ISSN: 1574-6525 For information on all Elsevier publications visit our website at books.elsevier.com Printed and bound in The Netherlands 06 07 08 09 10 10 9 8 7 6 5 4 3 2 1
    Foreword Constraints are an ubiquitous concept, which in its broader sense pertains to every day experience: they represent the conditions which restrict our freedom of decision. In fact, how much our choices are constrained by the external world is a basic philosophical ques- tion. In the formalized reasoning of scientific disciplines, constraints have been employed extensively, from logic to numerical analysis, from mathematical programming to opera- tions research. In computer science, constraints have been with us from the early days, for modeling, representing and reasoning (see the interesting historical remarks in Chapter 2 of this handbook, Constraint Satisfaction: An Emerging Paradigm). I see several good reasons for this ubiquity: one is the conceptually clear separation between the perfectly declarative problem statements and the often cumbersome enumera- tive efforts for finding solutions. Another reason is the complexity challenge: the classical constraint satisfaction problem is NP-complete and in fact tautology checking in propo- sitional calculus (a constraint problem on Boolean variables) has been the touchstone for this complexity class. A further reason is that large, complex constraint problems often occur in practice, they must be solved in one way or another, and fast, efficient, systematic solutions have an enormous economic value. What I find surprising about constraints is that within artificial intelligence and com- puter science a relatively recent, relatively uniform body of knowledge has emerged which often yields decisive advantages over classical, extensively studied and well developed techniques. As for many success stories within computer science, success is largely due to a mixture of structures, algorithms, languages, programming techniques and system im- plementations. The aim of this handbook is to present this knowledge in all its facets. Different chapters are largely self contained and all contribute to put the subject into focus, similarly to the Hawaii Keck observatory, where the mirror is composed of 36 hexagonal segments. From the conceptual point of view, the main characteristic features of constraint pro- gramming are constraint propagation, and the identification of various special cases which make complexity tractable. The former (see Chapter 3) is an inference technique which makes local constraints stronger without changing the global constraint. The latter issue concerns both the structure (see Chapter 7, Tractable Structures for Constraint Satisfaction Problems) and the kind of constraints (see Chapter 8, The Complexity of Constraint Lan- guages). Less specific, but still very important issues are as follows: Backtracking Search Algorithms, in Chapter 4; Local Search, in Chapter 5; Global Constraints, in Chapter 6; Symmetry in Constraint Programming, in Chapter 10; and Modelling, in Chapter 11. Another surprising fact about constraint theory is the incredibly close relationship with logic programming. In a rather precise sense logic programming is a way of expressing, and solving, certain classes of disjunctive, recursive constraints. Furthermore, logic pro- gramming can be very elegantly generalized to constraint logic programming (see Chapter v
    vi Foreword 12), where the ordinary Herbrand constraint system, and its unification algorithm, are com- plemented with specific constraint solvers. The interaction with the committed choice lan- guages studied in the Japanese projects of the eighties also yielded very interesting models of computation based on constraints. Amalgamation with more common (and efficiently implemented!) programming languages is also possible (see Chapter 13, Constraints in Procedural and Concurrent Languages). Besides and beyond the beauty of its theoretical foundations, what contributes the most to the practical convenience of constraint programming are: (i) the development of specific results for important classes of constraints; (ii) the ability of extending the basic theory to various additional aspects which are very relevant in practice; and (iii) the flexibility and potential for integration with other modeling and solving methodologies. About the development of specific results, this handbook includes chapters about con- straints on finite (Chapter 14), structured (Chapter 17), temporal (Chapter 19), continuous and interval-based (Chapter 16) domains. The potential to extend the basic theory in evi- dent in the case of soft constraints, considered in Chapter 9. Ordinary constraints are either satisfied or not, namely either true or false. Instead soft constraints return a more infor- mative weight. Interestingly enough, the proposed extensions both accommodate several important cases (fuzzy, hierarchical, optimization, probabilistic constraints), and still of- ten exhibit essentially the same solution algorithms. Extensions to random, changing and distributed/open constraints are treated in Chapters 18, 21 and 20 respectively. About the last issue, in addition to the seamless integration with logic and imperative programming languages we mentioned already, quite remarkable are the paradigms result- ing from the integration of constraint programming with operations research (see Chapter 15), with scheduling and planning (see Chapter 22), with vehicle routing (see Chapter 23), with component configuration (see Chapter 24), with (electricity, water, oil, data) networks (see Chapter 25), and with bioinformatics (see Chapter 26). The global scenario based on service-oriented computing which is now under devel- opment offers additional theoretical and practical challenges to constraint programming. Conditions for service deployment and discovery, both functional and involving different aspects of quality of service, could be expressed in terms of hard and soft constraints, and the negotiation phases should involve substantial constraint solving abilities. Transactions among the various actors could also require partially backtrackable behavior or at least programmable compensations. Some level of real time, distributed, global constraint solv- ing should be implemented in the middleware, since lots of higher level applications will be able to take advantage of, and pay for it. I think that research and practical development in the area of constraint programming will be very active for quite a while in the future, establishing closer and closer connections with a variety of other design methodologies and even other disciplines. I consider this handbook not only a very nice piece of scientific work, but also a contribution quite instru- mental at disseminating advanced knowledge about constraint programming both within the inner constraint community and across the much wider audience of potential users. UGO MONTANARI Dipartimento di Informatica Universit`a di Pisa, Italy
    Editors Francesca Rossi University of Padova Italy Peter van Beek University of Waterloo Canada Toby Walsh National ICT Australia & University of New South Wales Australia vii
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料