LEADER 13054nam 22007815 450 001 996200363903316 005 20200706033139.0 010 $a3-319-23219-3 024 7 $a10.1007/978-3-319-23219-5 035 $a(CKB)3890000000001375 035 $a(SSID)ssj0001558616 035 $a(PQKBManifestationID)16184132 035 $a(PQKBTitleCode)TC0001558616 035 $a(PQKBWorkID)14818663 035 $a(PQKB)11592264 035 $a(DE-He213)978-3-319-23219-5 035 $a(MiAaPQ)EBC6281285 035 $a(MiAaPQ)EBC5577868 035 $a(Au-PeEL)EBL5577868 035 $a(OCoLC)918984310 035 $a(PPN)188460829 035 $a(EXLCZ)993890000000001375 100 $a20150812d2015 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aPrinciples and Practice of Constraint Programming$b[electronic resource] $e21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings /$fedited by Gilles Pesant 205 $a1st ed. 2015. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2015. 215 $a1 online resource (XXIV, 747 p. 191 illus.) 225 1 $aProgramming and Software Engineering ;$v9255 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-319-23218-5 327 $aIntro -- Preface -- Tutorials and Workshops -- Conference Organization -- Invited Talks -- Constraint-based Problems and Solutionsin the Global Enterprise -- Industrial Success Stories of ASP and CP:What's Still Open? -- Synthesis of Constraint Solvers -- Contents -- Technical Track -- Encoding Linear Constraints with Implication Chains to CNF -- 1 Introduction -- 2 Preliminaries -- 2.1 SAT Solving -- 2.2 Multi Decision Diagrams -- 3 Pseudo Boolean Constraints and Chains -- 4 Translating Through MDDs with Chains -- 4.1 Preliminaries for the Construction -- 4.2 Algorithm and Properties of the Construction -- 5 Experiments -- 6 Conclusion and Future Work -- References -- Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP -- 1 Introduction -- 2 Background -- 3 Hybrid Best-First Search -- 3.1 Related Work -- 4 Hybrid Best-First Search and Tree Decompositions -- 4.1 Using HBFS in BTD -- 4.2 Related Work -- 5 Experimental Results -- 5.1 Proving Optimality -- 5.2 Anytime Behavior -- 6 Conclusions -- References -- Improved Constraint Propagation via Lagrangian Decomposition -- 1 Introduction -- 2 Related Work -- 3 Lagrangian Decomposition -- 4 Application to Constraint Programming -- 5 Application: Multiple Alldifferent Constraints -- 6 Application: Set Covering -- 7 Conclusion -- References -- Strengthening Convex Relaxations with Bound Tightening for Power Network Optimization -- 1 Introduction -- 2 AC Power Flow -- 3 The Quadratic Convex (QC) Relaxation -- 4 Consistency of Constraint Relaxation Networks -- 4.1 Relation to Concepts in Global Optimization -- 5 Constraint Relaxation Networks for Power Flows -- 6 Strength and Performance of the Bound Tightening -- 7 Application to AC Optimal Power Flow -- 8 Propagation with Load Uncertainty -- 9 Conclusion -- References -- Broken Triangles Revisited -- 1 Introduction. 327 $a2 Mixing Arc Consistency and BTP-merging -- 3 The Order of BTP-mergings -- 4 Optimal Sequence of BTP-mergings at a Single Variable -- 5 Virtual Interchangeability and Neighbourhood Substitution -- 6 Conclusion -- References -- A Microstructure-Based Family of Tractable Classes for CSPs -- 1 Introduction -- 2 Background -- 3 k-BTP: Definition and Properties -- 4 Relationship with Some Tractable Classes -- 5 Experiments -- 5.1 Instances Belonging to Tractable Classes -- 5.2 Link Between Efficient Solving and Belonging to Tractable Classes -- 6 Conclusion -- References -- The Unary Resource with Transition Times -- 1 Introduction -- 2 Background -- 2.1 Related Work -- 2.2 Unary Resource Propagators in CP -- 3 Transition Times Extension Requirements -- 4 Lower Bound of Transitions Times -- 5 Extending the -tree with Transition Times -- 6 Disjunctive Propagation Algorithms with Transition Times -- 6.1 Extension of Classic Unary Resource Propagation Algorithms -- 6.2 Detectable Precedences Propagation Example -- 7 Evaluation -- 8 Conclusion -- References -- A Global Constraint for a Tractable Class of Temporal Optimization Problems -- 1 Introduction -- 2 Background -- 2.1 Temporal Constraint Networks -- 2.2 Constraint Programming (CP) -- 3 The ExistAllen Constraint -- 3.1 Basic Filtering: One Relation, One Task, One Interval -- 3.2 A First Propagator -- 3.3 A Linear Propagator -- 3.4 Improvements -- 4 Evaluation -- 4.1 Problem Description -- 4.2 Benchmark -- 5 Conclusion -- References -- Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming -- 1 Introduction -- 2 Background -- 2.1 Centralized Constraint Optimization Problems (COPs) -- 2.2 Distributed Constraint Optimization Problems (DCOPs) -- 2.3 Graphical Processing Units (GPUs) -- 3 GPU-Based (Distributed) Bucket Elimination (GPU-(D)BE). 327 $a3.1 GPU Data Structures -- 3.2 Parallel Aggregate and Project Operations -- 3.3 General Observations -- 4 Related Work -- 5 Experimental Results -- 6 Conclusions and Discussions -- References -- Conflict Ordering Search for Scheduling Problems -- 1 Introduction -- 2 Related Works -- 3 Guiding Search by Timestamping Conflicts -- 3.1 Background -- 3.2 Conflict Ordering -- 3.3 Restarts and Timestamp Ordering -- 3.4 Differences with Last Conflict Search -- 4 Experiments -- 4.1 Branch-and-Bound -- 4.2 Branch-and-Bound with Restarts -- 4.3 Destructive Lower Bounds. -- 5 Conclusion -- References -- Simple and Scalable Time-Table Filtering for the Cumulative Constraint -- 1 Preliminaries -- 2 Existing Algorithms for Time-Tabling -- 3 A Linear Time-Table Filtering Algorithm -- 4 An Efficient O(n2) Time-Table Filtering -- 5 Experiments -- 6 Conclusion -- References -- General Bounding Mechanism for Constraint Programs -- 1 Introduction -- 2 Related Work -- 2.1 Lagrangian Decomposition -- 2.2 Knapsack and Regular Constraints -- 3 Proposed Approach -- 3.1 Lagrangian Decomposition -- 3.2 The Knapsack Constraint -- 3.3 The Regular Constraint -- 3.4 The Subgradient Procedure -- 4 Computational Results -- 4.1 Results for MKP -- 4.2 Results for SSP -- 5 Conclusions and Future Work -- References -- Smallest MUS Extraction with Minimal Hitting Set Dualization -- 1 Introduction -- 2 Preliminaries -- 3 Basic Algorithm -- 4 Additional Details -- 4.1 Reducing the Number of SAT Calls -- 4.2 Disjoint MCS Enumeration -- 4.3 Finding Approximate Solutions -- 5 Experimental Results -- 6 Conclusion -- References -- Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs -- 1 Introduction -- 2 Preliminaries -- 2.1 Constraint Satisfaction -- 2.2 First-Order Definable Relations -- 3 Fundamental Algorithms -- 3.1 Branching on Disjuncts -- 3.2 Sparsification. 327 $a4 Improved Upper Bounds -- 4.1 Structure Enumeration -- 4.2 Equality Constraint Languages -- 4.3 Temporal Constraint Reasoning -- 5 Lower Bounds -- 5.1 Lower Bounds for JEPD Languages -- 5.2 Lower Bounds for Allen's Interval Algebra -- 6 Discussion -- References -- Generalized Totalizer Encoding for Pseudo-Boolean Constraints -- 1 Introduction -- 2 Generalized Totalizer Encoding -- 3 Related Work -- 4 Implementation and Evaluation -- 5 Conclusion -- References -- Smaller Selection Networks for Cardinality Constraints Encoding -- 1 Introduction -- 2 Preliminaries -- 3 Pairwise and Bitonic Selection Networks -- 4 New Smaller Selection Networks -- 5 Sizes of New Selection Networks -- 6 Arc-Consistency of Selection Networks -- 7 Conclusions -- References -- PREFIX-PROJECTION Global Constraint for Sequential Pattern Mining -- 1 Introduction -- 2 Preliminaries -- 2.1 Sequential Patterns -- 2.2 SPM under Constraints -- 2.3 Projected Databases -- 2.4 CSP and Global Constraints -- 3 Related Works -- 3.1 Ad hoc Methods for SPM -- 3.2 CP Methods for SPM -- 4 PREFIX-PROJECTION Global Constraint -- 4.1 A Concise Encoding -- 4.2 Definition and Consistency Checking -- 4.3 Building the Projected Databases -- 4.4 Filtering -- 4.5 Encoding of SPM Constraints -- 5 Experimental Evaluation -- 6 Conclusion -- References -- On Tree-Preserving Constraints -- 1 Introduction -- 2 Preliminaries -- 3 Chain-Preserving Constraints -- 4 Path-Preserving Constraints -- 5 Tree-Preserving Constraints -- 5.1 Enforcing Arc- and Path-Consistency Preserves Tree-Preserving -- 5.2 Partial Path-Consistency -- 6 Tree-Preserving Constraints and the Scene Labelling Problem -- 7 Further Discussion and Conclusion -- References -- Modeling and Solving Project Scheduling with Calendars -- 1 Introduction -- 2 Problem Description -- 3 Models for RCPSP/max-cal. 327 $a3.1 Model timeidx (Time Indexed Formulation) -- 3.2 Model 2cap (Doubling Resource Capacity) -- 3.3 Model addtasks (Adding Split Tasks) -- 3.4 Model cumucal (Global Calendar Propagator) -- 3.5 Time Granularity Considerations -- 4 Experiments and Conclusion -- 4.1 Comparing Search Strategies -- 4.2 Comparing Models -- 4.3 Comparing Solvers -- Deterministic Estimation of the Expected Makespan of a POS Under Duration Uncertainty -- 1 Introduction -- 2 Expected Makespan with Worst-Case Distribution -- 3 Estimating Ewc[T(D)] -- 4 Concluding Remarks -- 5 Appendix A -- References -- A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs -- 1 Introduction -- 2 Definitions, Notation, and a Proposition -- 3 A New Algorithm -- 3.1 Preprocessing and Initialisation -- 3.2 Search and Inference -- 3.3 Bit- and Thread-Parallelism -- 4 Experimental Evaluation -- 4.1 Comparison with Other Solvers -- 4.2 Parallelism -- 4.3 Effects of Backjumping -- 4.4 Comparing All-Different Propagators -- 5 Conclusion -- References -- Automated Auxiliary Variable Elimination Through On-the-Fly Propagator Generation -- 1 Introduction -- 2 Preliminaries -- 2.1 MiniZinc and FlatZinc -- 2.2 Patterns, Occurrences, and Extensions -- 2.3 Indexicals -- 3 Our Approach -- 3.1 Identification of Frequent Patterns -- 3.2 Pattern Instantiation -- 3.3 Indexical Propagator Description Generation and Compilation -- 4 Example: Ship Schedule -- 5 Experimental Evaluation -- 6 Discussion -- 6.1 Related Work -- 6.2 Properties and Extensions -- 7 Conclusion -- References -- Automatically Improving SAT Encoding of Constraint Problems Through Common Subexpression Elimination in Savile Row -- 1 Introduction -- 2 CSE for SAT Encoding -- 3 Experimental Evaluation -- 4 Conclusion -- References -- Exact Sampling for Regular and Markov Constraints with Belief Propagation -- 1 Introduction. 327 $a1.1 Related Work. 330 $aThis book constitutes the refereed conference proceedings of the 21st International Conference on Principles and Practice of Constraint Programming, CP 2015, held in Cork, Ireland, in August/September 2015. This edition of the conference was part of George Boole 200, a celebration of the life and work of George Boole who was born in 1815 and worked at the University College of Cork. It was also co-located with the 31st International Conference on Logic Programming (ICLP 2015). The 48 revised papers presented together with 3 invited talks and 16 abstract papers were carefully selected from numerous 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, schedulling, configuration, and planning. 410 0$aProgramming and Software Engineering ;$v9255 606 $aMathematical logic 606 $aComputer science?Mathematics 606 $aArtificial intelligence 606 $aAlgorithms 606 $aMathematical Logic and Formal Languages$3https://scigraph.springernature.com/ontologies/product-market-codes/I16048 606 $aMathematics of Computing$3https://scigraph.springernature.com/ontologies/product-market-codes/I17001 606 $aArtificial Intelligence$3https://scigraph.springernature.com/ontologies/product-market-codes/I21000 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 615 0$aMathematical logic. 615 0$aComputer science?Mathematics. 615 0$aArtificial intelligence. 615 0$aAlgorithms. 615 14$aMathematical Logic and Formal Languages. 615 24$aMathematics of Computing. 615 24$aArtificial Intelligence. 615 24$aAlgorithm Analysis and Problem Complexity. 676 $a005.11 702 $aPesant$b Gilles$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996200363903316 996 $aPrinciples and Practice of Constraint Programming$9774019 997 $aUNISA