A hybrid framework using a QUBO solver for permutation-based combinatorial optimization
In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstra...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2020
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/5978 https://ink.library.smu.edu.sg/context/sis_research/article/6981/viewcontent/Goh__S._T.__Gopalakrishnan__S.__Bo__J.____Lau__H._C.__2020_._A_Hybrid_Framework_Using_a_QUBO_Solver_For_Permutation_Based_Combinatorial_Optimization.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-6981 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-69812021-06-07T06:27:35Z A hybrid framework using a QUBO solver for permutation-based combinatorial optimization GOH, Siong Thye GOPALAKRISHNAN, Sabrish BO, Jianyuan LAU, Hoong Chuin In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than 10% and 11% are obtained respectively compared to the best-known approach. 2020-09-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/5978 https://ink.library.smu.edu.sg/context/sis_research/article/6981/viewcontent/Goh__S._T.__Gopalakrishnan__S.__Bo__J.____Lau__H._C.__2020_._A_Hybrid_Framework_Using_a_QUBO_Solver_For_Permutation_Based_Combinatorial_Optimization.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Machine learning quadratic unconstrained binary optimization solver large-scale permutation-based combinatorial problems MITB student Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Machine learning quadratic unconstrained binary optimization solver large-scale permutation-based combinatorial problems MITB student Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Theory and Algorithms |
spellingShingle |
Machine learning quadratic unconstrained binary optimization solver large-scale permutation-based combinatorial problems MITB student Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Theory and Algorithms GOH, Siong Thye GOPALAKRISHNAN, Sabrish BO, Jianyuan LAU, Hoong Chuin A hybrid framework using a QUBO solver for permutation-based combinatorial optimization |
description |
In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than 10% and 11% are obtained respectively compared to the best-known approach. |
format |
text |
author |
GOH, Siong Thye GOPALAKRISHNAN, Sabrish BO, Jianyuan LAU, Hoong Chuin |
author_facet |
GOH, Siong Thye GOPALAKRISHNAN, Sabrish BO, Jianyuan LAU, Hoong Chuin |
author_sort |
GOH, Siong Thye |
title |
A hybrid framework using a QUBO solver for permutation-based combinatorial optimization |
title_short |
A hybrid framework using a QUBO solver for permutation-based combinatorial optimization |
title_full |
A hybrid framework using a QUBO solver for permutation-based combinatorial optimization |
title_fullStr |
A hybrid framework using a QUBO solver for permutation-based combinatorial optimization |
title_full_unstemmed |
A hybrid framework using a QUBO solver for permutation-based combinatorial optimization |
title_sort |
hybrid framework using a qubo solver for permutation-based combinatorial optimization |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2020 |
url |
https://ink.library.smu.edu.sg/sis_research/5978 https://ink.library.smu.edu.sg/context/sis_research/article/6981/viewcontent/Goh__S._T.__Gopalakrishnan__S.__Bo__J.____Lau__H._C.__2020_._A_Hybrid_Framework_Using_a_QUBO_Solver_For_Permutation_Based_Combinatorial_Optimization.pdf |
_version_ |
1770575725597818880 |