Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/158917
Title: Deep learning for combinatorial optimization problems
Authors: Xin, Liang
Keywords: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
Issue Date: 2022
Publisher: Nanyang Technological University
Source: Xin, L. (2022). Deep learning for combinatorial optimization problems. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/158917
Abstract: Combinatorial Optimization Problems (COPs) are a family of problems that search over a finite set of solutions to find the best one with the objective function optimized. COPs have extensive real-world applications in various industries, such as vehicle navigation systems, logistics and supply chain management. And a better solution for the problem could lead to a significantly large amount of cost reduction. Unfortunately, many important COPs including Vehicle Routing Problems, Boolean Satisfiability Problems and Scheduling Problems are extremely hard to solve, where the exact methods to find the best solutions have the worst-case exponential time complexity in general, therefore, usually too time-consuming to apply for problems with medium to large sizes. In contrast, though lacking theoretical guarantees, heuristic methods can find good solutions in a relatively short time and are usually more preferred for industrial applications. Traditional heuristic methods search over the solution space based on the hand-crafted rules designed manually by researchers, which require extensive expert knowledge for specific problems. On the contrary, recent studies have been focusing on training deep learning models to learn the heuristics from data samples. With the great learning ability of deep neural networks, potentially better heuristics could be extracted without the heavy research time, especially for the less well-studied problems with complicated constraints and objective functions. The deep learning models can either be trained by supervised learning to imitate the solutions obtained from highly optimized traditional algorithms or by reinforcement learning to explore the environment of solution space and optimize the objective values. In this report, we mainly focus on one of the most important families of COPs, the Vehicle Routing Problem (VRP). However, most ideas behind the proposed models could also be applied to other COPs in general. Though we tackle various aspects with different model architectures and training algorithms, the goal is to find better solutions in a shorter time.
URI: https://hdl.handle.net/10356/158917
Rights: This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0).
Fulltext Permission: embargo_20240523
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Theses

Files in This Item:
File Description SizeFormat 
thesis_XinLiang.pdf
  Until 2024-05-23
3.62 MBAdobe PDFUnder embargo until May 23, 2024

Page view(s)

98
Updated on Dec 6, 2022

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.