By this author

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

Issue number 2 from 18.08.2025

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

32 0