دانلود کتاب Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, ... (Lecture Notes in Computer Science, 12735)

فهرست مطالب :

Preface
Organization
Abstracts
Why You Should Constrain Your Machine Learned Models
Contextual Optimization: Bridging Machine Learning and Operations
Complete Symmetry Breaking Constraints for the Class of Uniquely Hamiltonian Graphs
Variable Ordering for Decision Diagrams: A Portfolio ApproachoŽ
Contents
Supercharging Plant Configurations Using Z3
1 Introduction
1.1 Complexity Without Perplexity
1.2 Domain Engineering - Deep Cleaning
1.3 Solver Engineering - Deep Solving
2 Virtual Plant Configurations
2.1 Domains
2.2 A Formalization of Domain Constraints
2.3 Objectives
2.4 Solvable Formalizations
3 Experiences with Domain Engineering
3.1 Model Visualization
3.2 Checking Global Model Invariants
3.3 Root-Cause Analysis Using Unsatisfiable Cores
4 Experiences with Solver Engineering
4.1 SMT Theories and Solvers
4.2 Uninterpreted Functions
4.3 Bit-Vectors
4.4 Constraints as Code
4.5 Solving for Multiple Objectives
5 Experiences with MiniZinc
6 Perspective
References
A Computational Study of Constraint Programming Approaches for Resource-Constrained Project Scheduling with Autonomous Learning Effects
1 Introduction
2 Optimization Model
3 Constraint Programming Formulations
4 Relaxations, Restrictions and Lower Bounding
4.1 CP-Based Lower Bounding
4.2 Relaxations
4.3 Destructive Lower Bounding
4.4 A Restriction-Based Upper Bound
5 Computational Study
5.1 CP Formulation Comparison
5.2 Lower Bounding Performance
5.3 Scheduling and Upper Bounding Efficacy
5.4 Overall Performance
5.5 Learning Potential and Benefit
5.6 Parameter Performance Impact
6 Conclusion
References
Strengthening of Feasibility Cuts in Logic-Based Benders Decomposition
1 Introduction
2 Literature Background
3 Logic-Based Benders Scheme and Cut Strengthening
3.1 Logic-Based Benders Decomposition
3.2 Cut-Strengthening Algorithms
4 Problems and Modelling
4.1 Cumulative Facility Scheduling with Fixed Costs
4.2 Single Machine Scheduling with Sequence-Dependent Setup Times and Multiple Time Windows
4.3 Vehicle Routing with Location Congestion
5 Computational Evaluation
5.1 Instances
5.2 Percentage of Solved Instances
6 Concluding Remarks
References
Learning Variable Activity Initialisation for Lazy Clause Generation Solvers
1 Introduction
2 Background
3 Approach
3.1 Machine Learning Model
4 Empirical Study
4.1 Data Sets
4.2 Experimental Configuration and Results
5 Conclusion
References
A*-Based Compilation of Relaxed Decision Diagrams for the Longest Common Subsequence Problem
1 Introduction
2 Multi-valued Decision Diagrams for the LCS Problem
3 Independent Upper Bounds
4 A*-Based Construction of MDDs
4.1 Relaxed MDDs
4.2 Further Details
5 Experimental Results
5.1 Comparison of Independent Upper Bounds
5.2 Impact of Parameters phi and beta
5.3 Main Comparison of A*C and TDC
6 Conclusions
References
Partitioning Students into Cohorts During COVID-19
1 Introduction
2 Problem Definition
3 Related Work
4 Mathematical Model
5 Application
6 Discussion
7 Conclusion
References
A Two-Stage Exact Algorithm for Optimization of Neural Network Ensemble
1 Introduction
2 Literature Review
3 Notation and Baseline Formulation
4 Two-Stage Optimization Algorithm
5 Computational Study
5.1 Instances
5.2 Results and Analysis
6 Conclusion and Future Work
References
Heavy-Tails and Randomized Restarting Beam Search in Goal-Oriented Neural Sequence Decoding
1 Introduction
2 Background
2.1 Beam Search for Goal-Oriented Neural Sequence Decoding
2.2 Heavy-Tailed Behavior and Randomization in Heuristic and Combinatorial Search Algorithms
3 Goal-Oriented Benchmark Problems
3.1 Combinatorial Routing Problems
3.2 Visual Program Synthesis
3.3 Conditional Molecular Design
4 Fat- and Heavy-Tailed Behavior in Goal-Oriented Neural Sequence Decoding
4.1 Fat- and Heavy-Tailed Behavior on a Single Instance
5 Randomized Restarting Neural-Guided Beam Search for Goal-Oriented Combinatorial Problems
5.1 Restart Strategies
6 Empirical Results
6.1 Results for the Travelling Salesman Problem (TSP)
6.2 Results for the Other Benchmarks
7 Discussion and Future Work
8 Conclusion
References
Combining Constraint Programming and Temporal Decomposition Approaches - Scheduling of an Industrial Formulation Plant
1 Introduction
2 Case Study
3 Methodology
3.1 Variables
3.2 Constraints
3.3 Moving Horizon Strategy
4 Results
5 Summary, Conclusion and Outlook
References
The Traveling Social Golfer Problem: The Case of the Volleyball Nations League
1 Introduction
2 The Traveling Social Golfer Problem (TSGP)
2.1 Definition of the TSGP
2.2 Decomposing the TSGP into Venue Assignment and Nation Assignment
3 The Complexity of Venue Assignment
4 An Integer Programming Formulation
5 Solving VNL in Practice
5.1 Do Feasible Schedules Exist?
5.2 Results
A Optimal solutions to VNL-instances
References
Towards a Compact SAT-Based Encoding of Itemset Mining Tasks
1 Introduction
2 Technical Background
2.1 Propositional Logic and SAT Problem
2.2 An Overview of Itemset Mining
3 SAT-based Encoding of Itemset Mining
4 A Compact SAT-Based Encoding
4.1 Solving Generalized Optimal Linear Arrangement Problem
5 Experimental Evaluation
6 Conclusion
References
A Pipe Routing Hybrid Approach Based on A-Star Search and Linear Programming
1 Introduction
2 Problem Definition
2.1 Routing Space
2.2 Input and Output Configurations
2.3 Straight Sections and Bends
2.4 Pipe and Polyline Approximation
2.5 Constraints
2.6 Objective Function
3 Routing Plan
3.1 Definition
3.2 Feasibility and Cost
4 Shortest Path Problem Formulation
4.1 Search Algorithms
4.2 Neighborhood
4.3 Trail Heuristic
5 Experiments
5.1 Test Cases
5.2 Results and Discussion
6 Conclusion
References
MDDs Boost Equation Solving on Discrete Dynamical Systems
1 Introduction
2 Preliminaries
2.1 Multi-valued Decision Diagrams (MDDs)
2.2 Discrete Dynamical Systems and Dynamics Graphs
3 The Abstraction on Cycles
3.1 The State-of-art Method
4 Boosting Everything up with MDDs
4.1 Equations over Dynamics Graphs
5 Experiments
6 Conclusions and Perspectives
References
Two Deadline Reduction Algorithms for Scheduling Dependent Tasks on Parallel Processors
1 Introduction
2 Notations
3 Extension of the Garey and Johnson Algorithm
3.1 Principles of Deadline Reductions
3.2 Description of the eGJ Algorithm
3.3 Complexity Analysis of eGJ
3.4 Strong Form of eGJ
4 Extension of the Leung Palem and Pnueli Algorithm
4.1 Description of the eLPP Algorithm
4.2 Weak eLPP Algorithm
4.3 Strong eLPP Algorithm
5 Experiments
5.1 Data Generation
5.2 Complexity Analysis
5.3 Output Analysis
6 Conclusions
References
Improving the Filtering of Branch-and-Bound MDD Solver
1 Introduction
2 Background
2.1 Decision Diagrams
2.2 Bounded-Size Approximations
2.3 The Dynamics of Branch-and-Bound with DDs
3 Improving the Filtering of Branch-and-Bound MDD
3.1 Local Bounds (LocB)
3.2 Rough Upper Bound (RUB)
4 Experimental Study
5 Previous Work
6 Conclusion and Future Work
References
On the Usefulness of Linear Modular Arithmetic in Constraint Programming
1 Introduction
2 Background
3 Domain Filtering for Linear Modular Constraints
3.1 Gauss-Jordan Elimination for Systems of Linear Modular Equality Constraints with a Prime Modulus
3.2 Domain Consistency for a System of Linear Modular Equality Constraints in Parametric Form
3.3 Dynamic Programming for a Single Linear Modular Constraint
4 Application to Checksums
5 Application to Model Counting
5.1 Synthetic Problem
5.2 Benchmarks from ch16GHSS07
5.3 Towards a Practical Scalable Model Counter
6 Conclusion and Future Outlook
References
Injecting Domain Knowledge in Neural Networks: A Controlled Experiment on a Constrained Problem
1 Introduction
2 Related Works and Baseline Choice
3 Basic Methods
4 Empirical Analysis
4.1 Regularization Methods Comparison and -tuning
4.2 Domain Knowledge at Training Time for Different Problem Dimensions
4.3 Training Set Size and Empirical Information
4.4 Constraint Violation Assessment
5 Conclusion
References
Learning Surrogate Functions for the Short-Horizon Planning in Same-Day Delivery Problems
1 Introduction
2 Related Work
3 Problem Definition and Formalization
3.1 Instance Specification
3.2 Feasible Solutions
3.3 Objective Function
3.4 Illustrative Example
4 Discounting Travel Times to Consider Expected Orders
4.1 Obtaining Training Data
4.2 Models for the Discounting
5 Computational Study
5.1 Instances
5.2 Training of the Discounted Route Duration Models
5.3 Full-Day Simulation Results
6 Conclusions and Future Work
References
Between Steps: Intermediate Relaxations Between Big-M and Convex Hull Formulations
1 Introduction
1.1 Background
2 Relaxations Between Convex Hull and Big-M
2.1 Properties of the P-Split Formulation
2.2 Illustrative Example
3 Numerical Comparison
3.1 Numerical Results
4 Conclusions
References
Logic-Based Benders Decomposition for an Inter-modal Transportation Problem
1 Introduction
2 Modeling
3 A Logic-Based Benders Decomposition Approach
3.1 Constructing the Initial Master Problem
3.2 Benders Subproblem
3.3 Adding Valid Benders Optimality Cuts
3.4 Subproblem Relaxation
4 Computational Work
5 Conclusions
References
Checking Constraint Satisfaction
1 Introduction
2 Preliminaries
2.1 Constraint Programming
2.2 Multi-valued Decision Diagram
3 Checking Constraint Satisfaction
3.1 Operator of Inclusion
4 Inferring Parameters of Global Constraints
4.1 Implementation
4.2 Properties Definitions
5 Experiments
5.1 Testing Environment
5.2 Comparison Between Inclusion and Intersection Based Inclusion
5.3 Learning Parameters of a Global Constraint
5.4 Conclusion
References
Finding Subgraphs with Side Constraints
1 Introduction
1.1 Preliminaries
1.2 Initial Experiments and Motivation
2 Hybrid Solving with High-Level Modelling
2.1 High-Level Modelling
2.2 When to Communicate?
2.3 How to Communicate
2.4 Design Experiments
2.5 A Rollback Approach to Communication
3 Subgraph Problems with Side Constraints
3.1 Retyping Problems
3.2 Temporal Subgraph Problems
3.3 Subgraph Isomorphism with Costs
4 Conclusion
References
Short-Term Scheduling of Production Fleets in Underground Mines Using CP-Based LNS
1 Introduction
2 Underground Mine Scheduling
3 Approach
3.1 Constraint Programming
3.2 Large Neighborhood Search
4 Results
5 Discussion and Conclusion
References
Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling
1 Introduction
2 Shifts as Paths in State-Expanded Networks
3 MILP Formulation
4 Learning to Reduce the Network
5 Experimental Results
6 Conclusions
References
SeaPearl: A Constraint Programming Solver Guided by Reinforcement Learning
1 Introduction
2 Technical Background
2.1 Reinforcement Learning
2.2 Graph Neural Network
3 Embedding Learning in Constraint Programming
4 Modeling, Learning and Solving with SeaPearl
5 Experimental Results
5.1 Graph Coloring Problem
5.2 Travelling Salesman Problem with Time Windows
6 Perspectives and Future Works
7 Conclusion
References
Learning to Sparsify Travelling Salesman Problem Instances
1 Introduction
2 Notation and Related Work
2.1 Exact, Heuristic and Approximate Approaches
2.2 Learning to Solve Combinatorial Optimisation Problems
2.3 Graph Sparsification
3 Sparsification Scheme
3.1 Linear Programming Features
3.2 Minimum Weight Spanning Tree Features
3.3 Local Features
3.4 Postprocessing Pruned TSP Graphs
4 Experiments and Results
4.1 Learning to Sparsify
4.2 Performance on MATILDA Instances
4.3 Pruning with and Without Guarantees
4.4 Minimum Weight Spanning Tree Pruning
4.5 Specifying the Pruning Rate
5 Discussion and Conclusions
References
Optimized Item Selection to Boost Exploration for Recommender Systems
1 Introduction
2 Problem Definition
3 Recommender System Components
4 Solving the ISP
4.1 Minimizing the Subset Size
4.2 Maximizing Diversity
4.3 Bounded Subset Size
4.4 Multi-level Optimization
5 Warm-Starts
6 Experiments
6.1 Evaluation Metrics and Questions
6.2 Datasets: Book and Movie Recommendations
6.3 Setup and Parameters
6.4 Embedding Space
6.5 Comparisons
6.6 Analysis of Coverage [Q1]
6.7 Analysis of Bounded Coverage [Q2]
6.8 Analysis of Warm-Start [Q3]
6.9 Analysis of Embedding Space [Q4]
7 Related Work
8 Interactive Exploration of ISP
9 Conclusion
References
Improving Branch-and-Bound Using Decision Diagrams and Reinforcement Learning
1 Introduction
2 Learning Bounds Inside Branch-and-Bound
2.1 Decision Diagram-Based Branch-and-Bound
2.2 Variable Ordering and Reinforcement Learning
2.3 The Branch-and-Bound Algorithm with a RL Agent
3 Experimental Results
3.1 Performances of the Learned Variable Ordering
3.2 Caching to Save Computation Time
3.3 Discussion
4 Conclusion
References
Physician Scheduling During a Pandemic
1 Introduction
2 Problem Description and Constraint Model
2.1 Input Parameters and Decision Variables
2.2 Hard Constraints
2.3 Soft Constraints
3 Experimental Evaluation
3.1 Impact of Pandemic-Related Constraints
4 Conclusion
References
Author Index