Principles and Practice of Constraint Programming : 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014, Proceedings / / edited by Barry O'Sullivan

• Pubblicazione: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014
• Edizione: 1st ed. 2014.
• Descrizione fisica: 1 online resource (XXVI, 944 p. 228 illus.)
• Disciplina: 005.11
• Soggetto topico: Mathematical logic; Computer science—Mathematics; Artificial intelligence; Algorithms; Mathematical Logic and Formal Languages; Mathematics of Computing; Artificial Intelligence; Algorithm Analysis and Problem Complexity
• Persona (resp. second.): O'SullivanBarry
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Intro -- Preface -- Prize-Winning Papers -- Tutorials and Workshops -- Conference Organization -- The Association for Constraint Programming -- Table of Contents -- Invited Talks -- A Modular Architecture for Hybrid Planning with Theories -- References -- Teaching Constraint Programming -- One Problem, Two Structures, Six Solvers, and Ten Years of Personnel Scheduling -- References -- Concurrent Constraint Programming Research Programmes - Redux -- References -- Best Technical Track Paper -- On Broken Triangles -- 1 Introduction -- 2 Value Merging in Binary CSP Based on the BTP -- 3 Experimental Trials -- 4 Generalising BTP-Merging to Constraints of Arbitrary Arity -- 5 A Tractable Class of General-Arity CSP -- 5.1 Directional General-Arity BTP -- 5.2 Merging -- 5.3 Tractability of DGABTP for a Known Variable Ordering -- 5.4 Finding a DGABTP Variable Ordering Is NP-Hard -- 6 Conclusion -- References -- Best Application Track Paper -- Using CP in Automatic Test Generation for ABB Robotics' Paint Control System -- 1 Introduction -- 2 Robotized Painting -- 2.1 Example of Robotized Painting -- 3 Testing the IPS -- 3.1 Continuous Integration -- 3.2 Testing in a CI Environment -- 4 CP Model of the IPS -- 4.1 Decision Variables and Domains -- 4.2 Test Scenarios -- 4.3 Avoiding Trivial and Enforcing Diversity -- 4.4 Search and Optimization -- 4.5 Search Heuristics -- 5 Implementation and Exploitation -- 5.1 Selection of CP and the CP Solver -- 5.2 Overall Implementation -- 5.3 Execution of the Model -- 5.4 Using the Flexibility of CP -- 5.5 Performance of Model -- 6 Lessons Learned and Conclusions -- 6.2 Actual Defects Found with the CP Model -- 6.3 Return on Investment with the Use of CP -- 6.4 Further Work -- References -- Best Student Paper -- On Compiling CNF into Decision-DNNF -- 1 Introduction -- 2 Technical Preliminaries. ; 3 Compiling CNFs into Decision-DNNFs -- 3.1 Decision-DNNF -- 3.2 Decision Vtrees -- 3.3 A Compilation Algorithm -- 3.4 Decision-Width -- 3.5 Relationship to Treewidth -- 4 Decision-DNNFs and Model Counters -- 5 From Decision-DNNF to SDD -- 6 Related Work -- 7 Conclusion -- References -- Runner-Up Best Student Paper -- A Complete Solver for Constraint Games -- 1 Introduction -- 2 Constraint Games -- 3 Modeling with Constraint Games -- 4 Pruning Techniques -- 5 An Algorithm for Nash Equilibrium Enumeration -- 6 Experiments -- 7 Conclusion -- References -- Technical Track -- Encoding Linear Constraints into SAT -- 1 Introduction -- 2 Preliminaries -- 2.1 SAT Solving -- 2.2 LCG and LD Solvers -- 2.3 Order and Logarithmic Encoding -- 2.4 Multi Decision Diagrams -- 3 Linear Integer Constraints -- 4 Construction of the MDD -- 5 Encoding MDDs into CNF -- 6 Optimization Problems -- 7 Improvements -- 7.1 Grouping Identical Coefficients -- 7.2 Removing Subsumed Clauses -- 7.3 Solution Phase Saving -- 7.4 Lazy Decomposition -- 8 Related Work and Extensions -- 9 Experimental Results -- 9.1 Multiple Knapsack -- 9.2 RCPSP -- 9.3 Graph Coloring -- 9.4 Sport Leagues Scheduling -- 10 Conclusion -- References -- Efficient Application of Max-SAT Resolution on Inconsistent Subsets -- 1 Introduction -- 2 Formalism and Definitions -- 3 Max-SAT Resolution -- 4 Transforming Inconsistent Subsets -- 5 Improved Transformation of Inconsistent Subsets -- 6 Experimental Study -- 7 Conclusion -- References -- Sequential Time Splitting and Bounds Communication for a Portfolio of Optimization Solvers -- 1 Introduction and Related Work -- 2 Solving Behaviour and Timesplit Solvers -- 3 Splitting Selection and Evaluation -- 3.1 Evaluation Metrics -- 3.2 TimeSplit Algorithm -- 3.3 TimeSplit Evaluation -- 4 Timesplit Portfolio Solvers -- 4.1 Static Splitting -- 4.2 Dynamic Splitting. ; 5 Empirical Evaluation -- 5.1 Test Results -- 6 Conclusions and Future Work -- References -- Scoring-Based Neighborhood Dominance for the Subgraph Isomorphism Problem -- 1 Introduction -- 2 CP for the Subgraph Isomorphism Problem -- 2.1 Technical Background -- 2.2 Isomorphism Model and Filtering Procedures -- 3 Scoring-Based Neighborhood Dominance -- 3.1 Principle and Correctness -- 3.2 Filtering SND Constraints -- 3.3 Simplifying the Target Graph -- 4 Theoretical Filtering Comparisons -- 5 A Weak SND Algorithm -- 6 Experimental Results -- 7 Conclusion -- References -- Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators -- 1 Introduction -- 2 Background: Automata with Accumulators -- 3 Reverse Constraints and Glue Constraints -- 3.1 The Reverse of a Constraint -- 3.2 Glue Constraints -- 3.3 Deriving the Glue Constraint -- 4 Implied Constraints on Prefixes and Suffixes -- 5 Experiments -- 6 Constant-Time Move Probing in Local Search -- 7 Conclusion -- References -- The Propagation Depth of Local Consistency -- 1 Introduction -- 2 Preliminaries -- 2.1 CSP-Refutations -- 2.2 Results and Related Work -- 2.3 The Existential Pebble Game -- 3 The Construction -- 3.1 Overview of the Construction -- 3.2 The Gadgets -- 3.3 Proof of Theorem 1 -- 4 Conclusion -- References -- The Balance Constraint Family -- 1 Introduction -- 2 Background -- 3 The Balance Constraint Family -- 4 Decompositions -- 4.1 Constraints Implied by ALLBALANCE -- 4.2 Special Cases of ALLBALANCE -- 5 A Filtering Algorithm for ATMOSTALLBALANCE -- 5.1 Finding a Support -- 5.2 Filtering the Domains -- 6 Related Work -- 7 Experimental Results -- 7.1 Balanced Academic Curriculum Problem (BACP) -- 7.2 Shift Scheduling -- 8 Conclusions -- References. ; Experimental Comparison of BTD and Intelligent Backtracking: Towards an Automatic Per-instance Algorithm Selector -- 1 Introduction -- 2 Generic Framework for Binary CSPs -- 3 Experimental Comparison -- 4 Per-instance Algorithm Selector -- 4.1 Basic Framework of the Selector -- 4.2 Selection of a Subset of Solvers -- 5 Experimental Evaluation -- 6 Conclusion -- References -- Solving Intensional Weighted CSPs by Incremental Optimization with BDDs -- 1 Introduction -- 2 Preliminaries -- 2.1 WCSPs and COPs -- 2.2 SMT and Weighted SMT -- 2.3 Solving WCSP with (Weighted) SMT -- 3 Binary Decision Diagrams -- 3.1 SAT Encodings of Pseudo-Boolean Constraints Using BDDs -- 4 Solving WCSPs by Incremental Optimization Using Shared ROBDDs -- 4.1 Incremental Optimization Algorithm -- 5 Benchmarking -- 5.1 WSimply Solving Methods Comparison -- 5.2 SBDD-Based versus State-of-the-Art CSP and WCSP Solvers -- 5.3 SBDD Incrementality -- 6 Conclusions and Future Work -- References -- On Backdoors to Tractable Constraint Languages -- 1 Introduction -- 2 Preliminaries -- 3 General Hardness -- 3.1 Hardness on Bounded Arity CSPs -- 3.2 Hardness When the Parameter Is the Size of the Backdoor -- 4 Combined Parameters: Helly Classes and Limits -- 5 Related Work -- 6 Conclusion -- References -- Nested Constraint Programs -- 1 Introduction -- 2 Preliminaries -- 3 Aggregators and Nested Constraint Programs -- 4 Solving NCP's -- 4.1 Complexity -- 4.2 Learning for NCPs -- 5 Experiments -- 6 Related Work -- 7 Conclusion -- References -- Beyond Consistency and Substitutability -- 1 Introduction -- 2 Value Elimination -- 3 Variable Elimination -- 4 Practical Considerations -- 5 Recovering All Solutions -- 6 Theoretical Discussion -- 7 Conclusion -- References -- Subexponential Time Complexity of CSP with Global Constraints -- 1 Introduction -- 2 Preliminaries -- 2.1 CSP. ; 2.2 Global Constraints -- 2.3 Subexponential Time Complexity -- 3 The Problem CSP= -- 4 The Problems CSP=, CSP≥, and CSP≤ -- 5 The Problem CSPc -- 6 Conclusion -- References -- A New Characterization of Relevant Intervals for Energetic Reasoning -- 1 Introduction -- 2 Background -- 3 The Energetic Reasoning Checker Revisited -- 4 Characterization of Intervals for the Propagator -- 5 Algorithms and Experiments -- 5.1 Checker -- 5.2 Propagator -- 5.3 Experiments -- 6 Discussion and Conclusion -- References -- A Declarative Paradigm for Robust Cumulative Scheduling -- 1 Introduction -- 2 Robust Cumulative Scheduling -- 3 Filtering Technique -- 4 Experiments with Side Constraints -- 5 Conclusion -- References -- Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems -- 1 Introduction -- 2 Background -- 2.1 Distributed Constraint Optimization Problems (DCOPs) -- 2.2 Distributed Pseudo-Tree Optimization Procedure (DPOP) -- 3 Branch-Consistent DPOP (BrC-DPOP) -- 3.1 Preliminaries -- 3.2 High-Level Algorithm Description -- 3.3 Messages and Data Structures -- 3.4 Algorithm Description -- 4 Theoretical Analysis -- 5 Related Work -- 6 Experimental Results -- 7 Conclusions and Future Work -- References -- Constraint-Based Lagrangian Relaxation -- 1 Introduction -- 2 Generalized Lagrangian Relaxation -- 2.1 Violation and Satisfiability Degrees -- 2.2 Generalized Lagrangian Relaxations -- 3 Generalized Lagrangian Duals -- 4 Generalized Lagrangian Primal Methods -- 5 Practical Implementation -- 6 Empirical Results -- 6.1 Graph Coloring -- 6.2 GLR versus SLR -- 6.3 Primal Lagrangian Tabu Search -- 7 Related Work -- 8 Conclusion -- References -- Loop Untangling -- 1 Introduction -- 2 Motivating Examples -- 3 General Loop Untangling Technique -- 3.1 Programs as Ordered State Changes and State Queries -- 3.2 Flattening. ; 3.3 Creating Iterations.
• Sommario/riassunto: This book constitutes the refereed conference proceedings of the 20th International Conference on Principles and Practice of Constraint Programming, CP 2014, held in Lyon, France, in September 2014. The 65 revised papers presented together with 4 invited talks were carefully selected from 108 submissions. The scope of CP 2014 includes all aspects of computing with constraints, including theory, algorithms, environments, languages, models, systems, and applications such as decision making, resource allocation, and agreement technologies.
• Titolo autorizzato: Principles and Practice of Constraint Programming
• ISBN: 3-319-10428-4
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910483772803321
• Lo trovi qui: Univ. Federico II
• Serie: Programming and Software Engineering ; ; 8656