В чем разница между целочисленным квадратичным программированием и смешанным целочисленным квадратичным программированием?

#optimization #quadratic-programming #branch-and-bound

#оптимизация #квадратичное программирование #переход с привязкой

Вопрос:

Я новичок в задаче оптимизации квадратичного программирования. В уравнении 8 следующей статьи: здесь имеется уравнение:

Авторы утверждают, что это 'Integer Quadratic Programming (IQP)' формула.

В качестве альтернативы, на другом веб-сайте: здесь есть следующее уравнение, которое описывается как формулировка ‘ Mixed Integer Quadratic Programming ( MIQP )’:

С моей точки зрения, оба уравнения, показанные выше, похожи, с той лишь разницей, что в MIQP формулу включено ‘1/2’.

1) Я ищу объяснение различий между IQP и MIQP

2) Кроме того, мне интересно применить квадратичное программирование к задаче присваивания, таким образом, я ищу какое-либо представление о том, что следует использовать (т. Е. IQP против MIQP ) и когда.

Ответ №1:

Целочисленно-квадратичное программирование (IQP) подразумевает, что в модели нет непрерывных переменных: все переменные дискретны. Смешанное целочисленно-квадратичное программирование (MIQP) допускает как дискретные, так и непрерывные переменные. Если ваша модель имеет только дискретные переменные, это и MIQP, и IQP. Все популярные решатели имеют тип MIQP, поэтому я склонен использовать MIQP, даже если у меня нет непрерывных переменных. IQP как тип модели используется не часто. Я не думаю, что об этом действительно стоит беспокоиться.

1. Эрвин, итак, вы бы сказали, что если бы в статье использовался MIQP (с уравнением 8, опубликованным выше), это дало бы точно такое же решение, как IQP? Также не могли бы вы указать мне на простое сравнение MIQP с IQP в Python или R.

2. Эрвин, у меня недостаточно опыта в QP, чтобы знать, что там в терминах решателей. С другой стороны, не уверен, знаете ли вы какой-либо исходный код, на который вы могли бы мне указать, но я также ищу пример задачи присваивания с использованием MIQP. Приветствия.

3. Как уже было сказано, это в значительной степени не проблема. Нет причин не использовать решатель MIQP для чисто целочисленных задач. Существует много различных проблем с назначением, поэтому на этот вопрос трудно ответить.