Principles and Practice of Constraint Programming – CP 2002: 8th International Conference, CP 2002 Ithaca, NY, USA, September 9–13, 2002 Proceedings

Michela Milano, Willem J. van Hoeve (auth.), Pascal Van Hentenryck (eds.)3540441204, 9783540441205

This book constitutes the refereed proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, CP 2002, held in Ithaca, NY, USA in September 2002.
The 38 revised full papers and 6 innovative application papers as well as the 14 short papers presented toghether with 25 abstracts from contributions to the doctoral program were carefully reviewed and selected from 146 submissions. All current issues in constraint processing are addressed, ranging from theoretical and foundational issues to application in various fields.

---

Table of contents :
Reduced Cost-Based Ranking for Generating Promising Subproblems….Pages 1-16
Integrating Constraint and Integer Programming for the Orthogonal Latin Squares Problem….Pages 17-32
On Optimal Correction of Inconsistent Linear Constraints….Pages 33-46
Temporal Planning through Mixed Integer Programming: A Preliminary Report….Pages 47-62
A New Multi-resource cumulatives Constraint with Negative Heights….Pages 63-79
On the Sum Constraint: Relaxation and Applications….Pages 80-92
Global Constraints for Lexicographic Orderings….Pages 93-108
A Global Filtering Algorithm for Handling Systems of Quadratic Equations and Inequations….Pages 109-123
Amplification of Search Performance through Randomization of Heuristics….Pages 124-138
Computing the Envelope for Stepwise-Constant Resource Allocations….Pages 139-154
Local Probing Applied to Scheduling….Pages 155-171
A Hybrid Approach for SAT….Pages 172-184
Recovering and Exploiting Structural Knowledge from CNF Formulas….Pages 185-199
Towards a Symmetric Treatment of Satisfaction and Conflicts in Quantified Boolean Formula Evaluation….Pages 200-215
Accelerating Random Walks….Pages 216-232
Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT….Pages 233-248
Learning and Solving Soft Temporal Constraints: An Experimental Study….Pages 249-264
Opportunistic Specialization in Russian Doll Search….Pages 264-279
Range-Based Algorithm for Max-CSP….Pages 280-294
Resolution Complexity of Random Constraints….Pages 295-310
Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics….Pages 310-326
Determining the Number of Solutions to Binary CSP Instances….Pages 327-340
Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions….Pages 341-356
Open Constraint Satisfaction….Pages 356-371
Beyond NP: Arc-Consistency for Quantified Constraints….Pages 371-386
Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information….Pages 387-401
A Dual Graph Translation of a Problem in ‘Life’….Pages 402-414
Groups and Constraints: Symmetry Breaking during Search….Pages 415-430
Partial Symmetry Breaking….Pages 431-445
Symmetry Breaking Revisited….Pages 446-461
Breaking Row and Column Symmetries in Matrix Models….Pages 462-477
Solving the Kirkman’s Schoolgirl Problem in a Few Seconds….Pages 477-491
Inferring Constraint Types in Constraint Programming….Pages 492-507
Model-Based Programming: Controlling Embedded Systems by Reasoning About Hidden State….Pages 508-524
The Adaptive Constraint Engine….Pages 525-540
Indexical-Based Solver Learning….Pages 541-556
Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions….Pages 556-572
Restart Policies with Dependence among Runs: A Dynamic Programming Approach….Pages 573-586
Visopt ShopFloor: On the Edge of Planning and Scheduling….Pages 587-602
Constraint Programming Contribution to Benders Decomposition: A Case Study….Pages 603-617
Modeling Camera Control with Constrained Hypertubes….Pages 618-632
Robust and Parallel Solving of a Network Design Problem….Pages 633-648
Connections Reservation with Rerouting for ATM Networks: A Hybrid Approach with Constraints….Pages 649-663
Communication and Computation in Distributed CSP Algorithms….Pages 664-679
Continuous First-Order Constraint Satisfaction with Equality and Disequality Constraints….Pages 680-685
A Relaxation of the Cumulative Constraint….Pages 686-691
Improving GSAT Using 2SAT….Pages 691-695
A Relational Constraint Solver for Model-Based Engineering….Pages 696-701
Conflict-Based Repair Techniques for Solving Dynamic Scheduling Problems….Pages 702-707
Scaling Properties of Pure Random Walk on Random 3-SAT….Pages 708-713
Criticality and Parallelism in Structured SAT Instances….Pages 714-719
Characterizing SAT Problems with the Row Convexity Property….Pages 720-725
Interchangeability in Soft CSPs….Pages 726-731
On Constraint Problems with Incomplete or Erroneous Data….Pages 732-737
Heuristic Constraint Propagation….Pages 738-743
An Arc-Consistency Algorithm for the Minimum Weight All Different Constraint….Pages 744-749
Algebraic Properties of CSP Model Operators….Pages 750-754
AC-3 d an Efficient Arc-Consistency Algorithm with a Low Space-Complexity….Pages 755-760
Integrating Search Objects in Asynchronous Constraint Solving….Pages 761-761
Distributed Constraint-Based Railway Simulation….Pages 762-762
Symmetry Breaking in Peaceably Coexisting Armies of Queens….Pages 763-763
Batch Processing with Sequence Dependent Setup Times….Pages 764-764
Interactive Heuristic Search Algorithm….Pages 765-765
On Constraint Problems with Incomplete or Erroneous Data….Pages 766-766
Design of a New Metaheuristic for MAXSAT Problems….Pages 767-767
Disjunctive and Continuous Constraint Satisfaction Problems….Pages 768-769
Tuning Randomization in Backtrack Search SAT Algorithms….Pages 769-769
Constraint Solving in Test-Data Generation….Pages 770-771
Improving Cost Calculations for Global Constraints in Local Search….Pages 772-772
A Modeling Framework for Constraints….Pages 773-774
A Linear Programming Based Satisfiability Solver Using a New Horn-Driven Search Tree Design….Pages 775-776
A Concurrent Constraint Programming Approach for Trajectory Determination of Autonomous Vehicles….Pages 777-777
Using Constraint Propagation to Accelerate Column Generation in Aircraft Scheduling….Pages 778-778
Solving and Learning Soft Temporal Constraints; Ceteris Paribus Statements Represented as Soft Constraints Problems….Pages 779-779
A Partially Solved Form for Heterogeneous Constraints in Disjunctive Normal Form….Pages 780-780
Models of Injection Problems….Pages 781-781
Partial Symmetry Breaking….Pages 782-782
Automatic Generation of Implied Clauses for SAT….Pages 783-783
Bridging the Gap between SAT and CSP….Pages 784-785
Reducing Symmetry in Matrix Models….Pages 786-786
Studying Interchangeability in Constraint Satisfaction Problems….Pages 787-788
Constraint Modeling in the Context of Academic Task Assignment….Pages 789-789
Design Tradeoffs for Autonomous Trading Agents….Pages 790-791