LP удваивает и снижает затраты с CPLEX - PullRequest
Новая
       16

LP удваивает и снижает затраты с CPLEX

1 голос
/ 17 мая 2019

Я работаю над алгоритмом генерации столбцов, использующим CPLEX для решения уменьшенной основной задачи.

После добавления новых переменных в RMP я устанавливаю их верхние границы равными 0, снова решаю RMP и извлекаю их уменьшенные затраты (чтобы проверить, соответствует ли рассчитанное мной значение значению, предоставленному CPLEX).

На первых итерациях приведенные затраты совпадают.

Однако после некоторых итераций я начинаю получать другую сниженную стоимость.

Когда я запускаю CPLEX Interative Optimizer, читаю модель LP (или MPS) и сравниваю двойные ограничения, я получаю несколько разных значений.

Есть ли смысл?

Я пытался использовать разные методы для решения моей LP Также попытался изменить допуски.

Статистика проблем 

Objective sense      : Minimize
Variables            :  453308  [Fix: 8,  Box: 453300]
Objective nonzeros   :    6545
Linear constraints   :  578166  [Less: 70814,  Greater: 503886,  Equal: 3466]
  Nonzeros           : 2710194
  RHS nonzeros       :    7986

Variables            : Min LB: 0.0000000        Max UB: 74868.86
Objective nonzeros   : Min   : 0.01000000       Max   : 10000.00
Linear constraints   :
  Nonzeros           : Min   : 0.004000000      Max   : 396.8800
  RHS nonzeros       : Min   : 0.01250000       Max   : 74868.86

Отображение качества решения Я получаю следующую информацию: 

Max. unscaled (scaled) bound infeas.        = 8.52651e-014 (3.33067e-015)
Max. unscaled (scaled) reduced-cost infeas. = 2.24935e-010 (5.62339e-011)
Max. unscaled (scaled) Ax-b resid.          = 5.90461e-011 (3.69038e-012)
Max. unscaled (scaled) c-B'pi resid.        = 2.6489e-011 (7.27596e-012)
Max. unscaled (scaled) |x|                  = 45433 (2839.56)
Max. unscaled (scaled) |slack|              = 4970.49 (80.1926)
Max. unscaled (scaled) |pi|                 = 295000 (206312)
Max. unscaled (scaled) |red-cost|           = 411845 (330962)
Condition number of scaled basis            = 1.1e+008

Ответы [ 2 ]

3 голосов
/ 21 мая 2019

Как уже упоминалось в комментарии Эрвина, то, что вы испытываете, - это, вероятно, вырождение.

И первичное, и двойственное решения часто не уникальны в задачах, больших, чем игрушечная модель.

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

Видите ли вы итерации в журнале?

В качестве отладки попробуйте выписать модель перед исправлением и после, а затем выполните diff для этих двух файлов, чтобы убедиться, что на вашей стороне нет ошибки моделирования / программирования.

Вы также можете связаться со мной по адресу bo.jensen (at) dk (dot) ibm (dot) com, и я постараюсь помочь вам, поскольку я не очень внимательно слежу за переполнением стека.

2 голосов
/ 21 мая 2019

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

Этот тип случайного пропуска обычно происходит, когда сгенерированные переменные создаются с верхней границей.

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

...