ПРИВЕДЕНИЕ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ К ФОРМЕ QUBO

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Практические задачи дискретной оптимизации часто содержат многомерные массивы переменных с линейными ограничениями, что осложняет их приведение к форме QUBO (квадратичной бинарной оптимизации без ограничений). В статье предложен систематический подход к преобразованию таких задач, включающий три ключевых этапа: переход от многомерного представления переменных к одномерному с использованием произведения Кронекера матриц, приведение смешанных переменных к бинарным и введение линейных ограничений в целевую функцию через квадратичные штрафы. Для каждого этапа получены явные вычислительные формулы, упрощающие их программную реализацию. Разработанный метод проиллюстрирован на примерах задач теории графов и комбинаторной оптимизации, включая классические постановки, что подтверждает его универсальность. Результаты статьи позволяют стандартизировать процесс адаптации задач для решения на квантовых алгоритмах отжига (например, D-Wave) и классических QUBO-решателях.

Об авторах

А. М Семенов

Российский квантовый центр (ООО "МЦКТ"); ООО "Облачные квантовые технологии"

Email: a.semenov@rqc.ru
Москва; Москва

С. Р Усманов

Российский квантовый центр (ООО "МЦКТ"); ООО "Облачные квантовые технологии"

Email: s.usmanov@rqc.ru
Москва; Москва

А. К Федоров

Российский квантовый центр (ООО "МЦКТ"); ООО "Облачные квантовые технологии"

Email: akf@rqc.ru
Москва; Москва

Список литературы

  1. Castillo-Salazar J.A., Landa-Silva D., Qu R. Workforce Scheduling and Routing Problems: Literature Survey and Computational Study // Ann. Oper. Res. 2014. V. 239. №1. P. 39–67. https://doi.org/10.1007/s10479-014-1687-2
  2. Cook S.A. An Overview of Computational Complexity // Comm. ACM. 1983. V. 26. № 6. P. 400–408. https://doi.org/10.1145/358141.358144
  3. Arora R.K. Optimization: Algorithms and Applications. New York: Chapman & Hall/CRC, 2015. https://doi.org/10.1201/b18469
  4. Tian Y., Zhu W., Zhang X., Jin Y. A Practical Tutorial on Solving Optimization Problems via PlatEMO // Neurocomputing. 2023. V. 518. P. 190–205. https://doi.org/10.1016/j.neucom.2022.10.075
  5. Fedorov A.K., Gisin N., Beloussov S.M., Lvovsky A.I. Quantum Computing at the Quantum Advantage Threshold: A Down-to-Business Review. https://arXiv.org/abs/2203.17181 [quant-ph], 2022.
  6. Tiunov E.S., Ulanov A.E., Lvovsky A.I. Annealing by Simulating the Coherent Ising Machine // Opt. Express. 2019. V. 27. № 7. P. 10288–10295. https://doi.org/10.1364/OE.27.010288
  7. Farhi E., Goldstone J., Gutmann S., Sipser M. Quantum Computation by Adiabatic Evolution. https://arXiv.org/abs/quant-ph/0001106, 2000.
  8. Das A., Chakrabarti B.K. Colloquium: Quantum Annealing and Analog Quantum Computation // Rev. Mod. Phys. 2008. V. 80. № 3. P. 1061–1081. https://doi.org/10.1103/RevModPhys.80.1061
  9. Albash T., Lidar D.A. Adiabatic Quantum Computation // Rev. Mod. Phys. 2018. V. 90. № 1. P. 015002 (64 pp.). https://doi.org/10.1103/RevModPhys.90.015002
  10. McCollum J., Krauss T. QUBO Formulations of the Longest Path Problem // Theor. Comput. Sci. 2021. V. 863. P. 86–101. https://doi.org/10.1016/j.tcs.2021.02.021
  11. Papalitsas C., Andronikos T., Giannakis K., Theocharopoulou G., Fanarioti S. A QUBO Model for the Traveling Salesman Problem with Time Windows // Algorithms. 2019. V. 12. № 11. P. 224 (21 pp.). https://doi.org/10.3390/a12110224
  12. Alidaee B., Kochenberger G., Lewis K., Wang H. A New Approach for Modeling and Solving Set Packing Problems // European J. Oper. Res. 2008. V. 186. № 2. P. 504–512. https://doi.org/10.1016/j.ejor.2006.12.068
  13. Bomze I.M., Budinich M., Pardalos P.M., Pelillo M. The Maximum Clique Problem // Handbook of Combinatorial Optimization: Supplement Volume A. Boston, MA: Springer, 1999. P. 1–74. https://doi.org/10.1007/978-1-4757-3023-4_1
  14. Date P., Arthur D., Pusey-Nazzaro L. QUBO Formulations for Training Machine Learning Models // Sci. Rep. 2021. V. 11. P. 10029 (10 pp.). https://doi.org/10.1038/s41598-021-89461-4
  15. Farhi E., Neven H. Classification with Quantum Neural Networks on Near Term Processors. https://arXiv.org/abs/1802.06002 [quant-ph], 2018.
  16. Boev A.S., Usmanov S.R., Semenov A.M., Ushakova M.M., Salahov G.V., Mastiukova A.S., Kiktenko E.O., Fedorov A.K. Quantum-Inspired Optimization for Wavelength Assignment // Front. Phys. 2022. V. 10. P. 1092065 (11 pp.). https://doi.org/10.3389/fphy.2022.1092065
  17. Seker O., Bodur M., Pouya H. Routing and Wavelength Assignment with Protection: A Quadratic Unconstrained Binary Optimization Approach Enabled by Digital Annealer Technology // IISE Trans. 2024. V. 56. № 2. P. 156–171. https://doi.org/10.1080/24725854.2023.2193835
  18. Rahman M.T., Han S., Tadayon N., Valaee S. Ising Model Formulation of Outlier Rejection, with Application in WiFi Based Positioning // Proc. 2019 IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP 2019). Brighton, UK. May 12–17, 2019. P. 4405–4409. https://doi.org/10.1109/ICASSP.2019.8683807
  19. Phillipson F., Bhatia H.S. Portfolio Optimisation Using the D-Wave Quantum Annealer // Proc. 21st Int. Conf. on Computational Science (ICCS 2021). Krakow, Poland. June 16–18, 2021. Part VI. Lect. Notes Comp. Sci. V. 12747. Berlin, Heidelberg: Springer-Verlag, 2021. P. 45–59. https://doi.org/10.1007/978-3-030-77980-1_4
  20. Mugel S., Kuchkovsky C., S´anchez E., Fern´andez-Lorenzo S., Luis-Hita J., Lizaso E., Or´us R. Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks // Phys. Rev. Res. 2022. V. 4. № 1. P. 013006 (12 pp.). https://doi.org/10.1103/PhysRevResearch.4.013006
  21. Ratke D. List of QUBO Formulations, 2021. https://blog.xa0.de/post/List-of-QUBOformulations/ (accessed Feb. 20, 2025).
  22. Leap User Documentation Handbook. D-Wave Systems Inc., 2025. https://docs.dwavequantum.com/en/latest/index.html (accessed Mar. 20, 2025).
  23. Kochenberger G., Hao J.-K., Glover F., Lewis M., L¨u Z., Wang H., Wang Y. The Unconstrained Binary Quadratic Programming Problem: A Survey // J. Comb. Optim. 2014. V. 28. № 1. P. 58–81. https://doi.org/10.1007/s10878-014-9734-0
  24. Lucas A. Ising Formulations of Many NP Problems // Front. Phys. 2014. V. 2. P. 5 (15 pp.). https://doi.org/10.3389/fphy.2014.00005
  25. Glover F., Kochenberger G., Hennig R., Du Y. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models // Ann. Oper. Res. 2022. V. 314. № 1. P. 141–183. https://doi.org/10.1007/s10479-022-04634-2
  26. Asghari M., Fathollahi-Fard A.M., Mirzapour Al-e-hashem S.M.J., Dulebenets M.A. Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey // Mathematics. 2022. V. 10. № 2. P. 283 (26 pp.). https://doi.org/10.3390/math100202830
  27. Castro E.R., Martins E.O., Sarthour R.S., Souza A.M., Oliveira I.S. Improving the Convergence of an Iterative Algorithm for Solving Arbitrary Linear Equation Systems Using Classical or Quantum Binary Optimization // Front. Phys. 2024. V. 12. P. 1443977 (12 pp.). https://doi.org/10.3389/fphy.2024.1443977
  28. Veszeli M.T., Vattay G. Mean Field Approximation for Solving QUBO Problems // PLoS ONE. 2021. V. 17. № 8. P. e0273709 (12 pp.). https://doi.org/10.1371/journal.pone.0273709
  29. Kanao T., Goto H. Simulated Bifurcation Assisted by Thermal Fluctuation // Commun. Phys. 2022. V. 5. P. 153 (7 pp.). https://doi.org/10.1038/s42005-022-00929-9
  30. Drubin M. Kronecker Product Factorization of the FFT Matrix // IEEE Trans. Comput. 1971. V. 20. № 5. P. 590–593. https://doi.org/10.1109/T-C.1971.223306
  31. Frolkoviˇc P. Numerical Recipes: The Art of Scientific Computing // Acta Appl. Math. 1990. V. 19. № 3. P. 297–299. https://doi.org/10.1007/BF01321860
  32. Langville A.N., Stewart W.J. The Kronecker Product and Stochastic Automata Networks // J. Comput. Appl. Math. 2004. V. 167. № 2. P. 429–447. https://doi.org/10.1016/j.cam.2003.10.010
  33. Guo C., Berkhahn F. Entity Embeddings of Categorical Variables. https://arXiv.org/abs/1604.06737 [cs.LG], 2016.
  34. Pardalos P.M., Xue J. The Maximum Clique Problem // J. Glob. Optim. 1994. V. 4. № 3. P. 301–328. https://doi.org/10.1007/BF01098364
  35. Bondy J.A., Murty U.S.R. Graph Theory. New York: Springer, 2008.
  36. Loiola E.M., de Abreu N.M.M., Boaventura-Netto P.O., Hahn P., Querido T. A Survey of the Quadratic Assignment Problem // European J. Oper. Res. 2007. V. 176. №2. P. 657–690. https://doi.org/10.1016/j.ejor.2005.09.032
  37. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Berlin, Heidelberg: Springer, 2004. https://doi.org/10.1007/978-3-540-24777-7
  38. Semenov A.M., Usmanov S.R., Fedorov A.K. Technique for Transforming Discrete Optimization Problems into QUBO Form // Probl. Inf. Transm. 2025. V. 61. № 2 (to appear).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».