In this paper, we propose a hybrid framework to solve large-scale\npermutation-based combinatorial problems effectively using a high-performance\nquadratic unconstrained binary optimization (QUBO) solver. To do so,\ntransformations are required to change a constrained optimization model to an\nunconstrained model that involves parameter tuning. We propose techniques to\novercome the challenges in using a QUBO solver that typically comes with\nlimited numbers of bits. First, to smooth the energy landscape, we reduce the\nmagnitudes of the input without compromising optimality. We propose a machine\nlearning approach to tune the parameters for good performance effectively. To\nhandle possible infeasibility, we introduce a polynomial-time projection\nalgorithm. Finally, to solve large-scale problems, we introduce a\ndivide-and-conquer approach that calls the QUBO solver repeatedly on small\nsub-problems. We tested our approach on provably hard Euclidean Traveling\nSalesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is\nless than $10\\%$ and $11\\%$ are obtained respectively compared to the\nbest-known approach.\n