Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, ... (Lecture Notes in Computer Science, 12735)

Description

This volume LNCS 12735 constitutes the papers of the 18th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2021, which was held in Vienna, Austria, in 2021. Due to the COVID-19 pandemic the conference was held online. The 30 regular papers presented were carefully reviewed and selected from a total of 75 submissions. The conference program included a Master Class on the topic "Explanation and Verification of Machine Learning Models". 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