Гуроби сообщает о неограниченной модели, несмотря на математическую невозможность

Я использую замечательный пакет JuMP Джулии для решения линейной программы с Gurobi 6.0.4 в качестве решателя. Целевая функция - это сумма переменных решения, четко определенная как неотрицательная, и проблема требует ее минимизации. По какой-то причине Гуроби считает эту модель безграничной.

Вот определение переменных и цели:

@defVar(model, delta2[i=irange,j=pair[i]] >= 0)
@setObjective(model, Min, sum{delta2[i,j], i=irange, j=pair[i]})

Странное наблюдение №1: хотя это проблема минимизации, журнал для метода Gurobi BarrierSolve ясно показывает, что целевая функция увеличивается на каждой итерации. Вдобавок Гуроби, кажется, переключает между количеством строк и столбцов. Перед этапом предварительного решения модель имеет 50 тыс. Строк и 25 тыс. Столбцов. После этапа предварительного вычисления (который удаляет менее 1 тыс. Строк и столбцов) у нас есть 24 тыс. Строк и 50 тыс. Столбцов. Журнал выглядит так:

Optimize a model with 50422 rows, 24356 columns and 1846314 nonzeros
Coefficient statistics:
  Matrix range    [1e-04, 2e+00]
  Objective range [1e+00, 1e+00]
  Bounds range    [9e-02, 2e+02]
  RHS range       [6e+00, 4e+03]
Presolve removed 164 rows and 635 columns
Presolve time: 0.79s
Presolved: 24192 rows, 49787 columns, 1836247 nonzeros
Ordering time: 1.60s

Странное наблюдение №2: BarrierSolve в конечном итоге завершается со статусом InfeasibleOrUnbounded. Затем он предлагает установить InfUnbdInfo=1 и использовать гомогенный метод Gurobi BarrierSolve, установив BarHomogeneous=1. Когда я делаю обе эти вещи, целевая функция продолжает увеличиваться (!), А журнал барьеров выглядит так:

                      Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0  -6.95693531e+06  1.94975493e+02  1.10e+01 9.79e+02  1.39e+03     4s
   1  -3.18487510e+06  7.02065119e+06  5.50e-01 5.57e+02  3.45e+02     5s
   2  -8.43175324e+05  2.31465924e+06  4.81e-02 1.60e+02  9.32e+01     6s
   3  -2.37967254e+05  6.66124613e+05  6.51e-03 3.69e+01  2.35e+01     8s
   4  -7.49693243e+04  1.81252940e+05  1.64e-03 9.49e+00  6.46e+00     9s
   5  -3.20211009e+04  8.98339452e+04  6.25e-04 5.30e+00  3.11e+00    10s
   6  -1.04312874e+04  5.17677474e+04  2.06e-04 3.06e+00  1.65e+00    11s
   7   4.58252702e+02  4.04538611e+04  1.24e-04 2.19e+00  1.23e+00    12s
   8   3.40831629e+04  5.42543944e+04  7.65e-05 1.87e+00  1.54e+00    13s
   9   3.10110459e+05  2.25902448e+05  5.50e-05 1.87e+00  6.81e+00    15s
  10   1.59299448e+06  9.88980682e+05  5.73e-05 1.85e+00  3.37e+01    16s
  11*  1.88981433e+07  1.28711401e+07  2.93e-06 6.92e-01  1.14e-03    17s
  12*  1.65096505e+08  3.73470456e+08  5.57e-06 5.73e-02  1.40e-04    18s
  13*  7.18252597e+09  3.21890978e+09  2.62e-06 2.01e-03  4.60e-06    20s
  14*  1.15822505e+12  7.53575462e+10  1.50e-05 6.18e-06  8.50e-09    21s
  15*  1.08512896e+13  2.57735417e+12  2.92e-06 6.99e-08  1.22e-10    22s
  16*  3.03152292e+14  7.54681485e+13  1.21e-07 7.50e-10  1.28e-12    23s

Barrier performed 16 iterations in 23.41 seconds
Unbounded model

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

РЕДАКТИРОВАТЬ: Я нашел частичное решение проблемы, ослабив некоторые ограничения и искусственно улучшив область выполнимости. Похоже, проблема была действительно вопросом осуществимости, а не вопросом неограниченности, что означает, что Гуроби мог на самом деле иметь в виду неограниченность дуального?

Спасибо за вашу помощь!


person Art    schedule 21.07.2015    source источник
comment
Можете ли вы опубликовать больше кода? Кроме того, можете ли вы попробовать установить верхнюю границу для переменных, чтобы убедиться, что она не ограничена?   -  person IainDunning    schedule 21.07.2015
comment
Кроме того, какая версия Гуроби? Вы также можете попробовать записать модель в LP-файл, чтобы на 100% убедиться, что ничего странного не происходит.   -  person IainDunning    schedule 21.07.2015
comment
Bounds range [9e-02, 2e+02] предполагает, что могут быть другие переменные?   -  person IainDunning    schedule 21.07.2015
comment
На самом деле существуют и другие переменные, но я не понимаю, почему это должно иметь значение ... Суть в том, что единственные переменные, присутствующие в целевой функции, обязательно неотрицательны, и поэтому неограниченность не имеет смысла.   -  person Art    schedule 21.07.2015
comment
О, я ценю это, но происходит что-то неочевидное, поэтому я просто пытаюсь выяснить, где ошибка.   -  person IainDunning    schedule 21.07.2015
comment
Я почти уверен, что это числовая проблема, но я не понимаю, во что играет Гуроби со своими шарадами о неограниченности / невозможности.   -  person Art    schedule 21.07.2015
comment
Не могли бы вы заставить его использовать симплексный метод? У вас есть ограничения диапазона с очень узким диапазоном?   -  person IainDunning    schedule 21.07.2015
comment
Остальная часть LP довольно сложна, и в ней много чего происходит, поэтому я не уверен, что вы хотите просматривать весь код.   -  person Art    schedule 21.07.2015
comment
Я попытался заставить его использовать симплекс, но он плохо подходит для этого конкретного LP и на самом деле не сходится. И да, у меня есть много ограничений диапазона с очень узким диапазоном! Именно ослабление тесноты этих ограничений снимает эту проблему.   -  person Art    schedule 21.07.2015


Ответы (1)


Ваша проблема плохо обусловлена ​​из-за ограничений "узкого" диапазона. Если они действительно должны быть ограничениями диапазона, подумайте о масштабировании вашей проблемы. Если они больше похожи на «приблизительные» ограничения равенства, рассмотрите возможность добавления переменной резерва и превращения ее в фактическое ограничение равенства и наложите штраф на слабины в цели.

person IainDunning    schedule 21.07.2015