HANDBOOK OF CONSTRAINT PROGRAMMING
CONTENTS I FOUNDATIONS INTRODUCTION PURPOSE OF THE HANDBOOK STRUCTURE AND CONTENT FUTURE RESEARCH CONSTRAINT SATISFACTION: AN EMERGING PARADIGM THE EARLY DAYS THE CONSTRAINT SATISFACTION PROBLEM: REPRESENTATION AND REASONING CONCLUSIONS CONSTRAINT PROPAGATION BACKGROUND FORMAL VIEWPOINT ARC CONSISTENCY HIGHER ORDER CONSISTENCIES DOMAIN-BASED CONSISTENCIES STRONGER THAN AC DOMAIN-BASED CONSISTENCIES WEAKER THAN AC CONSTRAINT PROPAGATION AS ITERATION OF REDUCTION RULES SPECI?C CONSTRAINTS BACKTRACKING SEARCH ALGORITHMS PRELIMINARIES BRANCHING STRATEGIES NOGOOD RECORDING NON-CHRONOLOGICAL BACKTRACKING HEURISTICS FOR BACKTRACKING ALGORITHMS RANDOMIZATION AND RESTART STRATEGIES BEST-FIRST SEARCH OPTIMIZATION COMPARING BACKTRACKING ALGORITHMS LOCAL SEARCH METHODS RANDOMISED ITERATIVE IMPROVEMENT ALGORITHMS TABU SEARCH AND RELATED ALGORITHMS PENALTY-BASED LOCAL SEARCH ALGORITHMS OTHER APPROACHES LOCAL SEARCH FOR CONSTRAINT OPTIMISATION PROBLEMS FRAMEWORKS AND TOOLKITS FOR LOCAL SEARCH CONCLUSIONS AND OUTLOOK GLOBAL CONSTRAINTS NOTATION AND PRELIMINARIES EXAMPLES OF GLOBAL CONSTRAINTS COMPLETE FILTERING ALGORITHMS OPTIMIZATION CONSTRAINTS PARTIAL FILTERING ALGORITHMS GLOBAL VARIABLES CONCLUSION TRACTABLE STRUCTURES FOR CONSTRAINT SATISFACTION PROBLEMS STRUCTURE-BASED TRACTABILITY IN INFERENCE TRADING TIME AND SPACE BY HYBRIDS OF SEARCH AND INFERENCE STRUCTURE-BASED TRACTABILITY IN SEARCH SUMMARY AND BIBLIOGRAPHICAL NOTES THE COMPLEXITY OF CONSTRAINT LANGUAGES BASIC DE?NITIONS EXAMPLES OF CONSTRAINT LANGUAGES DEVELOPING AN ALGEBRAIC THEORY APPLICATIONS OF THE ALGEBRAIC THEORY CONSTRAINT LANGUAGES OVER AN IN?NITE SET MULTI-SORTED CONSTRAINT LANGUAGES ALTERNATIVE APPROACHES FUTURE DIRECTIONS SOFT CONSTRAINTS BACKGROUND: CLASSICAL CONSTRAINTS SPECI?C FRAMEWORKS GENERIC FRAMEWORKS RELATIONS AMONG SOFT CONSTRAINT FRAMEWORKS SEARCH INFERENCE COMBINING SEARCH AND INFERENCE USING SOFT CONSTRAINTS PROMISING DIRECTIONS FOR FURTHER RESEARCH 10 SYMMETRY IN CONSTRAINT PROGRAMMING SYMMETRIES AND GROUP THEORY DE?NITIONS REFORMULATION ADDING CONSTRAINTS BEFORE SEARCH DYNAMIC SYMMETRY BREAKING METHODS COMBINATIONS OF SYMMETRY BREAKING METHODS SUCCESSFUL APPLICATIONS SYMMETRY EXPRESSION AND DETECTION FURTHER RESEARCH THEMES 1010 CONCLUSIONS 11 MODELLING REPRESENTING A PROBLEM PROPAGATION AND SEARCH VIEWPOINTS EXPRESSING THE CONSTRAINTS AUXILIARY VARIABLES IMPLIED CONSTRAINTS REFORMULATIONS OF CSPS COMBINING VIEWPOINTS 1110 SYMMETRY AND MODELLING 1111 OPTIMIZATION PROBLEMS 1112 SUPPORTING MODELLING AND REFORMULATION II EXTENSIONS, LANGUAGES, AND APPLICATIONS 12 CONSTRAINT LOGIC PROGRAMMING HISTORY OF CLP SEMANTICS OF CONSTRAINT LOGIC PROGRAMS CLP FOR CONCEPTUAL MODELING CLP FOR DESIGN MODELING SEARCH IN CLP IMPACT OF CLP FUTURE OF CLP AND INTERESTING RESEARCH QUESTIONS 13 CONSTRAINTS IN PROCEDURAL AND CONCURRENT LANGUAGES PROCEDURAL AND OBJECT-ORIENTED LANGUAGES CONCURRENT CONSTRAINT PROGRAMMING RULE-BASED LANGUAGES CHALLENGES AND OPPORTUNITIES 14 FINITE DOMAIN CONSTRAINT PROGRAMMING SYSTEMS ARCHITECTURE FOR CONSTRAINT PROGRAMMING SYSTEMS IMPLEMENTING CONSTRAINT PROPAGATION IMPLEMENTING SEARCH SYSTEMS OVERVIEW OUTLOOK 15 OPERATIONS RESEARCH METHODS IN CONSTRAINT PROGRAMMING SCHEMES FOR INCORPORATING OR INTO CP PLAN OF THE CHAPTER LINEAR PROGRAMMING MIXED INTEGER/LINEAR MODELING CUTTING PLANES RELAXATION OF GLOBAL CONSTRAINTS RELAXATION OF PIECEWISE LINEAR AND DISJUNCTIVE CONSTRAINTS LAGRANGEAN RELAXATION DYNAMIC PROGRAMMING 1510 BRANCH-AND-PRICE METHODS 1511 BENDERS DECOMPOSITION 1512 TOWARD INTEGRATION OF CP AND OR 16 CONTINUOUS AND INTERVAL CONSTRAINTS FROM DISCRETE TO CONTINUOUS CONSTRAINTS THE BRANCH-AND-REDUCE FRAMEWORK CONSISTENCY TECHNIQUES NUMERICAL OPERATORS HYBRID TECHNIQUES FIRST ORDER CONSTRAINTS APPLICATIONS AND SOFTWARE PACKAGES 17 CONSTRAINTS OVER STRUCTURED DOMAINS HISTORY AND APPLICATIONS CONSTRAINTS OVER REGULAR AND CONSTRUCTED SETS CONSTRAINTS OVER FINITE SET INTERVALS IN?UENTIAL EXTENSIONS TO SUBSET BOUND SOLVERS CONSTRAINTS OVER MAPS, RELATIONS AND GRAPHS CONSTRAINTS OVER LATTICES AND HIERARCHICAL TREES IMPLEMENTATION ASPECTS APPLICATIONS FURTHER TOPICS 18 RANDOMNESS AND STRUCTURE RANDOM CONSTRAINT SATISFACTION RANDOM SATIS?ABILITY RANDOM PROBLEMS WITH STRUCTURE RUNTIME VARIABILITY HISTORY 19 TEMPORAL CSPS CONSTRAINT-BASED FORMALISMS FOR REASONING ABOUT TIME EF?CIENT ALGORITHMS FOR TEMPORAL CSPS MORE EXPRESSIVE QUERIES FOR TEMPORAL CSPS FIRST-ORDER TEMPORAL CONSTRAINT LANGUAGES THE SCHEME OF INDE?NITE CONSTRAINT DATABASES 20 DISTRIBUTED CONSTRAINT PROGRAMMING DISTRIBUTED SEARCH IMPROVEMENTS AND VARIANTS DISTRIBUTED LOCAL SEARCH OPEN CONSTRAINT PROGRAMMING FURTHER ISSUES 21 UNCERTAINTY AND CHANGE BACKGROUND AND DE?NITIONS EXAMPLE: COURSE SCHEDULING UNCERTAIN PROBLEMS PROBLEMS THAT CHANGE PSEUDO-DYNAMIC FORMALISMS CHALLENGES AND FUTURE TRENDS SUMMARY 22 CONSTRAINT-BASED SCHEDULING AND PLANNING CONSTRAINT PROGRAMMING MODELS FOR SCHEDULING CONSTRAINT PROGRAMMING MODELS FOR PLANNING CONSTRAINT PROPAGATION FOR RESOURCE CONSTRAINTS CONSTRAINT PROPAGATION ON OPTIMIZATION CRITERIA HEURISTIC SEARCH 23 VEHICLE ROUTING THE VEHICLE ROUTING PROBLEM OPERATIONS RESEARCH APPROACHES CONSTRAINT PROGRAMMING APPROACHES CONSTRAINT PROGRAMMING IN SEARCH USING CONSTRAINT PROGRAMMING AS A SUBPROBLEM SOLVER CP-VRP IN THE REAL WORLD 24 CON?GURATION WHAT IS CON?GURATION? CON?GURATION KNOWLEDGE CONSTRAINT MODELS FOR CON?GURATION PROBLEM SOLVING FOR CON?GURATION 25 CONSTRAINT APPLICATIONS IN NETWORKS ELECTRICITY NETWORKS WATER (OIL) NETWORKS DATA NETWORKS 26 BIOINFORMATICS AND CONSTRAINTS WHAT BIOLOGISTS WANT FROM BIOINFORMATICS THE CENTRAL DOGMA A CLASSI?CATION OF PROBLEM AREAS SEQUENCE RELATED PROBLEMS STRUCTURE RELATED PROBLEMS FUNCTION RELATED PROBLEMS MICROARRAYS