Как помешать Гуроби конвертировать Макс в мин проб?
Я использую Gurobi (через C ++) как часть моей магистерской диссертации, чтобы решить Квадратичный случай рюкзака. До сих пор мне удавалось генерировать модель с бинарными переменными решения, квадратичной целевой функцией и ограничением емкости, и Гуроби решил ее просто отлично. Тогда я хотел решить проблему непрерывной релаксации QKP. Я построил модель, как и прежде, но с непрерывными переменными вместо двоичных, и Гуроби бросил мне исключение, когда я попытался оптимизировать его:
10020 - Objective Q not PSD (negative diagonal entry)
Это немного смутило меня, так как все значения, образующие проблему, равны ≥0. Готовясь опубликовать этот вопрос, я выписал обе модели в файл и обнаружил причину:
NAME (null)
* Max problem is converted into Min one
Что, конечно, означает, что все ранее положительные значения теперь отрицательны. Теперь я знаю, почему Q не PSD, но как мне это исправить? Могу ли я предотвратить преобразование проблемы Макса в проблему Мин? Нужно ли по-разному настраивать модель для непрерывного расслабления?
С моей (неопытной) точки зрения это выглядит так, будто Гуроби выстрелил себе в ногу.
Решение
Когда вы максимизируете квадратичную цель с помощью Gurobi или любого другого выпуклого оптимизатора, ваша матрица ‘Q’ должна быть отрицательно-полуопределенной, а когда вы минимизируете, ваша матрица ‘Q’ должна быть положительно определенной. Изменение знака и смысла цели ничего не меняет.
Гуроби не проверяет, является ли ваша проблема выпуклой, но он сообщит о любой невыпуклости, которую обнаружит. Тот факт, что ваша первоначальная проблема, похоже, решается как MIP, является случайностью, и вы не должны полагаться на нее.
Вы должны смоделировать квадратную задачу с двоичными переменными как линейную задачу с некоторыми простыми преобразования. Если x и y являются двоичными, выражение x*y можно изменить на z если вы добавите ограничения
z <= x
z <= y
z >= x + y - 1
Другие решения