Learning and Intelligent Optimization: 17th International Conference, LION 17, Nice, France, June 4–8, 2023, Revised Selected Papers (Lecture Notes in Computer Science, 14286)

This book constitutes the refereed proceedings of the 17th International Conference on Learning and Intelligent Optimization, LION-17, held in Nice, France, during June 4–8, 2023. The 40 full papers presented have been carefully reviewed and selected from 83 submissions. They focus on all aspects of unleashing the potential of integrating machine learning and optimization approaches, including automatic heuristic selection, intelligent restart strategies, predict-then-optimize, Bayesian optimization, and learning to optimize. Preface Organization Contents Anomaly Classification to Enable Self-healing in Cyber Physical Systems Using Process Mining 1 Introduction 1.1 Process Mining 1.2 Anomalies in Event Logs 1.3 Ensemble Machine Learning Approaches 1.4 Models Used 2 Literature Survey 3 Problem Statement and Dataset Description 4 Methodology 4.1 Event Logs and Process Discovery 4.2 Conformance Checking 4.3 Anomaly Classification 5 Results and Discussions 5.1 Model Preparation 5.2 Dataset Generation 5.3 Conformance Checking 5.4 Bagging and Boosting Classification 6 Conclusion References Hyper-box Classification Model Using Mathematical Programming 1 Introduction 2 Related Work 3 Methodology 3.1 Problem Statement 3.2 Mathematical Formulation 3.3 Testing Phase 3.4 Illustrative Example 4 Computational Results 5 Concluding Remarks References A Leak Localization Algorithm in Water Distribution Networks Using Probabilistic Leak Representation and Optimal Transport Distance 1 Introduction 1.1 Motivations 1.2 Related Works 1.3 Our Contributions 1.4 Content Organization 2 The Wasserstein Distance 2.1 Basic Definitions 2.2 Wasserstein Barycenter 3 Wasserstein Enabled Leak Localization 3.1 Generation of Leak Scenarios 3.2 Clustering in the Wasserstein Space 3.3 Evaluation Metrics 4 Experimental Results 4.1 Data Resources 4.2 Computational Results 5 Conclusions, Limitations, and Perspectives References Fast and Robust Constrained Optimization via Evolutionary and Quadratic Programming 1 Introduction and Related Work 2 Problem Formulation and Background Material 2.1 Particle Swarm Optimization 2.2 Sequential Linear Quadratic Programming 3 The Proposed UPSO-QP Approach 3.1 Local QP Problems 3.2 UPSO for Constrained Optimization 3.3 Considerations 4 Experiments 4.1 Numerical Constrained Optimization Problems 4.2 Constrained Optimization with Noisy Functions Values 4.3 Evaluation on High Dimensional Problems 5 Concluding Remarks References Bayesian Optimization for Function Compositions with Applications to Dynamic Pricing 1 Introduction 1.1 Related Work 1.2 Dynamic Pricing and Learning 1.3 Contributions and Organization 2 Problem Description 2.1 BO for Function Composition 2.2 Bayesian Optimization for Dynamic Pricing 3 Proposed Method 3.1 Statistical Model and GP Regression 3.2 cEI and cUCB Acquisition Functions 4 Experiments and Results 4.1 Results on Test Functions 4.2 Results for Demand Pricing Experiments 4.3 Runtime Comparisons with State of the Art 5 Conclusion References A Bayesian Optimization Algorithm for Constrained Simulation Optimization Problems with Heteroscedastic Noise 1 Introduction 2 Bayesian Optimization (BO) and Stochastic Kriging (SK): Notation and Terminology 2.1 Bayesian Optimization (BO) 2.2 Stochastic Kriging (SK) 3 Proposed Algorithm 4 Numerical Experiments 5 Results 6 Conclusion References Hierarchical Machine Unlearning 1 Introduction 2 Related Work 3 Preliminary 3.1 Machine Unlearning 3.2 PAC Learning 4 Hierarchical Machine Unlearning 4.1 Data Partitioning 4.2 Isolation Training 4.3 Model Aggregation 5 Time Overhead 6 Experiment 7 Conclusion References Explaining the Behavior of Reinforcement Learning Agents Using Association Rules 1 Introduction 2 Case Study: Street Fighter Turbo II 3 Definition of the Environment 4 Learning Algorithm 5 Explanation with Association Rules 6 Analysis of the Rules Obtained 7 Conclusion and Future Work References Deep Randomized Networks for Fast Learning 1 Introduction 2 Related Articles 3 The Proposed MP-DRNN Method 3.1 The Initial Phase of MP-DRNN 3.2 Extension Phases 4 Datasets 5 Evaluations and Further Studies 5.1 Evaluation of Reference Methods and Our Base Model 5.2 Improvements for Building MP-DRNN Models 6 Conclusions and Future Work References Generative Models via Optimal Transport and Gaussian Processes 1 Introduction 2 Background 2.1 Optimal Transport 2.2 Gaussian Process Regression 3 Learning and Generalizing Optimal Transport Maps 4 Experimental Setting 4.1 Toy 2D Examples 4.2 Image Generation 5 Results 5.1 Results on Toy 2D Examples 5.2 Results on Image Generation 6 Conclusions References Real-World Streaming Process Discovery from Low-Level Event Data 1 Introduction 2 Context 2.1 Naming Conventions 2.2 A Company's Expectations and Related Challenges 3 Related Work 3.1 A Brief Overview of Process Mining 3.2 The Organizational Perspective 3.3 Streaming Process Discovery 4 Contribution 4.1 Supervision of a Whole Application Domain 4.2 Unsupervised and Streaming Process Discovery 4.3 Control 4.4 Scaling 4.5 Optimistic Locking Mechanism 5 Deployment 6 Conclusion References Robust Neural Network Approach to System Identification in the High-Noise Regime 1 Introduction 2 Related Works 3 Proposed Method 4 Experimental Results and Discussion 4.1 Smooth Right-Hand Side 4.2 Non-smooth Right-Hand Side 4.3 Comparison with Other Methods 4.4 Improving Interpretability Using SINDy 5 Conclusion References GPU for Monte Carlo Search 1 Introduction 1.1 History of Monte Carlo Search Algorithms 1.2 Generating Playouts 1.3 Why GPUs Have Not Been Considered? 1.4 Our Contribution 2 Parallel Execution 2.1 Warp 2.2 Theoretical Model 2.3 Numerical Estimation 3 Expected Performance 3.1 Computing Power 3.2 CPU and GPU Memory Cache Size 3.3 Estimating Memory Latency 3.4 Random Access and CPU L1 Cache Latency 3.5 Random Access and GPU Latency 3.6 Synthesis 4 Snake in the Box 4.1 Performance Benchmark 4.2 Game Rules 4.3 Data Structure 5 Nested Monte-Carlo Search 5.1 Algorithm 5.2 NMCS with Parallel Leaf 5.3 NMCS on GPU 5.4 Performance Comparison 5.5 Implementation 6 Conclusion References Learning the Bias Weights for Generalized Nested Rollout Policy Adaptation 1 Introduction 2 Monte Carlo Search 2.1 NRPA and GNRPA 2.2 Learning the Bias 3 Experimental Results 3.1 3D Bin Packing 3.2 The Vehicle Routing Problem 4 Discussion 5 Conclusion References Heuristics Selection with ML in CP Optimizer 1 Introduction 2 CPO Modelling Language and Features Definition 2.1 CPO Modelling Language 2.2 Features Definition 2.3 Benchmark Problems and Performance Assessment 3 General Approach 3.1 Algorithm Selection Problem Formulation 3.2 Training Methodology Robustness 3.3 Trained Models Lifecycle Management 3.4 Machine Learning Workflow 3.5 Integration in CPO and Final Performance Evaluation 4 Experimental Results 4.1 Experimental Setup and Features Sets 4.2 Training Workflow Results 4.3 Benchmarking Results for CPO with ML 4.4 Features Importance Analysis 5 Concluding Remarks References Model-Based Feature Selection for Neural Networks: A Mixed-Integer Programming Approach 1 Introduction 2 Input Feature Selection Algorithm 2.1 Encoding DNNs as MILPs 2.2 The Optimal Sparse Input Features (OSIF) Problem 2.3 Input Distribution Constraints 2.4 Controlling the Number of Selected Features 3 Computational Results 3.1 Accuracy of DNNs with Sparse Input Features 3.2 Robustness to Adversarial Inputs 4 Conclusion References An Error-Based Measure for Concept Drift Detection and Characterization 1 Introduction 2 Related Work 3 Proposal 3.1 General Notations 3.2 Algorithm 4 Evaluation 4.1 Protocol 4.2 Results 5 Conclusion References Predict, Tune and Optimize for Data-Driven Shift Scheduling with Uncertain Demands 1 Introduction 2 Predict, Tune and Optimize 3 Multi-activity Shift Scheduling Under Uncertainty 4 Computational Experiments 5 Related Work 6 Conclusions References On Learning When to Decompose Graphical Models 1 Introduction 2 Preliminaries 2.1 Graphical Models 2.2 Decomposition-Based Backtracking Algorithms 3 A Preliminary Experiment 4 Machine Learning for Decomposition 4.1 Random k-Trees 4.2 Instances with Random Cost Functions 4.3 Instances with Deterministic Cost Functions 4.4 Benchmark Instances 5 Related Work 5.1 Decomposition-Based Algorithms 5.2 Machine Learning in Graphical Models 6 Conclusions and Future Work References Inverse Lighting with Differentiable Physically-Based Model 1 Introduction 2 Related Works 3 Problem Formulation 4 Methods 5 Experiments 6 Discussion and Future Work References Repositioning Fleet Vehicles: A Learning Pipeline 1 Introduction 2 Literature Review 3 The Ride-Hailing Problem 3.1 Problem Definition 3.2 Modelling the Repositioning Task 4 Learning Pipeline for Vehicle Repositioning 5 Case Study: Ambulance Fleet in Belgium 5.1 Use of the Pipeline 5.2 Training Phase 5.3 Results: Location Prediction 5.4 Results: Ambulances Repositioning 6 Conclusion Appendix 1. Analysis: Features Importance Appendix 2. Analysis: Online Learning References Bayesian Decision Trees Inspired from Evolutionary Algorithms 1 Introduction and Relevant Work 2 Bayesian Decision Trees 2.1 Stochastic Processes on Trees 3 Our Approach on Evolutionary Algorithms 4 Methods 4.1 Conventional MCMC 4.2 Evolutionary Algorithm in Bayesian Decision Trees 4.3 Sequential Monte Carlo with EA 5 Experimental Setup and Results 6 Conclusion References Towards Tackling MaxSAT by Combining Nested Monte Carlo with Local Search 1 Introduction 2 Related Work 3 Preliminaries 3.1 MaxSAT 3.2 Heuristics 3.3 Stochastic Local Search 3.4 Monte Carlo Tree Search 3.5 Nested Monte Carlo Search 4 Dynamic SLS Based Monte Carlo Methods 5 Orientation Experiments 5.1 Trial with Different Rollout 5.2 UCTMAX vs NMCTS 5.3 Current Global Best Solution 5.4 Probabilistic SLS Initialization 5.5 Fixed Flip Limits vs Dynamic Flip Limits 6 Experiments on Benchmark 7 Conclusion and Future Work References Relational Graph Attention-Based Deep Reinforcement Learning: An Application to Flexible Job Shop Scheduling with Sequence-Dependent Setup Times 1 Introduction 2 Related Work 3 Preliminaries 3.1 Flexible Job Shop Scheduling with Dynamic Setup Times 3.2 Graph Structural Properties 4 Method 4.1 Markov Decision Process Formulation 4.2 Edge Features Guided Relational Graph Attention Network 4.3 Deep Reinforcement Learning 5 Experiments and Results 5.1 Experimental Settings 5.2 Results 6 Conclusions and Future Work References Experimental Digital Twin for Job Shops with Transportation Agents 1 Introduction 2 Related Work 3 EDT Design 3.1 Tool Selection 3.2 JSPTA Environment Components 3.3 Neural Combinatorial Optimization Approach 3.4 Experimental Setup 4 EDT Evaluation 4.1 Testing Results 4.2 Discussion 5 Conclusion References Learning to Prune Electric Vehicle Routing Problems 1 Introduction 2 Related Literature 2.1 The Electric Vehicle Routing Problem 2.2 End-to-End Machine Learning Heuristics 2.3 Learning to Prune 3 Methodology 3.1 Pruning Matheuristic Methodology 3.2 Deep Learning Heuristic 3.3 Constructing Pseudo-labels 3.4 Pruning as Classification 3.5 Computational Setup 4 Results 4.1 Training the Deep Learning Heuristic 4.2 The Pruning Classification Model 4.3 Pruning Then Optimising 5 Conclusions and Discussion References Matheuristic Fixed Set Search Applied to Electric Bus Fleet Scheduling 1 Introduction 2 Model Outline 3 Graph Formulation 4 Mathematical Model 5 Matheuristic Fixed Set Search 5.1 Fixed Set 5.2 Integer Program Use 5.3 Learning Mechanism 6 Results 7 Conclusion References Class GP: Gaussian Process Modeling for Heterogeneous Functions 1 Introduction 2 Problem Setup and Notation 2.1 Observation Model 3 Background 3.1 Gaussian Process Modeling 3.2 Classification Tree Algorithm 4 Class-GP Framework 4.1 Learning Partitions 4.2 Gaussian Process in Each Partition 5 Class-GP Analysis 6 Numerical Results 6.1 Synthetic Data and Experimental Setup 7 Conclusion and Future Work A Appendix References Surrogate Membership for Inferred Metrics in Fairness Evaluation 1 Introduction 2 Problem Definition 3 Solving PMP with Surrogate Membership 4 From PMP to Fairness Evaluation 4.1 Fairness Metrics as Functions of Arithmetic Means 4.2 Bootstrap Estimation 5 Related Work 6 Experiments 6.1 [Q1] Performance Against Oracle 6.2 [Q2] Robustness Under Different Fairness Scenarios 7 Practical Considerations 7.1 Omitted Variable Bias 7.2 Characteristics of Z and Pz(x X) 8 Conclusions A Appendix - Comparison to Weighted Fairness Statistic A.1 Re-Writing the Weighted Estimator A.2 Re-Writing the Inferred Estimator References The BeMi Stardust: A Structured Ensemble of Binarized Neural Networks 1 Introduction 2 Binarized Neural Networks 3 The BeMi Ensemble 3.1 The BeMi Structure 3.2 Majority Voting System 3.3 A Multi-objective MIP Model for Training BNNs 4 Computational Results 4.1 Experiment 1 4.2 Experiment 2 4.3 Experiment 3 5 Conclusions References Discovering Explicit Scale-Up Criteria in Crisis Response with Decision Mining 1 Introduction 2 Methodology 3 Crisis Management Process at VRU 4 Data Gathering 4.1 Historic Data 4.2 Implicit Knowledge 5 Process Discovery 6 Decision Criteria Extraction 6.1 Results 7 Related Work 8 Conclusion and Future Work References Job Shop Scheduling via Deep Reinforcement Learning: A Sequence to Sequence Approach 1 Introduction 2 Related Works 3 Mathematical Foundations 3.1 Policy Gradient Algorithms 4 The Job Shop Optimization Problem: Notation 5 Our Sequence to Sequence Approach to the JSP 5.1 Sequence Encoding 5.2 Model Architecture 5.3 Experiments and Results 6 Conclusions References Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks 1 Introduction 2 Related Work 3 Problem Definition 4 Preliminaries 5 Methodology 5.1 Graph Colouring as a Markov Decision Process 5.2 Parameterising the State 5.3 Q-Network Architecture 5.4 Selecting Actions 5.5 The ReLCol Algorithm 6 Experimental Results 6.1 Comparison with Existing Algorithms 6.2 A Class of Graphs on Which ReLCol Outperforms DSATUR 6.3 Scalability of ReLCol 6.4 Representing the State as a Complete Graph 7 Conclusions References Multi-task Predict-then-Optimize 1 Introduction 2 Related Work 2.1 Differentiable Optimization 2.2 Multi-task Learning 3 Building Blocks 3.1 Optimization Problem 3.2 Gradient-Based Learning 3.3 Decision Losses 3.4 Multi-task Loss Weighting Strategies 4 Learning Architectures 4.1 Shared Learnable Layers 4.2 Label Accessibility and Learning Paradigms 5 Experiments 5.1 Benchmark Datasets and Neural Network Architecture 5.2 Performance Advantage of Multi-task Learning 5.3 Efficiency Benefit of Multi-task Learning 5.4 Learning Under Data Scarcity 5.5 Learning Under Task Redundancy 6 Conclusion References Integrating Hyperparameter Search into Model-Free AutoML with Context-Free Grammars 1 Introduction 2 Related Work 3 Background 4 Hyperparameter Search in Grammar-Based AutoML 5 Experiments 5.1 Experimental Setup 5.2 Ablation Study 5.3 Comparison with Other Techniques 6 Conclusions and Future Work References Improving Subtour Elimination Constraint Generation in Branch-and-Cut Algorithms for the TSP with Machine Learning 1 Introduction 2 Related Work 3 SEC Generation in B&C for the TSP 3.1 IP Formulation 3.2 B&C Framework for the TSP 3.3 SEC Generation Problem 4 The GNN-RL Framework for SEC Generation 4.1 Cut Detector 4.2 Cut Evaluator 5 Experiments 5.1 Setup 5.2 Results 6 Conclusion References Learn, Compare, Search: One Sawmill's Search for the Best Cutting Patterns Across and/or Trees 1 Introduction 2 Problem Description 3 Preliminary Concepts 3.1 Depth-First Search (DFS) 3.2 Limited Discrepancy Search (LDS) 3.3 Depth-Bounded Discrepancy Search (DDS) 3.4 Monte Carlo Tree Search (MCTS) 3.5 Searching AND/OR Trees 3.6 Learning for Search Tree Traversal and Adaptative Search 4 Learning from Past Decisions in LCS 4.1 Adaptation of Search Algorithms to Learning 4.2 Finding Similar Logs 5 Experiments 6 Results 7 Conclusion References Dynamic Police Patrol Scheduling with Multi-Agent Reinforcement Learning 1 Introduction 2 Background 2.1 Scheduling Problem with Reinforcement Learning 3 Problem Description 4 Model Formulation 4.1 State 4.2 Action 4.3 Transition 4.4 Constraints 4.5 Patrol Presence 4.6 Reward Function 5 Solution Approach 6 Experimental Setup 6.1 Environment 6.2 Model Parameters 6.3 Training and Test 6.4 Evaluation Metrics 7 Experimental Results 7.1 Solution Quality 7.2 Constraint Sensitivity Analysis 8 Discussion and Future Work References Analysis of Heuristics for Vector Scheduling and Vector Bin Packing 1 Introduction 2 Algorithms and Complexity 2.1 Theoretical Results and Exact Algorithms 2.2 First-Fit and Best-Fit Heuristics 2.3 Genetic Algorithms 2.4 Local Search and Simulated Annealing 3 New Algorithms 3.1 Local Search 3.2 Hybrid Heuristic 3.3 Game-Theoretic Approach 4 Evaluation 4.1 Simulator and Test Environment 4.2 Data Sets 4.3 Metric 4.4 Exact and Approximation Algorithms 4.5 First-Fit and Best-Fit Heuristics 4.6 Comparison of All Heuristics 4.7 Vector Bin Packing Results 5 Conclusion References Unleashing the Potential of Restart by Detecting the Search Stagnation 1 Introduction 2 Preliminaries 2.1 SAT Problem and SAT Solver 2.2 Techniques of CDCL SAT Solvers 2.3 Restart Strategies 2.4 Search Similarity Index 3 Restart Analysis 3.1 Impact of Restart on Search Similarity 3.2 Differences Among SAT Instance Categories 3.3 Differences Between SAT and UNSAT 3.4 Differences in Restart Strategies 4 Proposal and Evaluation – BroSt Restart 4.1 Observations 4.2 BroSt Restart 4.3 Experimental Setup 4.4 Evaluation 5 Related Work 6 Conclusion References Author Index