Максимизация линейного объектива с учетом квадратичных ограничений

Question

У меня есть программная формулировка из статьи, и я хочу дать ей инструмент для решения конкретных задач. Авторы назвали это экземпляром линейного программирования (LP), однако я не уверен. Формулировка выглядит примерно так:

max x1+x2+x3...

s.t.

x1.x3+x4.x5 <= 10

x2.x5+x3.x7+x1.x9 <=10

...

Я пытался запрограммировать это через cplexqcp функция (из-за квадратичных ограничений, однако ограничения не включают в себя x_i^2 переменная). Однако я получаю CPLEX Error 5002: Q in %s is not positive semi-definite error, Является ли это примером нелинейного программирования с невыпуклыми ограничениями? Могу ли я решить это с CPLEX или использовать NLP инструмент для этого? Я новичок в LP/NLP Персонал (не проходите никаких курсов по ним), поэтому, пожалуйста, помогите объяснить детали ответов на мои вопросы.

Спасибо.

Answer 1

Проблема, которую вы опубликовали, нуждается в некоторой информации о домене переменных x1, x2 и x3.

Если они непрерывны, то нет способа выразить вашу проблему в виде линейной программы (LP), поскольку поверхность x1*x2 просто нелинейна.

Если хотя бы одна из переменных продукта является двоичной (целочисленной), продукт может быть линеаризован (например, если у вас смешанная целочисленная программа), как описано здесь, - так как "границы" вышеупомянутого продукта являются линейными.

Cplex может в основном решить некоторые классы квадратичных задач. Судя по вашему сообщению об ошибке, ваша проблема не относится к этому. Таким образом, для решения этой проблемы вам, вероятно, потребуется придерживаться решения НЛП общего назначения. Примерный список решателей можно найти здесь, каждый из которых может быть запущен программным обеспечением AMPL или может использоваться автономно. Я не эксперт здесь, поэтому я не могу дать совет, какой решатель должен быть предпочтительным для вашей проблемы.

С уважением, Мартин