Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 20th International Conference, CPAIOR 2023 Nice, France, May 29 – June 1, 2023 Proceedings

Preface
Organization
Contents
Efficiently Approximating High-Dimensional Pareto Frontiers for Tree-Structured Networks Using Expansion and Compression
	1 Introduction
	2 Problem Formulation
	3 The Expansion Method
	4 The Compression Method
	5 Experiments
		5.1 Experimental Setup
		5.2 Evaluation Method
		5.3 Experimental Results
		5.4 Ablation Study
	6 Conclusion
	References
Objective-Based Counterfactual Explanations for Linear Discrete Optimization
	1 Introduction
	2 Background
		2.1 Counterfactual Explanations
		2.2 Nearest Counterfactual Explanations
		2.3 Inverse Combinatorial Optimization
	3 Problem Definition
		3.1 Existence of an Explanation
	4 The NCXplain Algorithm
	5 Experimental Method
		5.1 Forward Problems
		5.2 NCEMILP Instances
		5.3 Computational Details
	6 Experimental Results
	7 Limitations and Future Work
	8 Related Work
	9 Conclusion
	References
Column Elimination for Capacitated Vehicle Routing Problems
	1 Introduction
	2 Column Formulation for CVRP
	3 Decision Diagram Formulation for CVRP
		3.1 From Dynamic Programming to Decision Diagrams
		3.2 Dynamic Programming for Route Relaxations
		3.3 Exact and Relaxed Decision Diagrams
		3.4 Constrained Network Flow Formulation
	4 Column Elimination Procedure
	5 Lagrangian Relaxation
	6 Cutting Planes
	7 Reduced Cost-Based Arc Fixing
	8 Experimental Results
	9 Conclusion
	References
Cutting Plane Selection with Analytic Centers and Multiregression
	1 Introduction
	2 Related Work
	3 Contributions and Methodology
		3.1 Analytic Center-Based Methods
		3.2 Multiple LP Solutions
		3.3 Properties and Limitations of the Distance Measures
		3.4 Multi-output Regression
	4 Experiments
		4.1 Root Node Results
		4.2 Branch and Bound Generalisation
		4.3 Regression Model Results
	5 Conclusion
	References
Handling Symmetries in Mixed-Integer Semidefinite Programs
	1 Introduction
	2 Computing Symmetries
	3 Symmetry Detection
	4 Computational Results
	References
A Mixed-Integer Linear Programming Reduction of Disjoint Bilinear Programs via Symbolic Variable Elimination
	1 Introduction
	2 Reducing a DBLP to a MILP: A Worked Example
	3 Symbolic Calculus with Case Representation
		3.1 Case Representation
		3.2 Basic Case Operators
	4 Symbolic Reduction of a DBLP to a MILP
		4.1 Symbolic Minimization of Linear Piecewise Linear Functions
		4.2 Symbolic Minimization of Disjointly Linear Piecewise Bilinear Functions
	5 Empirical Analysis
	6 Conclusion and Future Work
	References
Local Branching Relaxation Heuristics for Integer Linear Programs
	1 Introduction
	2 Background
		2.1 ILP and Its LP Relaxation
		2.2 LNS for ILP Solving
		2.3 LB Heuristic
	3 Related Work
		3.1 LNS for ILPs
		3.2 LNS-Based Primal Heuristics in BnB
		3.3 LNS for Other COPs
	4 The Local Branching Relaxation Heuristic
	5 Empirical Evaluation
		5.1 Setup
		5.2 Results
	6 Conclusion
	References
Online Learning for Scheduling MIP Heuristics
	1 Introduction
	2 Background
	3 Scheduling Primal Heuristics Online
		3.1 The Online Scheduling Framework
		3.2 Choosing a Reward Function
		3.3 Choosing a Bandit Algorithm
	4 Computational Results
	References
Contextual Robust Optimisation with Uncertainty Quantification
	1 Introduction
	2 Robust Predict-then-Optimise
	3 Predictive Models with Uncertainty Quantification
	4 Conditional Ambiguity Sets
	5 Data-driven Robustness Parameter Specification
	6 Computational Evaluation and Discussion
		6.1 Simulated Problem
	References
Breaking Symmetries with High Dimensional Graph Invariants and Their Combination
	1 Introduction
	2 Preliminaries and Notation
	3 Graph Invariants and Their Induced Graph Orderings
	4 Symmetry Breaking Constraints with Graph Invariants
	5 An Application: Generation of Cubic Graphs
	6 Conclusion
	References
Optimization Bounds from Decision Diagrams in Haddock
	1 Introduction
	2 Background
		2.1 MDD as Layered Transition System
		2.2 State Properties
		2.3 Transition Functions
		2.4 Transition Existence Function
		2.5 Node Relaxation Functions
		2.6 MDD Language
	3 MDDs for Optimization
	4 Restricted Decision Diagrams
		4.1 Restricted MDDs in Haddock Propagation
		4.2 Relaxed MDDs in Haddock Propagation
		4.3 Restricted MDDs and Constraints External to the MDD
	5 Best-First Search
	6 Empirical Evaluation
	7 Conclusion
	References
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
	1 Introduction
	2 Preliminaries
		2.1 Reconfiguration Problems
		2.2 Zero-Suppressed Decision Diagram (ZDD)
	3 ZDD-Based Algorithmic Framework
		3.1 Algorithmic Framework
		3.2 Removal and Addition Operations
	4 Versatility of Proposed Algorithm
		4.1 Shortest, Farthest, and Connectivity Variants
		4.2 Token Jumping Model
		4.3 Reconfiguration Objects and Constraints
	5 Experimental Results
	6 Conclusion
	References
Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?
	1 Introduction
	2 Methodology
		2.1 Hybrid Genetic Search
		2.2 Local Search Using Relatedness Measures
		2.3 Crossover Using Relatedness Measures
	3 Experimental Analyses
		3.1 Computational Environment
		3.2 Benchmark Instances
		3.3 Parametrization and Training of the GNN
		3.4 Calibration of the Local Search
		3.5 Experimental Results – Set XML
		3.6 Experimental Results – Set X
	4 Conclusions
	References
Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions
	1 Introduction
	2 Notation
	3 The Linear Regions of Pruned Neural Networks
	4 Pruning Based on Linear Regions
	5 Counting Linear Regions in Subspaces
	6 Computational Experiments
	7 Conclusion
	References
OAMIP: Optimizing ANN Architectures Using Mixed-Integer Programming
	1 Introduction
		1.1 Related Work
	2 Preliminaries
	3 Neuron Importance Score
		3.1 MIP Constraints
		3.2 Bound Propagation
		3.3 MIP Objective
	4 OAMIP: Pruning Approach
	5 Empirical Results
		5.1 OAMIP Robustness
		5.2 Comparison to Random and Critical Pruning
		5.3 Generalization Between Different Datasets
		5.4 Comparison to SNIP
	6 Discussion
	References
Predicting the Optimal Period for Cyclic Hoist Scheduling Problems
	1 Introduction
	2 Hoist Scheduling Problem
	3 Methodology
		3.1 Data
		3.2 ML Model Training
	4 Experimental Results
		4.1 Experiment 1: ML Predictive Power and Model Selection
		4.2 Experiment 2: Bounds and Solutions
		4.3 Experiment 3: Solver Performance with Predicted Bounds
	5 Related Work
	6 Conclusion and Future Work
	References
Scalable and Near-Optimal -Tube Clusterwise Regression
	1 Introduction
	2 Related Work
	3 Optimal CLR with -Tube Objective
		3.1 Reduction of -Tube CLR to a MILP
		3.2 Row Generation Methodology
	4 Empirical Evaluation
		4.1 Synthetic Dataset Experiments
		4.2 Real Dataset Experiments
	5 Conclusion
	References
Branch & Learn with Post-hoc Correction for Predict+Optimize with Unknown Parameters in Constraints
	1 Introduction
	2 Background
	3 Branch & Learn with Post-hoc Correction
	4 Case Studies
		4.1 Maximum Flow with Unknown Edge Capacities
		4.2 0-1 Knapsack with Unknown Weights
		4.3 Minimum Cost Vertex Cover with Unknown Costs and Edge Values
	5 Experimental Evaluation
		5.1 B&L-C Versus IntOpt-C
		5.2 Post-hoc Regret on More General Problems
		5.3 Different Combinations of Correction Functions and Penalty Functions
	6 Conclusion
	References
Interpretable Clustering via Soft Clustering Trees
	1 Introduction
	2 Soft Clustering Trees
		2.1 Soft Decision Trees
		2.2 Soft Clustering Trees
		2.3 Sparsity in Soft Clustering Trees
		2.4 Learning Sparse Soft Clustering Trees Using Continuous Optimization
		2.5 Interpretable Spectral and Kernel-PCA Clustering
		2.6 Scalable Training of Soft Clustering Trees
	3 Experiments
		3.1 Implementation Details
		3.2 Datasets
		3.3 Evaluation
		3.4 Results
	4 Related Work
	5 Conclusion
	References
Ner4Opt: Named Entity Recognition for Optimization Modelling from Natural Language
	1 Introduction
	2 Problem Description
	3 Our Approach
		3.1 Classical NLP
		3.2 Modern NLP
		3.3 Data Augmentation
		3.4 Hybrid Modeling
	4 Experiments
		4.1 Ner4Opt Dataset
		4.2 Comparisons
		4.3 Experimental Setup
		4.4 Evaluation Metrics
		4.5 Numerical Results
		4.6 Post-Mortem Analysis
	5 Related Work
	6 Conclusions
	References
Exploiting Entropy in Constraint Programming
	1 Introduction
	2 Belief Propagation for CSPs
	3 Accuracy of BP-Estimated Marginals and Entropy
	4 Exploiting Entropy
		4.1 Deciding When to Use BP
		4.2 Deciding When to Stop BP Iterations
		4.3 Deciding When to Activate Damping
		4.4 Branching to Search for a Solution
	5 Experimental Evaluation
		5.1 Experimental Protocol
		5.2 Evaluation
	6 Conclusion
	References
Constraint Propagation on GPU: A Case Study for the Cumulative Constraint
	1 Introduction
	2 Background
		2.1 Constraint Satisfaction/Optimization Problem
		2.2 Cumulative
		2.3 GPUs and CUDA
	3 Design and Implementation
		3.1 Parallelization
	4 Experiments
		4.1 Results and Analysis
	5 Conclusions
	References
Constraint Programming for the Robust Two-Machine Flow-Shop Scheduling Problem with Budgeted Uncertainty
	1 Introduction
	2 Problem Statement
		2.1 Processing Times Uncertainty
		2.2 Worst-Case Evaluation
	3 Special Cases
		3.1 Global Budget and Preserved Order of Processing Times
		3.2 Machine-Dependent Budget = (1, 2)
		3.3 Unpreserved Order of Processing Times
	4 General Case
		4.1 Mixed-Integer Linear Programming Robust Counterparts
		4.2 Constraint Programming Robust Counterparts
		4.3 Column and Constraint Generation Algorithm
	5 Experimental Results
		5.1 Instances from Literature
		5.2 New Instances
	6 Conclusion
	References
A Weighted Counting Algorithm for the Circuit Constraint
	1 Introduction
	2 An Unbiased Estimator for the Weighted Count of Hamiltonian Circuits
		2.1 A Sampling Algorithm
		2.2 Empirical Accuracy of the Estimator
	3 Integration in the CP-BP Framework
		3.1 CP-BP Framework
		3.2 Implementation of Weighted Counting for Circuit
	4 Combinatorial Search Guidance
	5 Conclusion
	References
Boolean-Arithmetic Equations: Acquisition and Uses
	1 Introduction
	2 The Relevance of Boolean-Arithmetic Equations
	3 Describing Boolean-Arithmetic Expressions
	4 A Core Model for Acquiring BAE
		4.1 Problem Description
		4.2 A CP Core Model
	5 Enhancing the Core Model
		5.1 Linking the Number of Conditions, Their Arity, and the Number of Attributes
		5.2 Symmetry Breaking
		5.3 Pre-computing the Combinations of Possible Values of the Coefficients of a Condition
	6 Evaluation
	7 Related Work
	8 Conclusion
	References
Generating Random Instances of Weighted Model Counting
	1 Introduction
	2 Preliminaries
	3 Background on WMC Algorithms
	4 Random k-CNF Formulas with Varying Primal Treewidth
		4.1 Validating the Model
	5 Experimental Results
		5.1 Experiments on Random Instances
		5.2 Experiments on Competition Benchmarks
	6 Conclusions and Future Work
	References
Virtual Pairwise Consistency in Cost Function Networks
	1 Introduction
	2 Background
		2.1 Weighted Constraint Satisfaction Problem
		2.2 Constraint Satisfaction Problem and Local Consistencies
		2.3 Soft Local Consistencies
		2.4 Dual Encoding of a Cost Function Network
	3 Virtual Pairwise Consistency
	4 Experimental Results on UAI 2022 Competition
	5 Conclusion
	References
Multi-objective Optimization for the Design of Salary Structures
	1 Introduction
	2 Preliminary Concepts
	3 Optimization Model of Salary Structure Design
		3.1 Scoring Table
		3.2 Score Ranges
		3.3 Salary Structure
		3.4 Objective Functions
		3.5 Model Complexity
	4 Experiments
		4.1 Data
		4.2 Optimization Method
		4.3 Heuristic Search
	5 Results and Discussion
		5.1 Pareto Frontier
		5.2 Comparison with the Negotiated Structure
	6 Conclusion
	References
Scheduling Complex Observation Requests for a Constellation of Satellites: Large Neighborhood Search Approaches
	1 Introduction
	2 Related Work
	3 Earth Observation Scheduling Problem
		3.1 Problem Modeling
		3.2 Connected Components
	4 Large Neighborhood Search Algorithms
		4.1 Generic Large Neighbourhood Search
		4.2 Greedy Fill Method
		4.3 Greedy LNS Destroying Requests
		4.4 Hybrid LNS Destroying Connected Components
	5 Experiments
		5.1 Instances
		5.2 Experimental Setup
		5.3 Results
	6 Conclusion
	References
Predicting Wildlife Trafficking Routes with Differentiable Shortest Paths
	1 Introduction
	2 Related Work
	3 Flight Itinerary Prediction Formulation
		3.1 Predictive Model: Edge Transition Estimator
		3.2 Model Training: Path-Integrated Learning
		3.3 Model Training: Edge-Myopic Learning
	4 Data Sources
	5 Experiments
		5.1 Feature Selection
		5.2 Metrics
		5.3 Results Discussion
		5.4 Conclusion
	References
Iterated Greedy Constraint Programming for Scheduling Steelmaking Continuous Casting
	1 Introduction
	2 Problem Description
	3 Iterated Greedy CP Algorithm
		3.1 Lower Bound Computation
		3.2 Initial Heuristic
		3.3 Destruction and Construction Heuristics
		3.4 CP Improvement
		3.5 Iterated Greedy CP
	4 Experiments
		4.1 Experimental Setting
		4.2 Experimental Results
	5 Concluding Remark
	References
Combining Incomplete Search and Clause Generation: An Application to the Orienteering Problems with Time Windows
	1 Introduction
	2 Orienteering Problem with Time Windows
	3 Incomplete Search Using a Clause Basis
	4 Lazy Clause Generation Module
		4.1 Clauses Generated from Time-Window Conflicts
		4.2 Clauses Related to Local Optima: Lopt-Conflicts
	5 Clause Basis Data Structures
		5.1 CB-UnitPropagation
		5.2 CB-IncrementalSAT
		5.3 CB-OBDD
	6 Computational Study
		6.1 Parameter Settings for clauseGeneration
		6.2 Performance of the Versions of CB
	7 Related Works
	8 Conclusion and Perspectives
	References
Author Index