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 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.