Полуопределенная оптимизация для решения квадратичных задач с булевыми переменными

Abstract

RU: Цель. В работе рассматривается класс задач квадратичной оптимизации с булевыми переменными. Такие задачи возникают в области рыночной экономики, планировании, управлении проектами, искусственном интеллекте, оптимальном проектировании и являются NP-сложными. В данной работе предлагается процедура для нахождения нижних и верхних оценок целевых функций квадратичных задач с булевыми переменными. Методика. В данной работе предлагается преобразовывать квадратичные задачи с булевыми переменными в общую задачу квадратичной оптимизации, а затем применять для ее решения метод полуопределенной релаксации. Результаты. Применение полуопределенной релаксации позволило находить нижние оценки целевой функции в квадратичных задачах с булевыми переменными или точку глобального минимума с заданной точностью. Причем, в отличие от других методов, проверка оптимальности найденного решения не требует экспоненциального времени и достаточно проста. Верхняя оценка целевой функции, которая находится с помощью использования нижней оценки полуопределенной релаксации в качестве начальной точки при решении исходной задачи методами локального поиска, в 91 % случаев совпала с глобальным минимумом начальной задачи. Научная новизна. Разработана новая процедура нахождения верхних и нижних оценок целевой функции. Практическая значимость. Рассмотренная методика решения может быть использована для нахождения решения прикладных задач, которые могут быть сформулированы в виде квадратичных задач с булевыми переменными. Сравнительные эксперименты подтверждают эффективность данного подхода для решения таких задач.

UK: Мета. У роботі розглядається клас задач квадратичної оптимізації з булевими змінними. Такі задачі виникають в області ринкової економіки, планування, управління проектами, штучному інтелекті, оптимальному проектуванні та є NP-складними. У даній роботі пропонується процедура для знаходження нижніх і верхніх оцінок цільових функцій квадратичних задач з булевими змінними. Методика. У даній роботі пропонується перетворювати квадратичні задачі з булевими змінними в загальну задачу квадратичної оптимізації, а потім застосовувати для її розв'язання метод напіввизначеної релаксації. Результати. Застосування напіввизначеної релаксації дозволило знаходити нижні оцінки цільової функції в квадратичних задачах з булевими змінними або точку глобального мінімуму з заданою точністю. Причому, на відміну від інших методів, перевірка оптимальності знайденого розв'язку не вимагає експоненціального часу і є досить простою. Верхня оцінка цільової функції, яка знаходиться за допомогою використання нижньої оцінки напіввизначеної релаксації в якості початкової точки під час розв'язування вихідної задачі методами локального пошуку, в 91% випадків збіглася з глобальним мінімумом початкової задачі. Наукова новизна. Розроблено нову процедуру знаходження верхніх і нижніх оцінок цільової функції. Практична значимість. Розглянута методика розв'язання може бути використана для знаходження розв'язку прикладних задач, які можуть бути сформульовані у вигляді квадратичних задач з булевими змінними. Порівняльні експерименти підтверджують ефективність даного підходу для розв'язування таких задач.

EN: Purpose. We consider boolean quadratic optimization problems. Such problems arise in market economy, planning, project management, artificial intelligence, optimal design and are NP-hard. In this paper we propose a procedure for finding the lower and upper bounds of the objective functions of boolean quadratic problems. Methodology. In this paper we propose to convert the boolean quadratic problem to the general quadratic optimization problem, and then apply semi definite relaxation to it. Findings. The using of semidefinite relaxation has allowed us to find lower bounds of the objective function or global minimum point with a given accuracy in boolean quadratic problems. Moreover, unlike other methods, testing the optimality of the found solution doesn`t require exponential time and is quite simple. The upper bound of the objective function, which is found by using the lower es timate of semidefinite relaxation as a starting point for solving the original problem by local search methods, in 91% of cases coincided with the global minimum of the initial problem. Originality. A new procedure for finding the upper and lower bounds of objective function was proposed. Practical value. The considered method of solution can be used for finding the solution in applications that can be formulated as boolean quadratic problems. Comparative numerical experiments confirm the efficiency of this approach to solvin g such problems.