Численная проблема со SCIP: та же проблема, разные оптимальные значения - PullRequest
Новая
       26

Численная проблема со SCIP: та же проблема, разные оптимальные значения

0 голосов
/ 16 апреля 2020

У меня возникла следующая числовая проблема при использовании решателя SCIP в качестве вызываемой библиотеки через PySCIPOpt:

две эквивалентные и почти идентичные модели для одной и той же задачи дают разные оптимальные значения и оптимальные решения с оптимальными значениями, имеющими относительную разность порядка 1e-6

Независимая часть программного обеспечения подтвердила, что решения, предложенные обеими моделями, выполнимы для исходной задачи и что их истинные значения соответствуют оптимальным значениям, сообщенным SCIP для каждой модели . До появления этого экземпляра было решено множество экземпляров одной и той же проблемы, причем обе модели всегда соглашались на свои оптимальные решения и значения.

Можно ли изменить числовую точность SCIP для сравнивая значения первичных решений среди них и с двойными границами? Какие параметры должны быть изменены, чтобы преодолеть эту числовую трудность?

Что я пробовал

Я пробовал следующие вещи, и проблема сохранялась:

  1. Отключение предварительного разрешения с помощью model.setPresolve(SCIP_PARAMSETTING.OFF).
  2. Настройка model.setParam('numerics/feastol', epsilon) с различными значениями epsilon.

Поскольку допустимые множества и целевые функции совпадают (см. Описание ниже), я ' мы проверили, что фактические коэффициенты целевых функций совпадают, вызвав model.getObjective() и сравнив коэффициенты на равенство для каждой переменной, фигурирующей в целевой функции.

Единственное, что, казалось, помогло, это добавить некоторый шум (умножение числами вида 1+eps с малыми eps) на коэффициенты в целевой функции модели, дающей худшее решение. Это заставляет SCIP выдавать одинаковое (и лучшее) решение для обеих моделей, если eps находится в определенном диапазоне.

На всякий случай, вот что я получаю с scip -v в терминале:

SCIP версия 6.0.2 [точность: 8 байт] [память: блок] [режим: оптимизированный] [LP solver: SoPlex 4.0.2] [GitHa sh: e639a0059d]

Описание моделей

Модель (I) имеет приблизительно 30 КБ двоичных переменных, скажем X[i] для i в некотором наборе индексов I. Это выполнимый и не сложный MIP.

Модель (II) имеет те же переменные модели (I) плюс ~ 100 непрерывных переменных, скажем Y[j] для j в некотором наборе индексов J. Также модель (II) имеет некоторые ограничения, подобные этому X[i_1] + X[i_2] + ... + X[i_n] <= Y[j].

Обе целевые функции согласуются и зависят только от X[i] переменных, смысл в минимизации. Обратите внимание, что переменные Y[j] по существу свободны в модели (II), поскольку они непрерывны и не появляются в целевой функции. Очевидно, что нет смысла включать переменные Y[j], но оптимальные значения не должны отличаться.

Модель (II) - это та, которая дает лучшее (то есть меньшее) значение.

...