Conference Agenda

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.

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.