Principles and practice of constraint programming -- CP 2005 : 11th international conference, CP 2005, Sitges, Spain, October 1-5, 2005 : proceedings

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. Invited Papers. Search And Inference In Ai Planning / Hector Geffner -- Owl: A Description Logic Based Ontology Language / Ian Horrocks -- Preference Reasoning / Francesca Rossi -- The G12 Project: Mapping Solver Independent Models To Efficient Solutions / Peter J. Stuckey, Maria Garcia De La Banda, Michael Maher, Kim Marriott, John Slaney, Zoltan Somogyi, Mark Wallace, Toby Walsh -- Best Papers. Symmetry Definitions For Constraint Satisfaction Problems / David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, Barbara M. Smith -- Dynamic Ordering For Asynchronous Backtracking On Discsps / Roie Zivan, Amnon Meisels -- Full Papers. Incremental Algorithms For Local Search From Existential Second-order Logic / Magnus Agren, Pierre Flener, Justin Pearson -- Inter-distance Constraint: An Extension Of The All-different Constraint For Scheduling Equal Length Jobs / Konstantin Artiouchine, Philippe Baptiste --^ Mind The Gaps: A New Splitting Strategy For Consistency Techniques / Heikel Batnini, Claude Michel, Michel Rueher -- Graph Invariants As Necessary Conditions For Global Constraints / Nicolas Beldiceanu, Mats Carlsson, Jean-xavier Rampon, Charlotte Truchet -- Allocation And Scheduling For Mpsocs Via Decomposition And No-good Generation / Luca Benini, Davide Bertozzi, Alessio Guerri, Michela Miano -- Sub-optimality Approximations / Russell Bent, Irit Katriel, Pascal Van Hentenryck -- A Linear-logic Semantics For Constraint Handling Rules / Hariolf Betz, Thom Fruhwirth -- Distributed Stable Matching Problems / Ismel Brito, Pedro Meseguer -- Beyond Hypertree Width: Decomposition Methods Without Decompositions / Hubie Chen, Victor Dalmau -- Ad-hoc Global Constraints For Life / Kenil C.k. Cheng, Roland H.c. Yap -- Tractable Clones Of Polynomials Over Semigroups / Victor Dalmau, Ricard Gavalda, Pacal Tesson, Denis Therien --^ Cp (graph): Introducing A Graph Computation Domain In Constraint Programming / Gregoire Dooms, Yves Deville, Pierre Dupont -- Interval Analysis In Scheduling / Jerome Fortin, Pawel Zielinski, Didier Dubois, Helene Fargier -- Assumption-based Pruning In Conditional Csp / Felix Geller, Michael Veksler -- Conditional Symmetry Breaking / Ian P. Gent, Tom Kelsey, Steve A. Linton, Iain Mcdonald, Ian Miguel, Barbara M. Smith -- Symmetry And Consistency / Ian P. Gent, Tom Kelsey, Steve Linton, Colva Roney-dougal -- Solving The Molr And Social Golfers Problems / Warwick Harvey, Thorsten Winterer -- Advances In Polytime Isomorph Elimination For Configuration / Laurent Henocque, Mathias Kleiner, Nicolas Prcovic -- Planning And Scheduling To Minimize Tardiness / J.n. Hooker -- Search Heuristics And Heavy-tailed Behavior / Tudor Hulubei, Barry O'sullivan -- 2-way Vs. D-way Branching For Csp / Joey Hwang, David G. Mitchell --^ Maintaining Longest Paths In Cyclic Graphs / Irit Katriel, Pascal Van Hentenryck -- Applying Constraint Programming To Rigid Body Protein Docking / Ludwig Krippahl, Pedro Barahona -- Maximum Constraint Satisfaction On Diamonds / Andrei Krokhin, Benoit Larose -- Exploiting Unit Propagation To Compute Lower Bounds In Branch And Bound Max-sat Solvers / Chu Min Li, Felip Manya, Jordi Planes -- Generalized Conflict Learning For Hybrid Discrete/linear Optimization / Hui Li, Brian Williams -- Parallel Local Search In Comet / Laurent Michel, Pascal Van Hentenryck -- Generating Corrective Explanations For Interactive Constraint Satisfaction / Barry O'callaghan, Barry O'sullivan, Eugene C. Freuder -- Spread: A Balancing Constraint Based On Statistics / Gilles Pesant, Jean-charles Regin -- Automatic Detection Of Variable And Value Symmetries ; Breaking All Value Symmetries In Surjection Problems / Jean-francois Puget. Ac-*: A Configurable, Generic And Adaptive Arc Consistency Algorithm ; Maintaining Arc Consistency Algorithms During The Search Without Additional Space Cost / Jean-charles Regin -- Weak Composition For Qualitative Spatial And Temporal Reasoning / Jochen Renz, Gerard Ligozat -- Boosting Distributed Constraint Satisfaction / Georg Ringwelski, Youssef Hamadi -- Depth-first Mini-bucket Elimination / Emma Rollon, Javier Larrosa -- Using Sat In Qbf / Horst Samulowitz, Fahiem Bacchus -- Tree Decomposition With Function Filtering / Marti Sanchez, Javier Larrosa, Pedro Meseguer -- On Solving Soft Temporal Constraints Using Sat Techniques / Hossein M. Sheini, Bart Peintner, Karem A. Sakallah, Martha E. Pollack -- Eplex: Harnessing Mathematical Programming Solvers For Constraint Logic Programming / Kish Shen, Joachim Schimpt -- Caching Search States In Permutation Problems / Barbara M. Smith -- Repair-based Methods For Quantified Scps / Kostas Stergious --^ Handling Implication And Universal Quantification Constraints In Flux / Michael Thielscher -- Solving Simple Planning Problems With More Inference And No Search / Vincent Vidal, Hector Geffner -- Solving Large-scale Nonlinear Programming Problems By Constraint Partitioning / Benjamin W. Wah, Yixin Chen -- Factor Analytic Studies Of Csp Heuristics / Richard J. Wallace -- Short Papers. Lookahead Saturation With Restriction For Sat / Anbulagan, John Slaney -- Evolving Variable-ordering Heuristics For Constrained Optimisation / Stuart Bain, John Thornton, Abdul Sattar -- Multi-point Constructive Search / J. Christopher Beck -- Bounds Of Graph Characteristics / Nicolas Beldiceanu, Thierry Petit, Guillaume Rochart -- Acquiring Parameters Of Implied Global Constraints / Christian Bessiere, Remi Coletta, Thierry Petit -- Integrating Benders Decomposition Within Constraint Programming / Hadrien Cambazard, Narendra Jussien --^ Using Boolean Constraint Propagation For Sub-clauses Deduction / S. Darras, G. Dequen, L. Devendeville, B. Mazure, R. Ostrowski, L. Sais -- Extending Systematic Local Search For Job Shop Scheduling Problems / Bistra Dilkina, Lei Duan, William S. Havens -- Interactive Reconfiguration In Power Supply Restoration / Tarik Hadzic, Henrik Reif Andersen -- Neighbourhood Clause Weight Redistribution In Local Search For Sat / Abdelraouf Ishtaiwi, John Thornton, Abdul Sattar, Duc Nhgia Pham -- Computing And Exploiting Tree-decompositions For Solving Constraint Networks / Philippe Jegou, Samba Ndojh Ndiaye, Cyril Terrioux -- Encoding Requests To Web Service Compositions As Constraints / Alexander Lazovik, Marco Aiello, Rosella Gennari -- Test Instance Generation For Max 2sat / Mistuo Motoki -- Consistency For Quantified Constraint Satisfaction Problems / Peter Nightingale -- Alternate Modeling In Sport Scheduling / Laurent Perron --^ Approximations In Distributed Optimization / Adrian Petcu, Boi Faltings -- Extremal Csps / Nicolas Prcovic -- Beyond Finite Domains: The All Different And Global Cardinality Constraints / Claude-guy Quimper, Toby Walsh -- Views And Iterators For Generic Constraint Implementations / Christian Schulte, Guido Tack -- Approximated Consistency For The Automatic Recording Problem / Meinolf Sellmann -- Towards An Optimal Cnf Encoding Of Boolean Cardinality Constraints / Carsten Sinz -- Approximate Constrained Subgraph Matching / Stephane Zampelli, Yves Deville, Pierre Dupont. Doctoral Papers. Distributed Constraints For Large-scale Scheduling Problems / Montserrat Abril, Miguel A. Salido, Federico Barber -- Solving Over-constrained Problems With Sat / Josep Argelich, Felip Manya -- A Constraint Based Agent For Tac-scm / David A. Burke, Kenneth N. Brown -- Solving The Car-sequencing Problem As A Non-binary Csp / Mihaela Butaru, Zineb Habbas -- Dimensioning An Inbound Call Center Using Constraint Programming / Cyril Canon, Jean-charles Billaut, Jean-louis Bouquard -- Methods To Learn Abstract Scheduling Models / Tom Carchrae, J. Christopher Beck, Eugene C. Freuder -- Automated Search For Heuristic Functions / Pavel Cejnar, Roman Bartak -- Constraint-based Inference: A Bridge Between Constraint Processing And Probability Inference / Le Chang, Alan K. Mackworth -- Scheduling Social Tournaments / Ivan Dotu, Alvaro Del Val, Pascal Van Hentenryck -- Domain Reduction For The Circuit Constraint / Latife Genc Kaya, John Hooker --^ Using Constraint Programming For Solving Distance Csp With Uncertainty / Carlos Grandon, Bertrand Neveu -- Improved Algorithm For Finding (a, B)-super Solutions / Emmanuel Hebgrard, Toby Walsh -- Local Consistency In Weighted Csps And Inference In Max-sat / Federico Heras, Javier Larrosa -- Modeling Constraint Programs With Software Technology Standards / Matthias Hoche, Stefan Jahnichen -- Solution Equivalent Subquadrangle Reformulations Of Constraint Satisfaction Problems / Chris Houghton, David Cohen -- Mechanism Design For Preference Aggregationover Coalitions / Eric Hsu, Sheila Mcilraith -- Lp As A Global Search Heuristic Across Different Constrainedness Regions / Lucian Leahu, Carla Gomes -- Consistency For Partially Defined Constraints / Andrei Legtchenko, Arnaud Lallouet -- Subnet Generation Problem: A New Network Routing Problem / Cheuk Fun Bede Leung, Barry Richards, Olli Kamarainen -- Partial Redundant Modeling / Tiziana Ligorio, Susan L. Epstein --^ And / Or Branch-and-bound For Solving Mixed Integer Linear Programming Problems / Radu Marinescu, Rina Dechter -- Weak Symmetries In Problem Formulations / Roland Martin, Karsten Weihe -- Towards The Systematic Generation Of Channelling Constraints / B. Martinez-hernandez, A.m. Frisch -- And / Or Search Spaces And The Semantic Width Of Constraint Networks / Robert Mateescu, Rina Dechter -- Statistical Modelling Of Csp Solving Algorithms Performance / Carles Mateu, Ramon Bejar, Cesar Fernandez -- Probabilistic Arc Consistency / Deepak Mehta, M.r.c. Van Dongen -- Goose -- A Generic Object-oriented Search Environment / Henry Muller, Stefan Jahnichen -- Randomization For Multi-agent Constraint Optimization / Quang Huy Nguyen, Boi V. Faltings -- Uncertainty In Soft Constraint Problems / Maria Silvia Pini, Francesca Rossi -- Speeding Up Constrained Path Solvers With A Reachability Propagator / Luis Quesada, Peter Van Roy, Yves Deville --^ From Linear Relaxations To Global Constraint Propagation / Glaude-guy Quimper, Alejandoro Lopez-ortiz -- Encoding Htn Planning As A Dynamic Csp / Pavel Surynek, Roman Bartak -- Specialised Constraints For Stable Matching Problems / Chris Unsworth, Patrick Prosser -- Bounds-consistent Local Search / Stefania Verachi, Steven Prestwich -- Robust Constraint Solving Using Multiple Heuristics / Alfio Vidotto, Kenneth N. Brown, J. Christopher Beck -- Scheduling With Uncertain Start Dates / Christine Wei Wu, Kenneth N. Brown, J. Christopher Beck -- The Role Of Redundant Clauses In Solving Satisfiability Problems / Honglei Zeng, Sheila Mcilraith -- Applying Decompostion Methods To Crossword Puzzle Problems / Yaling Zheng, Berthe Y. Choueiry -- Asymmetric Distributed Constraints Satisfaction Problems / Roie Zivan, Amnon Meisels -- Full Arc Consistency In Wcsp And In Constraint Hierarchies With Finite Domains / Josef Zlomek, Roman Bartak. System Demonstrations. Cojava: A Unified Language For Simulation And Optimization / Alexander Brodsky, Hadon Nash -- Programming With Toy(fd) / Antonio J. Fernandez, Teresa Hortala-gonzalez, Fernando Saenz-perez -- Computing Super-schedules / Emmanuel Hebrard, Paul Tyler, Toby Walsh -- Proterv-ii: An Integrated Production Planning And Scheduling System / Andras Kovacs, Peter Egri, Tamas Kis, Jozsef Vancza -- The Comet Programming Language And System / Laurent Michel, Pascal Van Hentenryck -- Random Stimuli Generation For Functional Hardware Verification As A Cp Application / Yehuda Naveh, Roy Emek -- A Bdd-based Interactive Configurator For Modular Systems / Erik R. Van Der Meer. Peter Van Beek (ed.). Includes Bibliographical References And Index. Also Issued Online. 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 -