Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Only Sessions at Location/Venue 
 
 
Session Overview
Session
WB 02: Learning for Optimization 1
Time:
Wednesday, 04/Sept/2024:
11:00am - 12:00pm

Session Chair: Tobias Klein
Location: Theresianum 0602
Room Location at NavigaTUM


Show help for 'Increase or decrease the abstract text size'
Presentations

Learning to Filter State-Expanded Networks for Two-Stage Stochastic Programming

Michael Römer

Bielefeld University, Germany

Mixed-integer linear programming models relying on state-expanded networks have been shown to yield be highly efficient formulations for certain problem classes such as personnel scheduling. In recent works, we demonstrated that Machine Learning can be used to heuristically reduce the size of large-scale state-expanded networks, resulting in significant reductions in model size and solution time while exhibiting a negligible impact on solution quality. In this talk, we propose to apply this approach in the context of optimization under uncertainty, namely in a two-stage stochastic programming approach for shift scheduling with stochastic demands. In particular, we show how to use information from solving the LP relaxations of deterministic instances for multiple demand scenarios to train a Machine Learning model which is then used to filter the state-expanded networks to be used in the stochastic programming model. In a set of computational experiments, we show that the resulting drastic reduction of the model size can either be used to solving given stochastic programming models much faster or to solve models with a much larger number of scenarios compared to models relying on the non-filtered state-expanded networks.



Graph Convolutional Neural Network Assisted Monte Carlo Tree Search for the Capacitated Vehicle Routing Problem with Time Windows

Jorin Dornemann1, Tobias Klein2, Kathrin Fischer2, Anusch Taraz1

1Institute of Mathematics, Hamburg University of Technology, Germany; 2Institute for Operations Research and Information Systems, Hamburg University of Technology, Germany

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a well-known combinatorial optimization problem that extends the classical Vehicle Routing Problem to account for additional real-world constraints such as truck capacity and customer time windows. Recent studies have explored the use of deep graph convolutional networks (GCNs) to predict the arcs that are part of the optimal tour for the Travelling Salesman Problem and related routing problems. We propose a novel context complemented graph convolutional network (CCGCN) which is integrated into a Monte Carlo Tree Search (MCTS) to solve the CVRPTW sequentially. The deep convolutional part of the proposed neural network builds efficient CVRPTW graph representations, whereas the context part processes information of partially built tours to output probabilities on which vertex to add next to the tour, which are used during the expansion of the search tree. For simulating final solution values within the Monte Carlo search tree, we conducted experiments using two different heuristics: LKH and a beam search. By leveraging the probabilities provided by our CCGCN and employing a variation of Upper Confidence Bound applied to trees, we effectively manage the tradeoff between exploration and exploitation, thus reducing the optimality gap compared to solutions generated solely by LKH. Evaluations of the proposed heuristic are performed on benchmark instances of the CVRPTW with up to 100 customers; these show promising results.



 
Contact and Legal Notice · Contact Address:
Privacy Statement · Conference: OR 2024
Conference Software: ConfTool Pro 2.6.153+TC
© 2001–2025 by Dr. H. Weinreich, Hamburg, Germany