Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, CPAIOR 2022 Los Angeles, CA, USA, June 20–23, 2022 Proceedings

Description

This book constitutes the proceedings of the 19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2022, which was held in Los Angeles, CA, USA, in June 2022.The 28 regular papers presented were carefully reviewed and selected from a total of 60 submissions. The conference program included a Master Class on the topic "Bridging the Gap between Machine Learning and Optimization”. Preface Organization Abstract of Keynote Speakers Decision Diagrams for Deterministic and Stochastic Optimization Combining Reasoning and Learning for Discovery Deep Learning and Neural Network Accelerators for Combinatorial Optimization Contents A Two-Phase Hybrid Approach for the Hybrid Flexible Flowshop with Transportation Times 1 Introduction 2 The Constraint Programming Model 3 Metaheuristic Approach 3.1 Computation of the Initial Solution 3.2 Local Search Approaches 3.3 Deconstruction and Reconstruction 3.4 General Structure of IGT_NEH 4 Hybrid Approach 5 Computational Experiments 6 Conclusions and Future Work References A SAT Encoding to Compute Aperiodic Tiling Rhythmic Canons 1 Introduction 2 The Aperiodic Tiling Complements Problem 3 A SAT Encoding 3.1 Existing Solution Approaches 4 Computational Results References Transferring Information Across Restarts in MIP 1 Introduction 2 Global Information 3 Implementation Details 4 Computational Experiments 5 Conclusion and Outlook References Towards Copeland Optimization in Combinatorial Problems 1 Solving Combinatorial Problems by Voting 1.1 Related Work 2 Foundations: Social Choice and (Soft) CSPs 3 Sampling Approach 4 Experimental Evaluation 4.1 Evaluation Metrics 5 Conclusion and Future Work References Coupling Different Integer Encodings for SAT 1 Introduction 2 Preliminaries 2.1 Constraint Programming 2.2 Boolean Satisfiability 3 Encoding Integer Variables 4 Encoding Constraints 4.1 Coupling Equality Constraints 4.2 Coupling Inequality Constraints 4.3 Coupling Element Constraints 5 Views 6 Experimental Results 7 Related Work 8 Conclusion A Proofs References Model-Based Algorithm Configuration with Adaptive Capping and Prior Distributions 1 Introduction 2 SMBO for Hyperparameter Configuration 3 Surrogate Models M and Scoring Functions S 3.1 Hamming Similarity: Searching Near the Current Best 3.2 Beta Distribution 3.3 Dirichlet Distribution 4 Learning Priors 5 Experiments 5.1 Experimental Setup 5.2 Comparison of Models and Surrogates 5.3 Comparison with ParamILS 6 Conclusion and Future Work A Adapted SMBO References Shattering Inequalities for Learning Optimal Decision Trees 1 Introduction 2 The Optimal Decision Tree Problem 2.1 The Optimal Decision Tree Problem 2.2 Problem Formulation 3 Shattering Inequalities 3.1 Decomposition and Separation 4 Experiments 4.1 Experimental Setup 4.2 Results 5 Conclusion References Learning Pseudo-Backdoors for Mixed Integer Programs 1 Introduction 2 Related Work 3 Learning Pseudo-Backdoors 3.1 MIP and Backdoor Data Representation 3.2 Neural Network Architecture 3.3 Learning the Scorer Model 3.4 Learning the Classifier Model 4 Experiment Results 4.1 Problem Domains 4.2 Data Generation and Model Evaluation 4.3 Main Results 5 Conclusion References Leveraging Integer Linear Programming to Learn Optimal Fair Rule Lists 1 Introduction 2 Technical Background and Notations 2.1 Rule Lists and Associated Notations 2.2 Statistical Fairness 3 CORELS and FairCORELS 4 The Proposed Pruning Approach 4.1 A Sufficient Condition to Reject Prefixes 4.2 Integration Within FairCORELS 5 Experimental Study 5.1 Experimental Protocol 5.2 Evaluation of the Proposed ILP-Based Pruning Approaches 5.3 Scalability and Complementarity with the Permutation Map 6 Conclusion References Solving the Extended Job Shop Scheduling Problem with AGVs – Classical and Quantum Approaches 1 Introduction 1.1 Problem Motivation and Description 2 Use Case Scenario 2.1 Definitions and Process Requirements 3 The Extended Job Shop Scheduling Problem with AGVs – Definition 3.1 Parameters 3.2 Variables 3.3 Constraints 3.4 Objective 4 Related Work 5 Methods 5.1 Solving the Extended JSSP with AGVs Using Constraint Programming 5.2 Solving the Extended JSSP with AGVs on a Quantum Annealer 6 Results 6.1 Experimental Results Using the Constraint Programming Approach 6.2 Experimental Results Using the Quantum Approach 7 Discussion and Conclusion References Stochastic Decision Diagrams 1 Introduction 2 Related Work 3 Stochastic Decision Diagrams 4 Stochastic Dynamic Programming 5 Relaxed SDDs 6 Conditions for Node Merger 7 Computational Evaluation 8 Conclusion References Improving the Robustness of EPS to Solve the TSP 1 Introduction 2 Preliminaries 2.1 TSP Model in CP 2.2 EPS 3 Performance with a Hundred Cores 4 Re-decomposition 4.1 How to Avoid Redoing Calculations? 4.2 Discussion 5 Experiments 5.1 Satisfaction vs Optimization 5.2 Comparison for a Given Number of Sub-problems 5.3 The Value 5.4 Computations that Have Already Been Made 5.5 Solving Evolution 5.6 Overall Results 5.7 Robustness 6 Conclusion References Efficient Operations Between MDDs and Constraints 1 Introduction 2 Preliminaries 2.1 Constraint Programming 2.2 Multi-valued Decision Diagram 3 Generalisation of the Construction Process 3.1 State, Transition and Verification 3.2 Sum 3.3 GCC 3.4 AllDifferent 3.5 Generic Constraint Intersection Function 4 Exponential Gain 4.1 Building the AllDifferent's MDD 4.2 Performing the Construction on the Fly 5 Application: Construction of the MDD of Constraints 6 Experiments 6.1 Constraint Building 6.2 The Car Sequencing Problem 7 Conclusion References Deep Policy Dynamic Programming for Vehicle Routing Problems 1 Introduction 2 Related Work 3 Deep Policy Dynamic Programming 3.1 The Graph Neural Network 3.2 Travelling Salesman Problem 3.3 Vehicle Routing Problem 3.4 Travelling Salesman Problem with Time Windows 4 Experiments 4.1 Travelling Salesman Problem 4.2 Vehicle Routing Problem 4.3 TSP with Time Windows 4.4 Ablations 5 Discussion References Learning a Propagation Complete Formula 1 Introduction 2 Propagation Complete Formulas 3 Implicational Systems 4 Checking Propagation Completeness by SAT 4.1 Encoding Empowerment 4.2 Encoding 1-Provability 4.3 Putting the Parts Together 5 The Learning Approach to Compilation 6 Experiments 7 Conclusion References A FastMap-Based Algorithm for Block Modeling 1 Introduction 2 Preliminaries and Background 2.1 Block Modeling 2.2 FastMap 3 FastMap-Based Block Modeling Algorithm (FMBM) 3.1 Probabilistically-Amplified Shortest-Path Distances 3.2 Main Algorithm 4 Experiments 4.1 Visualization 5 Conclusions and Future Work References Packing by Scheduling: Using Constraint Programming to Solve a Complex 2D Cutting Stock Problem 1 Introduction 2 Problem Definition 3 Literature Review 4 The Single Resource CP Formulation 5 Alternative Approaches 5.1 Integer-Based CP Formulations 5.2 Mixed-Integer Formulation 5.3 First-Fit Based Heuristic 6 Numerical Results 7 Discussion and Conclusion References Dealing with the Product Constraint 1 Introduction 2 Preliminaries 2.1 Constraint Programming 2.2 Multi-valued Decision Diagram 3 Product Constraint as a Sum of Logarithms 4 Exact Representation of the Product Constraint 5 Relaxed Product Constraint 6 Incremental Precision Refinement 6.1 Extracting Suspicious Arcs 6.2 On the Fly Intersection 6.3 IPR Algorithm 7 Experiments 7.1 Exact Product Method 7.2 Logarithm and Relaxed Methods 7.3 Incremental Precision Refinement (IPR) 8 Conclusion References Multiple-choice Knapsack Constraint in Graphical Models 1 Introduction 2 Related Work 3 Preliminaries 4 Pseudo-Boolean Constraints in CFNs 4.1 Solving the Knapsack LP 4.2 Propagation 5 Experimental Results 5.1 Sequence of Diverse Solutions for CPD 5.2 Knapsack Problem with a Conflict Graph 6 Conclusion and Future Work References A Learning Large Neighborhood Search for the Staff Rerostering Problem 1 Introduction 2 Related Work 3 Staff Rerostering Problem 4 Large Neighborhood Search 4.1 Random Destroy Operator 4.2 Repair Operator 5 Learning-Based Destroy Operator 5.1 Markov Decision Process Formulation 5.2 Destroy Set Prediction as Conditional Generative Modeling 5.3 Sampling Destroy Sets 5.4 Neural Networks 5.5 Training 5.6 Training Data Generation 6 Experimental Evaluation 7 Conclusion and Future Work References A MinCumulative Resource Constraint 1 Introduction 2 Constraint Scheduling Background 2.1 Global Cardinality Constraint 2.2 Generalized Cumulative 2.3 SoftCumulative 3 Min-Cumulative 4 Underload Check 5 Underload Filtering 5.1 Naive Algorithm 5.2 Overflow Algorithm 6 Model with SoftCumulative 7 Comparing the Rules 8 Experiments 9 Conclusion References Practically Uniform Solution Sampling in Constraint Programming 1 Introduction 2 Solution Sampling 2.1 Systems of Linear Modular Inequalities 2.2 Sampling Algorithm 3 Experiments 3.1 Benchmark Problems 3.2 Quality of Sampling 3.3 Runtime Efficency of Our Sampling Approach 4 Conclusion References Training Thinner and Deeper Neural Networks: Jumpstart Regularization 1 Introduction 2 Background 3 Death, Stagnation, and Jumpstarting 4 Computational Experiments 5 Conclusion References Hybrid Offline/Online Optimization for Energy Management via Reinforcement Learning 1 Introduction 2 Background 3 Problem Description 3.1 Energy Management Case Study 3.2 State-of-the-Art Offline/Online Approach 4 Proposed Methods 4.1 RL-Based TUNING 4.2 End-to-End RL 5 Experimental Results 5.1 Cost Value over Computation Time 5.2 Decision Variables 6 Related Work 6.1 Deep Reinforcement Learning for Combinatorial Optimization 6.2 Predict-then-Optimize 6.3 Hybrid Offline/Online Optimization 7 Conclusions References Enumerated Types and Type Extensions for MiniZinc 1 Introduction 2 Preliminaries 3 Enumerated Types 4 Type Extensions 4.1 Syntax and Examples 4.2 Pattern Matching and Range Notation 4.3 Implementing Enumerated Type Extension 5 Defaults 5.1 The minizinclexer.py:MznLexer -xdefault Operator 5.2 Implementing Defaults 6 Experiments 7 Related Work 8 Conclusion References A Parallel Algorithm for GAC Filtering of the Alldifferent Constraint 1 Introduction 2 Régin's Alldifferent Filtering Algorithm 3 Bulk Synchronous Parallel Model 4 A Parallel Alldifferent Filtering Algorithm 5 Experimental Evaluation 5.1 Data Structures, Data Distribution, and CP Solver Integration 5.2 N-Queens 5.3 Scheduling 6 Related Work and Discussion 7 Conclusion References Analyzing the Reachability Problem in Choice Networks 1 Introduction 2 Statement of Problems 3 Motivation and Related Work 4 Reachability in Choice Networks 4.1 Computational Complexity 4.2 A Fixed-Parameter Algorithm 4.3 Exact Exponential Algorithm 4.4 Approximation Complexity 5 Weighted Reachability in Choice Networks 5.1 Approximation Complexity 6 Lower Bounds for OCRD 7 Conclusion References Model-Based Approaches to Multi-attribute Diverse Matching 1 Introduction 2 Diverse Matching 2.1 Multi-attribute Diverse Weighted Bipartite b-Matching 2.2 Related Work 3 Constraint Programming Models for MDWBM 3.1 Assignment CP Model 3.2 Selection CP Model 4 Quadratic Models for MDWBM 4.1 BQP Model 4.2 Quadratic Unconstrained Binary Optimization 5 Empirical Evaluation 5.1 Fujitsu Digital Annealer 5.2 Experimental Setting 5.3 Experiments on Standard MDWBM 5.4 Experiments on Constrained MDWBM 6 Conclusions References Author Index