Principles and Practice of Constraint Programming – CP 2005: 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005. Proceedings

Héctor Geffner (auth.), Peter van Beek (eds.)3540292381, 9783540292388

This book constitutes the refereed proceedings of the 11th International Conference on Principles and Practice of Constraint Programming, CP 2005, held in Sitges, Spain, in October 2005.

The 48 revised full papers and 22 revised short papers presented together with extended abstracts of 4 invited talks and 40 abstracts of contributions to the doctoral students program as well as 7 abstracts of contributions to a systems demonstration session were carefully reviewed and selected from 164 submissions. All current issues of computing with constraints are addressed, ranging from methodological and foundational aspects to solving real-world problems in various application fields.

---

Table of contents :
Front Matter….Pages –
Search and Inference in AI Planning….Pages 1-4
OWL: A Description Logic Based Ontology Language….Pages 5-8
Preference Reasoning….Pages 9-12
The G12 Project: Mapping Solver Independent Models to Efficient Solutions….Pages 13-16
Symmetry Definitions for Constraint Satisfaction Problems….Pages 17-31
Dynamic Ordering for Asynchronous Backtracking on DisCSPs….Pages 32-46
Incremental Algorithms for Local Search from Existential Second-Order Logic….Pages 47-61
Inter-distance Constraint: An Extension of the All-Different Constraint for Scheduling Equal Length Jobs….Pages 62-76
Mind the Gaps: A New Splitting Strategy for Consistency Techniques….Pages 77-91
Graph Invariants as Necessary Conditions for Global Constraints….Pages 92-106
Allocation and Scheduling for MPSoCs via Decomposition and No-Good Generation….Pages 107-121
Sub-optimality Approximations….Pages 122-136
A Linear-Logic Semantics for Constraint Handling Rules….Pages 137-151
Distributed Stable Matching Problems….Pages 152-166
Beyond Hypertree Width: Decomposition Methods Without Decompositions….Pages 167-181
Ad-hoc Global Constraints for Life….Pages 182-195
Tractable Clones of Polynomials over Semigroups….Pages 196-210
CP(Graph): Introducing a Graph Computation Domain in Constraint Programming….Pages 211-225
Interval Analysis in Scheduling….Pages 226-240
Assumption-Based Pruning in Conditional CSP….Pages 241-255
Conditional Symmetry Breaking….Pages 256-270
Symmetry and Consistency….Pages 271-285
Solving the MOLR and Social Golfers Problems….Pages 286-300
Advances in Polytime Isomorph Elimination for Configuration….Pages 301-313
Planning and Scheduling to Minimize Tardiness….Pages 314-327
Search Heuristics and Heavy-Tailed Behaviour….Pages 328-342
2 -Way vs.d -Way Branching for CSP….Pages 343-357
Maintaining Longest Paths in Cyclic Graphs….Pages 358-372
Applying Constraint Programming to Rigid Body Protein Docking….Pages 373-387
Maximum Constraint Satisfaction on Diamonds….Pages 388-402
Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers….Pages 403-414
Generalized Conflict Learning for Hybrid Discrete/Linear Optimization….Pages 415-429
Parallel Local Search in Comet….Pages 430-444
Generating Corrective Explanations for Interactive Constraint Satisfaction….Pages 445-459
SPREAD: A Balancing Constraint Based on Statistics….Pages 460-474
Automatic Detection of Variable and Value Symmetries….Pages 475-489
Breaking All Value Symmetries in Surjection Problems….Pages 490-504
AC-*: A Configurable, Generic and Adaptive Arc Consistency Algorithm….Pages 505-519
Maintaining Arc Consistency Algorithms During the Search Without Additional Space Cost….Pages 520-533
Weak Composition for Qualitative Spatial and Temporal Reasoning….Pages 534-548
Boosting Distributed Constraint Satisfaction….Pages 549-562
Depth-First Mini-Bucket Elimination….Pages 563-577
Using SAT in QBF….Pages 578-592
Tree Decomposition with Function Filtering….Pages 593-606
On Solving Soft Temporal Constraints Using SAT Techniques….Pages 607-621
Eplex: Harnessing Mathematical Programming Solvers for Constraint Logic Programming….Pages 622-636
Caching Search States in Permutation Problems….Pages 637-651
Repair-Based Methods for Quantified CSPs….Pages 652-666
Handling Implication and Universal Quantification Constraints in FLUX….Pages 667-681
Solving Simple Planning Problems with More Inference and No Search….Pages 682-696
Solving Large-Scale Nonlinear Programming Problems by Constraint Partitioning….Pages 697-711
Factor Analytic Studies of CSP Heuristics….Pages 712-726
Lookahead Saturation with Restriction for SAT….Pages 727-731
Evolving Variable-Ordering Heuristics for Constrained Optimisation….Pages 732-736
Multi-point Constructive Search….Pages 737-741
Bounds of Graph Characteristics….Pages 742-746
Acquiring Parameters of Implied Global Constraints….Pages 747-751
Integrating Benders Decomposition Within Constraint Programming….Pages 752-756
Using Boolean Constraint Propagation for Sub-clauses Deduction….Pages 757-761
Extending Systematic Local Search for Job Shop Scheduling Problems….Pages 762-766
Interactive Reconfiguration in Power Supply Restoration….Pages 767-771
Neighbourhood Clause Weight Redistribution in Local Search for SAT….Pages 772-776
Computing and Exploiting Tree-Decompositions for Solving Constraint Networks….Pages 777-781
Encoding Requests to Web Service Compositions as Constraints….Pages 782-786
Test Instance Generation for MAX 2SAT….Pages 787-791
Consistency for Quantified Constraint Satisfaction Problems….Pages 792-796
Alternate Modeling in Sport Scheduling….Pages 797-801
Approximations in Distributed Optimization….Pages 802-806
Extremal CSPs….Pages 807-811
Beyond Finite Domains: The All Different and Global Cardinality Constraints….Pages 812-816
Views and Iterators for Generic Constraint Implementations….Pages 817-821
Approximated Consistency for the Automatic Recording Problem….Pages 822-826
Towards an Optimal CNF Encoding of Boolean Cardinality Constraints….Pages 827-831
Approximate Constrained Subgraph Matching….Pages 832-836
Distributed Constraints for Large-Scale Scheduling Problems….Pages 837-837
Solving Over-Constrained Problems with SAT….Pages 838-838
A Constraint Based Agent for TAC–SCM….Pages 839-839
Solving the Car-Sequencing Problem as a Non-binary CSP….Pages 840-840
Dimensioning an Inbound Call Center Using Constraint Programming….Pages 841-841
Methods to Learn Abstract Scheduling Models….Pages 842-842
Automated Search for Heuristic Functions….Pages 843-843
Constraint-Based Inference: A Bridge Between Constraint Processing and Probability Inference….Pages 844-844
Scheduling Social Tournaments….Pages 845-845
Domain Reduction for the Circuit Constraint….Pages 846-846
Using Constraint Programming for Solving Distance CSP with Uncertainty….Pages 847-847
Improved Algorithm for Finding (a,b)-Super Solutions….Pages 848-848
Local Consistency in Weighted CSPs and Inference in Max-SAT….Pages 849-849
Modeling Constraint Programs with Software Technology Standards….Pages 850-850
Solution Equivalent Subquadrangle Reformulations of Constraint Satisfaction Problems….Pages 851-851
Mechanism Design for Preference Aggregation over Coalitions….Pages 852-852
LP as a Global Search Heuristic Across Different Constrainedness Regions….Pages 853-853
Consistency for Partially Defined Constraints….Pages 854-854
Subnet Generation Problem: A New Network Routing Problem….Pages 855-855
Partial Redundant Modeling….Pages 856-856
AND/OR Branch-and-Bound for Solving Mixed Integer Linear Programming Problems….Pages 857-857
Weak Symmetries in Problem Formulations….Pages 858-858
Towards the Systematic Generation of Channelling Constraints….Pages 859-859
AND/OR Search Spaces and the Semantic Width of Constraint Networks….Pages 860-860
Statistical Modelling of CSP Solving Algorithms Performance….Pages 861-861
Probabilistic Arc Consistency….Pages 862-862
GOOSE – A Generic Object-Oriented Search Environment….Pages 863-863
Randomization for Multi-agent Constraint Optimization….Pages 864-864
Uncertainty in Soft Constraint Problems….Pages 865-865
Speeding Up Constrained Path Solvers with a Reachability Propagator….Pages 866-866
From Linear Relaxations to Global Constraint Propagation….Pages 867-867
Encoding HTN Planning as a Dynamic CSP….Pages 868-868
Specialised Constraints for Stable Matching Problems….Pages 869-869
Bounds-Consistent Local Search….Pages 870-870
Robust Constraint Solving Using Multiple Heuristics….Pages 871-871
Scheduling with Uncertain Start Dates….Pages 872-872
The Role of Redundant Clauses in Solving Satisfiability Problems….Pages 873-873
Applying Decomposition Methods to Crossword Puzzle Problems….Pages 874-874
Asymmetric Distributed Constraints Satisfaction Problems….Pages 875-875
Full Arc Consistency in WCSP and in Constraint Hierarchies with Finite Domains….Pages 876-876
CoJava: A Unified Language for Simulation and Optimization….Pages 877-877
Programming with $mathcal{TOY}(mathcal{FD})$ ….Pages 878-878
Computing Super- Schedules….Pages 879-879
Proterv-II: An Integrated Production Planning and Scheduling System….Pages 880-880
The Comet Programming Language and System….Pages 881-881
Random Stimuli Generation for Functional Hardware Verification as a CP Application….Pages 882-882
A BDD-Based Interactive Configurator for Modular Systems….Pages 883-883
Back Matter….Pages –