Principles and Practice of Constraint Programming — CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings

Andrew Eremin, Mark Wallace (auth.), Toby Walsh (eds.)3540428631, 9783540428633

This book constitutes the refereed proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, CP 2001, held in Paphos, Cyprus, in November/December 2001.
The 37 revised full papers, 9 innovative applications presentations, and 14 short papers presented were carefully reviewed and selected from a total of 135 submissions. All current issues in constraint processing are addressed, ranging from theoretical and foundational issues to advanced and innovative applications in a variety of fields.

---

Table of contents :
Hybrid Benders Decomposition Algorithms in Constraint Logic Programming….Pages 1-15
Branch-and-Check: A Hybrid Framework Integrating Mixed Integer Programming and Constraint Logic Programming….Pages 16-30
Towards Inductive Constraint Solving….Pages 31-45
Collaborative Learning for Constraint Solving….Pages 46-60
Towards Stochastic Constraint Programming: A Study of Onine Multi-Choice Knapsack with Deadlines….Pages 61-76
Global Cut Framework for Removing Symmetries….Pages 77-92
Symmetry Breaking….Pages 93-107
The Non-existence of (3,1,2)-Conjugate Orthogonal Idempotent Latin Square of Order 10….Pages 108-120
Random 3-SAT and BDDs: The Plot Thickens Further….Pages 121-136
Capturing Structure with Satisfiability….Pages 137-152
Phase Transitions and Backbones of 3-SAT and Maximum 3-SAT….Pages 153-167
Solving Non-binary CSPs Using the Hidden Variable Encoding….Pages 168-182
A Filtering Algorithm for the Stretch Constraint….Pages 183-195
Network Flow Problems in Constraint Programming….Pages 196-210
Pruning for the Minimum Constraint Family and for the Number of Distinct Values Constraint Family….Pages 211-224
A Constraint Programming Approach to the Stable Marriage Problem….Pages 225-239
Components for State Restoration in Tree Search….Pages 240-255
Adaptive Constraint Handling with CHR in Java….Pages 256-270
Consistency Maintenance for ABT….Pages 271-285
Constraint-Based Verification of Client-Server Protocols….Pages 286-301
A Temporal Concurrent Constraint Programming Calculus….Pages 302-316
Lower Bounds for Non-binary Constraint Optimization Problems….Pages 317-331
New Lower Bounds of Constraint Violations for Over-Constrained Problems….Pages 332-345
A General Scheme for Multiple Lower Bound Computation in Constraint Optimization….Pages 346-360
Solving Disjunctive Constraints for Interactive Graphical Applications….Pages 361-376
Sweep as a Generic Pruning Technique Applied to the Non-overlapping Rectangles Constraint….Pages 377-391
Non-overlapping Constraints between Convex Polytopes….Pages 392-407
Formal Models of Heavy-Tailed Behavior in Combinatorial Search….Pages 408-421
The Phase Transition of the Linear Inequalities Problem….Pages 422-432
In Search of a Phase Transition in the AC-Matching Problem….Pages 433-450
Specific Filtering Algorithms for Over-Constrained Problems….Pages 451-463
Specializing Russian Doll Search….Pages 464-478
A CLP Approach to the Protein Side-Chain Placement Problem….Pages 479-493
Fast, Constraint-Based Threading of HP-Sequences to Hydrophobic Cores….Pages 494-508
One Flip per Clock Cycle….Pages 509-523
Solving Constraints over Floating-Point Numbers….Pages 524-538
Optimal Pruning in Parametric Differential Equations….Pages 539-553
Interaction of Constraint Programming and Local Search for Optimisation Problems….Pages 554-559
Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency….Pages 560-564
Neighborhood-Based Variable Ordering Heuristics for the Constraint Satisfaction Problem….Pages 565-569
The Expressive Power of Binary Linear Programming….Pages 570-574
Constraint Generation via Automated Theory Formation….Pages 575-579
The Traveling Tournament Problem Description and Benchmarks….Pages 580-584
Deriving Explanations and Implications for Constraint Satisfaction Problems….Pages 585-589
Generating Tradeoffs for Interactive Constraint-Based Configuration….Pages 590-594
Structural Constraint-Based Modeling and Reasoning with Basic Configuration Cells….Pages 595-599
Composition Operators for Constraint Propagation:An Application to Choco….Pages 600-604
Solving Boolean Satisfiability Using Local Search Guided by Unit Clause Elimination….Pages 605-609
GAC on Conjunctions of Constraints….Pages 610-614
Dual Models of Permutation Problems….Pages 615-619
Boosting Local Search with Artificial Ants….Pages 620-624
Fast Optimal Instruction Scheduling for Single-Issue Processors with Arbitrary Latencies….Pages 625-639
Evaluation of Search Heuristics for Embedded System Scheduling Problems….Pages 640-654
Interpreting Sloppy Stick Figures with Constraint-Based Subgraph Matching….Pages 655-669
Selecting and Scheduling Observations for Agile Satellites: Some Lessons from the Constraint Reasoning Community Point of View….Pages 670-684
A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation….Pages 685-700
A Constraint Optimization Framework for Mapping a Digital Signal Processing Application onto a Parallel Architecture….Pages 701-715
iOpt: A Software Toolkit for Heuristic Search Methods….Pages 716-729
AbsCon: A Prototype to Solve CSPs with Abstraction….Pages 730-744
A Constraint Engine for Manufacturing Process Planning….Pages 745-759
On the Dynamic Detection of Interchangeability in Finite Constraint Satisfaction Problems….Pages 760-760
Automatic Generation of Implied Clauses for SAT….Pages 761-761
Verification of Infinite-State Systems by Specialization of CLP Programs….Pages 763-763
Partially Ordered Constraint Optimization Problems….Pages 763-763
Translations for Comparing Soft Frameworks….Pages 764-764
Counting Satisfiable k -CNF Formulas….Pages 765-765
High-Level Modelling and Reformulation of Constraint Satisfaction Problems….Pages 766-766
Distributed Constraint Satisfaction as a Computational Model of Negotiation via Argumentation….Pages 767-767
Aircraft Assignment Using Constraint Programming….Pages 768-768
Labelling Heuristics for CSP Application Domains….Pages 769-769
Improving SAT Algorithms by Using Search Pruning Techniques….Pages 770-770
Optimum Symmetry Breaking in CSPs Using Group Theory….Pages 771-771
Distributed Dynamic Backtracking….Pages 772-772
Constraint Programming for Distributed Resource Allocation….Pages 773-773
Exploiting the CSP Structure by Interchangeability….Pages 774-775
Constraint Processing Techniques for Model-Based Reasoning about Dynamic Systems….Pages 776-776
Distributed Constraint Satisfaction with Cooperating Asynchronous Solvers….Pages 777-777
Building Negative Reduced Cost Paths Using Constraint Programming….Pages 778-778
An Incremental and Non-binary CSP Solver: The Hyperpolyhedron Search Algorithm….Pages 779-780
Partial Stable Generated Models of Generalized Logic Programs with Constraints….Pages 781-782
Heterogeneous Constraint Problems An Outline of the Field of Work….Pages 783-783
Comparing SAT Encodings for Model Checking….Pages 784-784
Asynchronous Search for Numeric DisCSPs….Pages 785-785
Temporal Concurrent Constraint Programming….Pages 786-786