Deep learning for combinatorial optimization problems
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis-Doctor of Philosophy |
| Language: | English |
| Published: |
Nanyang Technological University
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/158917 |
| _version_ | 1811688890197606400 |
|---|---|
| author | Xin, Liang |
| author2 | Zhang Jie |
| author_facet | Zhang Jie Xin, Liang |
| author_sort | Xin, Liang |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T05:39:23Z |
| format | Thesis-Doctor of Philosophy |
| id | ntu-10356/158917 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:39:23Z |
| publishDate | 2022 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1589172022-06-03T07:08:02Z Deep learning for combinatorial optimization problems Xin, Liang Zhang Jie School of Computer Science and Engineering ZhangJ@ntu.edu.sg Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence 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. Doctor of Philosophy 2022-06-01T12:23:54Z 2022-06-01T12:23:54Z 2022 Thesis-Doctor of Philosophy Xin, L. (2022). Deep learning for combinatorial optimization problems. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/158917 https://hdl.handle.net/10356/158917 en This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0). application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence Xin, Liang Deep learning for combinatorial optimization problems |
| title | Deep learning for combinatorial optimization problems |
| title_full | Deep learning for combinatorial optimization problems |
| title_fullStr | Deep learning for combinatorial optimization problems |
| title_full_unstemmed | Deep learning for combinatorial optimization problems |
| title_short | Deep learning for combinatorial optimization problems |
| title_sort | deep learning for combinatorial optimization problems |
| topic | Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence |
| url | https://hdl.handle.net/10356/158917 |
| work_keys_str_mv | AT xinliang deeplearningforcombinatorialoptimizationproblems |