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

✍ Scribed by Peter J. Stuckey (editor)

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 485
• Edition: 1st ed. 2021
• Category: Library

✦ Synopsis

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

✦ Table of Contents

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