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

✍ Scribed by Pierre Schaus

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 459
• Series: Lecture Notes in Computer Science, 13292
• Category: Library

✦ Synopsis

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”.

✦ Table of Contents

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