Penalty weights in QUBO formulations: permutation problems. (English) Zbl 1499.90177
Pérez Cáceres, Leslie (ed.) et al., Evolutionary computation in combinatorial optimization. 22nd European conference, EvoCOP 2022, held as part of EvoStar 2022, Madrid, Spain, April 20–22, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13222, 159-174 (2022).
Summary: Optimisation algorithms designed to work on quantum computers or other specialised hardware have been of research interest in recent years. Commercial solvers that use quantum or quantum-inspired methods, such as Fujitsu’s Digital Annealer (DA) and D-wave’s Quantum Annealer, can solve optimisation problems faster than algorithms implemented on general purpose computers. However, they can only optimise problems that are in binary and quadratic form. Quadratic Unconstrained Binary Optimisation (QUBO) is therefore a common formulation used by these solvers.
There are many combinatorial optimisation problems that are naturally represented as permutations e.g. travelling salesman problem. Encoding permutation problems using binary variables however presents some challenges. Many QUBO solvers are single flip solvers, it is therefore possible to generate solutions that cannot be decoded to a valid permutation. To create bias towards generating feasible solutions, we use penalty weights. The process of setting static penalty weights for various types of problems is not trivial. This is because values that are too small will lead to infeasible solutions being returned by the solver while values that are too large may lead to slower convergence. In this study, we explore some methods of setting penalty weights within the context of QUBO formulations. We propose new static methods of calculating penalty weights which lead to more promising results than existing methods.
For the entire collection see [Zbl 1492.68026].
There are many combinatorial optimisation problems that are naturally represented as permutations e.g. travelling salesman problem. Encoding permutation problems using binary variables however presents some challenges. Many QUBO solvers are single flip solvers, it is therefore possible to generate solutions that cannot be decoded to a valid permutation. To create bias towards generating feasible solutions, we use penalty weights. The process of setting static penalty weights for various types of problems is not trivial. This is because values that are too small will lead to infeasible solutions being returned by the solver while values that are too large may lead to slower convergence. In this study, we explore some methods of setting penalty weights within the context of QUBO formulations. We propose new static methods of calculating penalty weights which lead to more promising results than existing methods.
For the entire collection see [Zbl 1492.68026].
Keywords:
quantum-inspired optimisation; digital annealer; permutation; penalty weights; constraint handling; quadratic unconstrained binary optimisation; Ising model; binary quadratic problemReferences:
| [1] | Aramon, M.; Rosenberg, G.; Valiante, E.; Miyazawa, T.; Tamura, H.; Katzgraber, HG, Physics-inspired optimization for quadratic unconstrained problems using a digital annealer, Front. Phys., 7, 48 (2019) · doi:10.3389/fphy.2019.00048 |
| [2] | Arza, E.; Pérez, A.; Irurozki, E.; Ceberio, J., Kernels of mallows models under the hamming distance for solving the quadratic assignment problem, Swarm Evol. Comput., 59 (2020) · doi:10.1016/j.swevo.2020.100740 |
| [3] | Ayodele, M.; McCall, J.; Regnier-Coudert, O.; Handl, J.; Hart, E.; Lewis, PR; López-Ibáñez, M.; Ochoa, G.; Paechter, B., RK-EDA: a novel random key based estimation of distribution algorithm, Parallel Problem Solving from Nature - PPSN XIV, 849-858 (2016), Cham: Springer, Cham · doi:10.1007/978-3-319-45823-6_79 |
| [4] | Baluja, S.: Population-based incremental learning. a method for integrating genetic search based function optimization and competitive learning. Technical report, Department of Computer Science, Carnegie-Mellon University, Pittsburgh (1994) |
| [5] | Birdal, T., Golyanik, V., Theobalt, C., Guibas, L.J.: Quantum permutation synchronization. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 13122-13133, June 2021 |
| [6] | Boros, E.; Hammer, PL; Sun, R.; Tavares, G., A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), Discret. Optim., 5, 2, 501-529 (2008) · Zbl 1170.90454 · doi:10.1016/j.disopt.2007.02.001 |
| [7] | Burkard, RE; Karisch, SE; Rendl, F., QAPLIB-a quadratic assignment problem library, J. Global Optim., 10, 4, 391-403 (1997) · Zbl 0884.90116 · doi:10.1023/A:1008293323270 |
| [8] | Glover, F., Kochenberger, G., Du, Y.: A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538 (2018) · Zbl 1428.90143 |
| [9] | Glover, F., Kochenberger, G., Du, Y.: Quantum bridge analytics i: a tutorial on formulating and using QUBO models. 4OR 17(4), 335-371 (2019) · Zbl 1428.90143 |
| [10] | Goh, S.T., Gopalakrishnan, S., Bo, J., Lau, H.C.: A hybrid framework using a QUBO solver for permutation-based combinatorial optimization. arXiv preprint arXiv:2009.12767 (2020) |
| [11] | Hiroshi, N., Junpei, K., Noboru, Y., Toshiyuki, M.: Third generation digital annealer technology (2021). https://www.fujitsu.com/global/documents/about/research/techintro/3rd-g-da_en.pdf |
| [12] | Hussain, A., Muhammad, Y.S., Nauman Sajid, M., Hussain, I., Mohamd Shoukry, A., Gani, S.: Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Comput. Intell. Neurosci. 2017 (2017) |
| [13] | Johnson, MW, Quantum annealing with manufactured spins, Nature, 473, 7346, 194-198 (2011) · doi:10.1038/nature10012 |
| [14] | Larranaga, P.; Kuijpers, CMH; Murga, RH; Inza, I.; Dizdarevic, S., Genetic algorithms for the travelling salesman problem: a review of representations and operators, Artif. Intell. Rev., 13, 2, 129-170 (1999) · doi:10.1023/A:1006529012972 |
| [15] | Lucas, A., Ising formulations of many np problems, Front. Phys., 2, 5 (2014) · doi:10.3389/fphy.2014.00005 |
| [16] | Matsubara, S., et al.: Digital annealer for high-speed solving of combinatorial optimization problems and its applications. In: 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 667-672. IEEE (2020) |
| [17] | Moraglio, A., Georgescu, S.: Ising machine data input apparatus and method of inputting data into an ising machine, December 2020. https://worldwide.espacenet.com/patent/search?q=pn |
| [18] | Regnier-Coudert, O.; McCall, J.; Bartz-Beielstein, T.; Branke, J.; Filipič, B.; Smith, J., Factoradic representation for permutation optimisation, Parallel Problem Solving from Nature - PPSN XIII, 332-341 (2014), Cham: Springer, Cham · doi:10.1007/978-3-319-10762-2_33 |
| [19] | Reinelt, G., TSPLIB-a traveling salesman problem library, ORSA J. Comput., 3, 4, 376-384 (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376 |
| [20] | Rosenberg, G.; Haghnegahdar, P.; Goddard, P.; Carr, P.; Wu, K.; De Prado, ML, Solving the optimal trading trajectory problem using a quantum annealer, IEEE J. Sel. Top. Signal Process., 10, 6, 1053-1060 (2016) · doi:10.1109/JSTSP.2016.2574703 |
| [21] | Santucci, V.; Baioletti, M.; Milani, A., Algebraic differential evolution algorithm for the permutation flowshop scheduling problem with total flowtime criterion, IEEE Trans. Evol. Comput., 20, 5, 682-694 (2015) · doi:10.1109/TEVC.2015.2507785 |
| [22] | Şeker, O., Tanoumand, N., Bodur, M.: Digital annealer for quadratic unconstrained binary optimization: a comparative performance analysis. arXiv preprint arXiv:2012.12264 (2020) |
| [23] | Takehara, K., Oku, D., Matsuda, Y., Tanaka, S., Togawa, N.: A multiple coefficients trial method to solve combinatorial optimization problems for simulated-annealing-based ising machines. In: 2019 IEEE 9th International Conference on Consumer Electronics (ICCE-Berlin), pp. 64-69. IEEE (2019) |
| [24] | Verma, A., Lewis, M.: Penalty and partitioning techniques to improve performance of QUBO solvers. Discrete Optim. 100594 (2020). doi:10.1016/j.disopt.2020.100594. https://www.sciencedirect.com/science/article/pii/S1572528620300281. Issn: 1572-5286 · Zbl 1510.90202 |
| [25] | Zaman, M., Tanahashi, K., Tanaka, S.: Pyqubo: python library for mapping combinatorial optimization problems to QUBO form. arXiv preprint arXiv:2103.01708 (2021) · Zbl 07568687 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
