Event Details
Solving Combinatorial Optimization Problems using Statistical Learning
Presenter: Andrew Naguib
Supervisor:
Date: Sun, April 9, 2023
Time: 10:00:00 - 00:00:00
Place: ZOOM - Please see below.
ABSTRACT
Zoom Meeting Link: https://uvic.zoom.us/j/88166311324?pwd=OVUvaXdOekFYNVlXZDhTeWk0QW5KUT09
Meeting ID: 881 6631 1324
Password: 029067
You can also dial-in:
+1 647 558 0588 Canada
+1 778 907 2071 Canada
Abstract:
We examine the use of geometric deep neural networks to provide competent solutions, not necessarily incumbent, to two combinatorial problems:
the capacitated vehicle routing problem and the bin packing problem—which have non-deterministic polynomial computational complexity. The core idea is based on learning to approximate the decisions made by the branch and bound algorithm when using the computationally expensive strong branching strategy. The classifiers - graph convolutional neural network, GraphSAGE, and graph attention network - are trained on six topologically different instances (to investigate the geographical dispersion effect on performance) and evaluated on eight additional instances. The experiments show that the proposed approach is able to match the performance of the branch and bound algorithm and improve upon it on two different branching strategies, while requiring significantly less computation time and explored branching nodes.