Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Principles and Practice of Constraint Programming [[electronic resource] ] : 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings / / edited by Gilles Pesant
| Principles and Practice of Constraint Programming [[electronic resource] ] : 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings / / edited by Gilles Pesant |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XXIV, 747 p. 191 illus.) |
| Disciplina | 005.11 |
| Collana | Programming and Software Engineering |
| 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 |
| ISBN | 3-319-23219-3 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- 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.
2 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). 3.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. 4 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. 3.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. 1.1 Related Work. |
| Record Nr. | UNISA-996200363903316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Principles and Practice of Constraint Programming : 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings / / edited by Gilles Pesant
| Principles and Practice of Constraint Programming : 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings / / edited by Gilles Pesant |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XXIV, 747 p. 191 illus.) |
| Disciplina | 005.11 |
| Collana | Programming and Software Engineering |
| 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 |
| ISBN | 3-319-23219-3 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- 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.
2 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). 3.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. 4 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. 3.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. 1.1 Related Work. |
| Record Nr. | UNINA-9910484000103321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||