Hentenryck / Milano Hybrid Optimization

The Ten Years of CPAIOR
1. Auflage 2010
ISBN: 978-1-4419-1644-0
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 45, 560 Seiten

Reihe: Springer Optimization and Its Applications

Hybrid Optimization focuses on the application of artificial intelligence and operations research techniques to constraint programming for solving combinatorial optimization problems. This book covers the most relevant topics investigated in the last ten years by leading experts in the field, and speculates about future directions for research. This book includes contributions by experts from different but related areas of research including constraint programming, decision theory, operations research, SAT, artificial intelligence, as well as others. These diverse perspectives are actively combined and contrasted in order to evaluate their relative advantages. This volume presents techniques for hybrid modeling, integrated solving strategies including global constraints, decomposition techniques, use of relaxations, and search strategies including tree search local search and metaheuristics. Various applications of the techniques presented as well as supplementary computational tools are also discussed.

Autoren/Hrsg.

Milano, Michela

Hentenryck, Pascal Van

Inhaltsverzeichnis

1;Preface;6
2;Contents;8
3;Contributors;10
4;The Ten Years of CPAIOR: A Success Story;14
4.1;1 Introduction;14
4.2;2 Chapter Overview;16
4.3;References;21
5;Hybrid Modeling;23
5.1;1 Modeling as a Key to Hybrid Problem Solving;23
5.2;2 Modeling Systems;25
5.3;3 Basic Terminology;26
5.4;4 CP Modeling;27
5.4.1;4.1 Consistency, Filtering, and Propagation;27
5.4.2;4.2 Global Constraints;27
5.4.3;4.3 Example: Sudoku Puzzles;28
5.4.4;4.4 CP Modeling Guidelines;29
5.4.5;4.5 Example: Car Sequencing;30
5.4.6;4.6 Example: Employee Scheduling;32
5.4.7;4.7 Assignment and Circuit Problems;35
5.5;5 MILP Modeling;37
5.5.1;5.1 Knapsack Modeling;38
5.5.2;5.2 MILP Representability;40
5.5.3;5.3 Example: Fixed-Charge Problems;43
5.5.4;5.4 MILP Modeling Guidelines;45
5.5.5;5.5 Example: Facility Location;46
5.5.6;5.6 Examples: Piecewise Linear and Indicator Constraints;49
5.5.7;5.7 Example: Car Sequencing;52
5.5.8;5.8 Network Flow Models;53
5.5.9;5.9 Assignment Problems;53
5.5.10;5.10 Circuit Problems;54
5.5.11;5.11 Example: Sudoku Puzzles;55
5.6;6 Integrated Modeling;55
5.6.1;6.1 Integrated Modeling Guidelines;57
5.6.2;6.2 Example: Facility Location;57
5.6.3;6.3 Examples: Piecewise Linear and Indicator Constraints;58
5.6.4;6.4 Network Flow Problems;60
5.6.5;6.5 Assignment Problems;60
5.6.6;6.6 Circuit Problems;61
5.6.7;6.7 Example: Sudoku Puzzles;63
5.6.8;6.8 Example: Car Sequencing;63
5.6.9;6.9 Example: Employee Scheduling;65
5.6.10;6.10 Decomposition: Machine Assignment and Scheduling;65
5.6.11;6.11 Decomposition: Routing and Frequency Assignment;67
5.7;7 Conclusions;69
5.8;References;71
6;Global Constraints: A Survey;75
6.1;1 Introduction;75
6.1.1;1.1 CP Principles;76
6.1.2;1.2 Global Constraints;76
6.2;2 Preliminaries and Notations;81
6.3;3 Global Constraints Collection;83
6.3.1;3.1 Solution Based Constraints;84
6.3.1.1;3.1.1 Generic Constraint (GENERIC);85
6.3.1.2;3.1.2 Table Constraint (TABLE);88
6.3.2;3.2 Counting Constraints;88
6.3.2.1;3.2.1 Flow Theory;89
6.3.2.2;3.2.2 Alldiff and Permutation Constraints (ALLDIFF, PERMUTATION);93
6.3.2.3;3.2.3 Global Cardinality Constraint (GCC) ;94
6.3.2.4;3.2.4 Cardinality Matrix Constraint (CARD-MATRIX);95
6.3.2.5;3.2.5 Global Cardinality Constraint with Costs (COST-GCC);96
6.3.3;3.3 Balancing Constraints;97
6.3.4;3.4 Constraint Combination Based Constraints;99
6.3.4.1;3.4.1 Max-SAT Constraint (MAX-SAT);99
6.3.4.2;3.4.2 Or and And Constraints (AND, OR);101
6.3.5;3.5 Sequencing Constraints;101
6.3.5.1;3.5.1 Among Constraint (AMONG);102
6.3.5.2;3.5.2 Sequence Constraint (SEQUENCE) ;102
6.3.5.3;3.5.3 Generalized Sequence Constraint (GEN-SEQUENCE);106
6.3.5.4;3.5.4 Global Sequencing Constraint (GSC);107
6.3.6;3.6 Distance Constraints;108
6.3.6.1;3.6.1 Inter-Distance Constraint (INTER-DISTANCE);108
6.3.6.2;3.6.2 Sum and Binary Inequalities Constraint (SUM-INEQ);108
6.3.7;3.7 Geometric Constraints;109
6.3.8;3.8 Summation Based Constraints;110
6.3.8.1;3.8.1 Subset-Sum Constraint (SUBSET-SUM);110
6.3.8.2;3.8.2 Knapsack Constraint (KNAPSACK);112
6.3.9;3.9 Packing Constraints;114
6.3.9.1;3.9.1 Symmetric Alldiff Constraint (SYM-ALLDIFF);114
6.3.9.2;3.9.2 Stretch Constraint (STRETCH);114
6.3.9.3;3.9.3 k-diff Constraint (K-DIFF);115
6.3.9.4;3.9.4 Number of Distinct Values Constraint (NVALUE);116
6.3.9.5;3.9.5 Bin Packing Constraint (BIN-PACKING);116
6.3.10;3.10 Graph Based Constraints;118
6.3.10.1;3.10.1 Cycle Constraint (CYCLE);118
6.3.10.2;3.10.2 Path Constraint (PATH);118
6.3.10.3;3.10.3 Path Partitioning Constraint (PATH-PARTITION);119
6.3.10.4;3.10.4 Shorter Path Constraint (SHORTER-PATH);120
6.3.10.5;3.10.5 Tree Constraint (TREE);120
6.3.10.6;3.10.6 Weighted Spanning Tree Constraint (WST);121
6.3.11;3.11 Order Based Constraints;123
6.3.11.1;3.11.1 Lexicographic Constraint (LEXICO);123
6.3.11.2;3.11.2 Sort Constraint (SORT);123
6.3.12;3.12 Formal Language Based Constraints;124
6.3.12.1;3.12.1 Regular Language Based Constraints (REGULAR);124
6.3.12.2;3.12.2 Context-Free Language Based Constraints(GRAMMAR);129
6.4;4 Filtering Algorithm Design;132
6.4.1;4.1 Algorithms Based on Constraints Addition;133
6.4.2;4.2 Filtering Algorithms Based on Existing Algorithms;133
6.4.3;4.3 Dedicated Filtering Algorithms;135
6.5;5 Discussion;136
6.5.1;5.1 Incrementality and Amortized Complexity;136
6.5.2;5.2 Incomplete Algorithms and Fixed-Point Property;137
6.5.3;5.3 Identification of the Filtering;138
6.5.4;5.4 Closure;138
6.5.5;5.5 Power of a Filtering Algorithm;139
6.6;6 Conclusion;140
6.7;References;140
7;Decomposition Techniques for Hybrid MILP/CP Models applied to Scheduling and Routing Problems;147
7.1;1 Introduction;147
7.2;2 Literature Review;148
7.2.1;2.1 Hybrid MILP/CP Algorithms for Scheduling;150
7.2.2;2.2 Hybrid Column Generation Approaches;154
7.3;3 Applications to Scheduling;156
7.3.1;3.1 Methodology;156
7.3.1.1;3.1.1 MILP/CP-Based Decomposition Method;158
7.3.1.2;3.1.2 Branch-and-Cut Method;159
7.3.2;3.2 Single-Stage Scheduling Problem;161
7.3.2.1;3.2.1 Hybrid MILP/CP Model;162
7.3.2.2;3.2.2 Discrete-Time MILP Model (DT);164
7.3.2.3;3.2.3 Continuous-Time MILP Model (CT);165
7.3.3;3.3 Computational Studies;166
7.4;4 Applications to Vehicle Routing and Crew Scheduling;168
7.4.1;4.1 Set Based Model;170
7.4.1.1;4.1.1 Variables;171
7.4.1.2;4.1.2 Objective;171
7.4.1.3;4.1.3 Constraints;171
7.4.2;4.2 Position Based Model;171
7.4.2.1;4.2.1 Variables;172
7.4.2.2;4.2.2 Objective;172
7.4.2.3;4.2.3 Constraints;172
7.4.3;4.3 Arc Based Model;172
7.4.3.1;4.3.1 Variables;172
7.4.3.2;4.3.2 Objective;173
7.4.3.3;4.3.3 Constraints;173
7.4.3.4;4.3.4 Redundant Constraints;174
7.4.4;4.4 Solving the Integer Problem;175
7.5;5 Conclusions;175
7.6;References;176
8;Hybrid Solving Techniques;180
8.1;1 Introduction;180
8.2;2 Exploiting OR Techniques within CP;182
8.2.1;2.1 Interaction Between CP & MIP Solvers;183
8.2.2;2.2 Linearizing Global Constraints;184
8.2.3;2.3 Cost-Based Domain Filtering;185
8.2.4;2.4 Specialized OR Methods within Hybrid Algorithms;186
8.3;3 Exploiting CP Techniques within MIP;189
8.3.1;3.1 Design Concepts;190
8.3.2;3.2 Interfacing to the Framework;193
8.3.3;3.3 Infrastructure Provided by the Framework;195
8.3.4;3.4 Solution Process;198
8.4;4 Conclusions;200
8.5;References;200
9;Over-Constrained Problems;202
9.1;1 Introduction;202
9.1.1;1.1 A Brief Historical Overview;203
9.1.2;1.2 Outline;204
9.2;2 Constraint Programming;204
9.3;3 From Soft Constraints to Hard Optimization Constraints;206
9.4;4 Soft Global Constraints;209
9.4.1;4.1 Matchings;210
9.4.2;4.2 Network Flows;210
9.4.3;4.3 Soft Alldifferent Constraint;211
9.4.4;4.4 Variable-Based Violation Measure;212
9.4.5;4.5 Decomposition-Based Violation Measure;214
9.4.6;4.6 Soft Global Cardinality Constraint;216
9.4.6.1;4.6.1 Two Capacitated Matchings;217
9.4.6.2;4.6.2 Variable-Based Violation Measure;218
9.4.6.3;4.6.3 Value-Based Violation Measure;219
9.4.7;4.7 Soft Regular Constraint;220
9.4.7.1;4.7.1 Variable-Based Violation Measure;222
9.4.7.2;4.7.2 Edit-Based Violation Measure;223
9.4.8;4.8 Other Soft Global Constraints;225
9.4.8.1;4.8.1 Soft Cumulative Constraint;225
9.4.8.2;4.8.2 Soft Precedence Constraint;225
9.4.8.3;4.8.3 Soft Constraints for a Timetabling Application;226
9.4.8.4;4.8.4 Soft Balancing Constraints;226
9.4.8.5;4.8.5 Soft Same Constraint;226
9.4.8.6;4.8.6 Soft All-Equal Constraint;227
9.4.8.7;4.8.7 Soft Sequence Constraint;227
9.4.8.8;4.8.8 Soft Slide Constraint;228
9.4.8.9;4.8.9 Soft Context-Free Grammar Constraint;228
9.4.8.10;4.8.10 -Alldifferent, -Gcc, and -Regular Constraints;228
9.4.8.11;4.8.11 Soft Global Constraints for Weighted CSPs;229
9.4.8.12;4.8.12 Soft Global Constraints for Preference Modeling;229
9.4.8.13;4.8.13 Global Constraint for Max-CSP;229
9.4.8.14;4.8.14 Soft Open Global Constraints;229
9.5;5 Constraint-Based Local Search;230
9.6;6 Conclusion and Outlook;231
9.7;References;232
10;A Survey on CP-AI-OR Hybrids for Decision Making Under Uncertainty;237
10.1;1 Introduction;237
10.2;2 Decision Making Under Uncertainty;238
10.2.1;2.1 Single-Stage Stochastic Knapsack;239
10.2.2;2.2 Multi-Stage Stochastic Knapsack;242
10.3;3 A Collection of Stochastic Problems;244
10.3.1;3.1 Stochastic Queueing Control Problem;244
10.3.2;3.2 Scheduling Conditional Task Graphs;245
10.3.3;3.3 Stochastic Reservation;245
10.3.4;3.4 Job Shop Scheduling with Probabilistic Duration;245
10.3.5;3.5 Two-Stage Stochastic Matching Problem;245
10.3.6;3.6 Production/Inventory Management;246
10.3.7;3.7 Stochastic Template Design;246
10.3.8;3.8 Scheduling Internal Audit Activities;247
10.3.9;3.9 Stochastic Sequencing with Release Times and Deadlines;247
10.4;4 Frameworks for Decision Making Under Uncertainty in CP and AI;248
10.4.1;4.1 Stochastic Boolean Satisfiability;248
10.4.1.1;4.1.1 Definitions;248
10.4.1.2;4.1.2 Restrictions and Generalizations;249
10.4.2;4.2 Probabilistic Constraint Satisfaction Problems;249
10.4.2.1;4.2.1 Definitions;250
10.4.3;4.3 Event-Driven Probabilistic Constraint Programming;250
10.4.3.1;4.3.1 Definitions;251
10.4.3.2;4.3.2 Relations to Other Frameworks;251
10.4.4;4.4 Stochastic Constraint Programming;252
10.4.4.1;4.4.1 Definitions;252
10.5;5 A Classification of Existing Approaches;253
10.6;6 Approaches Based on Stochastic Reasoning;254
10.6.1;6.1 General Purpose Strategies;255
10.6.1.1;6.1.1 Probabilistic CSP;256
10.6.1.2;6.1.2 Stochastic Constraint Programming;256
10.6.1.3;6.1.3 Evolved Parameterized Policies;257
10.6.1.4;6.1.4 Stochastic SAT;257
10.6.2;6.2 Problem Specific Strategies;258
10.6.2.1;6.2.1 Scheduling Conditional Task Graphs;258
10.6.2.2;6.2.2 Computing Optimal R,S Policy Parameters Under Service Level Constraints;259
10.6.2.3;6.2.3 Computing Optimal R,S Policy Parameters Under a Penalty Cost Scheme;259
10.6.2.4;6.2.4 Cost-based Filtering for Stochastic Inventory Control;259
10.6.2.5;6.2.5 Evolutionary Search for Replenishment Cycle Policies;260
10.6.2.6;6.2.6 Neuroevolutionary Inventory Control;260
10.7;7 Reformulation-Based Approaches;260
10.7.1;7.1 General Purpose Strategies;261
10.7.1.1;7.1.1 Scenario-Based Stochastic Constraint Programming;261
10.7.1.2;7.1.2 Event-Driven Probabilistic Constraint Programming;263
10.7.2;7.2 Problem Specific Strategies;263
10.7.2.1;7.2.1 Stochastic Queueing Control Problem;263
10.7.2.2;7.2.2 A Stochastic Allocation and Scheduling Problem;264
10.7.2.3;7.2.3 Scheduling Internal Audit Units;264
10.7.2.4;7.2.4 Job Shop Scheduling with Probabilistic Durations;265
10.7.2.5;7.2.5 Production/Inventory Control Problem;265
10.7.2.6;7.2.6 Local Search for Stochastic Template Design;265
10.8;8 Approaches Based on Sampling;266
10.8.1;8.1 Sample Average Approximation;268
10.8.1.1;8.1.1 Two-stage Stochastic Matching Problem;268
10.8.2;8.2 Forward Sampling;268
10.8.2.1;8.2.1 Multi-Choice Stochastic Knapsack with Deadlines;268
10.8.2.2;8.2.2 Job Shop Scheduling with Probabilistic Durations;269
10.8.3;8.3 Sample Aggregation;269
10.8.3.1;8.3.1 Multi-Choice Stochastic Knapsack with Deadlines;270
10.9;9 Related Works;270
10.9.1;9.1 Stochastic Dynamic Programming;271
10.9.2;9.2 Related Modeling Frameworks;271
10.10;10 Conclusions;273
10.11;Appendix;274
10.12;References;276
11;Constraint Programming and Local Search Hybrids;281
11.1;1 Introduction;281
11.2;2 Local Search on CP Models;282
11.2.1;2.1 Min-Conflicts and Related Algorithms;282
11.2.2;2.2 SAT-Based Methods;285
11.2.3;2.3 Localizer and Comet;286
11.2.4;2.4 Some Other Methods;288
11.3;3 Using CP to Evaluate Neighborhoods;289
11.3.1;3.1 Constraint Checking;290
11.3.2;3.2 Exploring the Neighborhood Using Tree Search;290
11.3.2.1;3.2.1 An Example;291
11.3.2.2;3.2.2 Flexibility and Efficiency;292
11.3.3;3.3 Large Neighborhood Search;294
11.3.3.1;3.3.1 The Re-Optimization Method;296
11.3.3.2;3.3.2 Selecting the Fragment;297
11.3.3.3;3.3.3 Learning in Large Neighborhood Search;299
11.4;4 Local Search for Pruning and Propagation;300
11.5;5 Other Integrations;303
11.6;6 Conclusion;308
11.7;References;309
12;Hybrid Metaheuristics;314
12.1;1 Introduction;314
12.2;2 Examples and Literature Overview;315
12.2.1;2.1 Hybridization of Metaheuristics with (Meta-)Heuristics;315
12.2.1.1;2.1.1 Multilevel Techniques;316
12.2.1.2;2.1.2 Hyper-Heuristics;317
12.2.1.3;2.1.3 Literature Overview;318
12.2.2;2.2 Hybridization of Metaheuristics With Constraint Propagation Techniques;319
12.2.2.1;2.2.1 Ant Colony Optimization Hybridized with Constraint Programming;320
12.2.2.2;2.2.2 Solution-Guided Multi-Point Constructive Search;322
12.2.2.3;2.2.3 Literature Overview;323
12.2.3;2.3 Hybridizing Metaheuristics with Tree Search;324
12.2.3.1;2.3.1 Beam-ACO;325
12.2.3.2;2.3.2 Large Neighborhood Search Based on MIP Solvers;326
12.2.3.3;2.3.3 Literature Overview;328
12.2.4;2.4 Hybridization of Metaheuristics With Problem Relaxation;329
12.2.4.1;2.4.1 Searching in the Vicinity of Non-Integral Solutions;330
12.2.4.2;2.4.2 Relaxation Guided Variable Neighborhood Search;331
12.2.4.3;2.4.3 Literature Overview;332
12.2.5;2.5 Hybridization of Metaheuristics With Dynamic Programming;333
12.2.5.1;2.5.1 Iterated Dynasearch;333
12.2.5.2;2.5.2 Dynamic Programming for Solving Subproblems;335
12.2.5.3;2.5.3 Literature Overview;336
12.3;3 Discussion and Conclusions;337
12.4;References;339
13;Learning in Search;345
13.1;1 Introduction;345
13.2;2 Strategy Learning;346
13.2.1;2.1 Strategy Learning in Integer Programming;348
13.2.2;2.2 Impacts-Based Strategies in Constraint Programming;350
13.2.3;2.3 Conflict-Directed Strategies in Constraint Programming;354
13.3;3 Search Restarts for Exploiting Learning;356
13.4;4 Clause Learning;357
13.4.1;4.1 Clause Learning for Satisfiability Problems;357
13.4.2;4.2 Clause Learning in Constraint Programming;359
13.5;5 Conclusion;362
13.6;References;363
14;What Is Autonomous Search?;365
14.1;1 Introduction;365
14.1.1;1.1 Related Approaches;366
14.1.2;1.2 Autonomous Search;367
14.1.3;1.3 Chapter Organization;368
14.2;2 Solvers Architecture;368
14.2.1;2.1 General Architecture;369
14.2.1.1;2.1.1 Problem Modeling/Encoding;369
14.2.1.2;2.1.2 The Evaluation Function;370
14.2.1.3;2.1.3 The Solving Algorithm;371
14.2.1.4;2.1.4 Configuration of the Solver: The Parameters;372
14.2.1.5;2.1.5 Control;372
14.2.1.6;2.1.6 Existing Classifications and Taxonomies;373
14.2.2;2.2 Architecture of Autonomous Solvers;375
14.2.2.1;2.2.1 Control by Self Adaptation;376
14.2.2.2;2.2.2 Control by Supervised Adaptation;376
14.2.3;2.3 Searching for a Solution vs. Solutions for Searching;376
14.2.4;2.4 A Rule-Based Characterization of Solvers;377
14.2.4.1;2.4.1 Formal Description;378
14.2.4.2;2.4.2 Identification of Computation Rules;381
14.2.4.3;2.4.3 Control of the Computation Rules and Solvers;382
14.3;3 Case Studies;384
14.3.1;3.1 Tuning Before Solving;384
14.3.1.1;3.1.1 Preprocessing Techniques;384
14.3.1.2;3.1.2 Parameter Tuning on Preliminary Experiments;385
14.3.1.3;3.1.3 Components Setting Before Solving;386
14.3.2;3.2 Control During Solving;387
14.3.2.1;3.2.1 Controlling Encoding;387
14.3.2.2;3.2.2 Controlling Variable Orderings and Values Selection in Search Heuristics;387
14.3.2.3;3.2.3 Evolving Heuristics;388
14.3.2.4;3.2.4 Controlling Evaluation Function;389
14.3.2.5;3.2.5 Parameters Control in Metaheuristics Algorithms;389
14.3.3;3.3 Control During Solving in Parallel and Distributed Search;390
14.4;4 Challenges and Opportunities;391
14.4.1;4.1 Performance Evaluation;391
14.4.2;4.2 Continuous Search;392
14.4.3;4.3 Automated Generation of Components;393
14.5;5 Conclusion;393
14.6;References;395
15;Software Tools Supporting Integration;400
15.1;1 Introduction;400
15.2;2 Existing Features That Facilitate Integration;402
15.3;3 BARON;403
15.4;4 Comet;405
15.5;5 ECLiPSe;408
15.6;6 G12;410
15.7;7 IBM ILOG CP Optimizer and OPL Development Studio;412
15.8;8 SCIP;415
15.9;9 SIMPL;418
15.10;10 Xpress-Mosel;420
15.11;11 Other Hybrid Tools;423
15.11.1;11.1 COIN-OR;423
15.11.2;11.2 Microsoft Solver Foundation;424
15.11.3;11.3 Prolog IV;424
15.11.4;11.4 SALSA;424
15.11.5;11.5 ToOLS;425
15.12;12 Conclusion;425
15.13;References;427
16;Connections and Integration with SAT Solvers: A Survey and a Case Study in Computational Biology;431
16.1;1 Introduction;431
16.2;2 Boolean Constraints as Part of the Bigger Picture;432
16.3;3 Brief Overview of SAT and its Integration in CP;434
16.3.1;3.1 Community and Approach to Research;434
16.3.2;3.2 Techniques Used in SAT and CP;436
16.3.2.1;3.2.1 Propagation;436
16.3.2.2;3.2.2 Execution Tracing and Analysis;437
16.3.3;3.3 Problem Solving in SAT and CP;439
16.3.4;3.4 Integration of SAT Solvers into CP Solvers;440
16.3.4.1;3.4.1 Use of SAT to Solve the Boolean Structure;440
16.3.4.2;3.4.2 Translations to SAT;441
16.4;4 Application to GRN Deciphering;445
16.4.1;4.1 Thomas-GRNs;446
16.4.2;4.2 Thomas-GRNs Formalization in CLP and SAT;449
16.4.2.1;4.2.1 The CLP Encoding of Thomas-GRNs;449
16.4.2.2;4.2.2 The SAT Encoding;452
16.4.3;4.3 Five Examples of GRN Deciphering Queries;453
16.4.3.1;4.3.1 Query 1: Models Consistent with the Existence of One Steady State;453
16.4.3.2;4.3.2 Query 2: Models Consistent with Biological Observations;454
16.4.3.3;4.3.3 Query 3: Diameter of the Network Taking into Consideration the Biological Observations;455
16.4.3.4;4.3.4 Query 4: Models Consistent with Biological Observations and Induction Hypotheses;455
16.4.3.5;4.3.5 Query 5: Inference of Necessary Hypotheses Among the Hypotheses About Composition of Interactions;457
16.4.4;4.4 Discussion;457
16.5;5 Conclusion;458
16.6;Appendix;461
16.7;Appendix;462
16.8;References;462
17;Bioinformatics: A Challenge to Constraint Programming;468
17.1;1 Introduction;468
17.1.1;1.1 Data Sources;469
17.1.2;1.2 About This Article;469
17.2;2 Sequence Analysis;470
17.2.1;2.1 Phylogenetic Trees;471
17.2.2;2.2 Haplotypes and SNP;472
17.3;3 RNA Structure;474
17.3.1;3.1 Questions Related to Secondary Structure;475
17.3.2;3.2 Ab Initio 3D Structure Prediction;477
17.4;4 Protein Structure Modeling;478
17.4.1;4.1 Structure Prediction;479
17.4.1.1;4.1.1 Lattice and HP Models;479
17.4.2;4.2 Protein Structure Determination;483
17.5;5 Protein Interaction;484
17.6;6 Systems Biology;485
17.7;7 Conclusion;487
17.8;References;488
18;Sports Scheduling;493
18.1;1 Introduction and Scope;493
18.2;2 Constrained Minimum Break Scheduling;495
18.2.1;2.1 Multiple Step Approach;496
18.2.2;2.2 Schedule then Break;498
18.2.3;2.3 Future Directions;499
18.3;3 Traveling Tournament Problem;500
18.3.1;3.1 Exact Approaches;503
18.3.2;3.2 Lower Bounds;504
18.3.3;3.3 Feasible Solutions;505
18.3.4;3.4 Further Work and the Future of the TTP;506
18.4;4 Further Models;507
18.5;5 Conclusions;508
18.6;References;509
19;Stimuli Generation for Functional Hardware Verification with Constraint Programming;513
19.1;1 Introduction;513
19.2;2 Functional Hardware Verification;516
19.2.1;2.1 Verification Process;516
19.2.2;2.2 Formal Verification;517
19.2.3;2.3 Simulation-based Verification and Stimuli Generation;518
19.2.3.1;2.3.1 Targeted Versus Massive Pseudo-Random Stimuli Generation;519
19.2.3.2;2.3.2 Test Specification Language;520
19.2.3.3;2.3.3 Static Versus Dynamic Stimuli Generation;521
19.2.3.4;2.3.4 Checking;522
19.2.3.5;2.3.5 Test Benches;522
19.3;3 Constraint Satisfaction for Stimuli Generation;523
19.3.1;3.1 Introduction and Motivation;523
19.3.2;3.2 Unique Requirements;524
19.3.3;3.3 Alternatives to Constraint Programming and Hybrid Approaches;526
19.3.3.1;3.3.1 Declarative Alternatives;526
19.3.3.2;3.3.2 Hybrid Approaches;526
19.3.3.3;3.3.3 Procedural Alternatives;528
19.3.3.4;3.3.4 Manual Alternatives;528
19.3.4;3.4 Concrete Example;528
19.4;4 Modeling for Verification with CP;530
19.4.1;4.1 Introduction;530
19.4.2;4.2 Distributed Model;531
19.4.3;4.3 A CSP-Oriented Modeling Language;532
19.5;5 Examples of CP models;535
19.5.1;5.1 Processor Modeling;535
19.5.2;5.2 Verifying ADL-based Systems with Random CSPs;536
19.5.3;5.3 Micro-architectural Events;537
19.5.4;5.4 Address Translation;539
19.5.5;5.5 System Modeling;541
19.5.6;5.6 Automatic Test-pattern Generation;542
19.6;6 Advanced Topics and Challenges;543
19.6.1;6.1 Dynamic Test Program Generation;543
19.6.2;6.2 Problem Partitioning;544
19.6.3;6.3 Compliance Validation;546
19.6.4;6.4 Checking the Processor's Memory Model;549
19.6.5;6.5 System Verification: Coupling of the Transaction Path CSP with the Unit CSPs;551
19.6.6;6.6 Complex Data Transfers: Unbounded Vector Constraints;553
19.6.7;6.7 Floating Point Unit Verification: A Small and Hard CSP;556
19.7;7 Conclusions;558
19.8;References;559