Как получить доступ к решению для двойного симплексного решателя?

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

Minimize
obj: [ a^2 - 2 a * b + b^2 ] / 2
Subject To
c1: a + b >= 10
c2: a <= 100
End

Я использую Python API для решения проблемы следующим образом:

import cplex

cpx = cplex.Cplex()
cpx.read('quadratic_obj_so.lp')  
# use the dual simplex   
cpx.parameters.lpmethod.set(cpx.parameters.lpmethod.values.dual)
cpx.solve()
print cpx.solution.get_values()[0:15]
print cpx.solution.status[cpx.solution.get_status()]
print cpx.solution.get_objective_value()

И для приведенного выше примера я получаю (показаны только итерации 16-18):

Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
  16   1.4492800e-19  -1.0579911e-07  3.81e-14  7.11e-15  5.17e-25
  17   9.0580247e-21  -2.6449779e-08  1.91e-14  3.55e-15  2.33e-25
  18   5.6612645e-22  -6.6124446e-09  5.45e-14  7.11e-15  6.46e-27

[73.11695794600045, 73.11695794603409]
optimal
0.0

поэтому a и b равны, что имеет смысл, поскольку я стараюсь минимизировать их расстояние, и ограничения явно выполняются.

Однако моя настоящая проблема намного сложнее, и я получаю:

Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
92   1.4468496e+06   1.2138985e+06  1.80e+02  2.64e-12  5.17e-02
  93   1.4468523e+06   1.2138969e+06  2.23e+02  2.17e-12  1.08e-02
  94   1.4468541e+06   1.2138945e+06  2.93e+02  2.31e-12  5.62e-02
  *    1.4457132e+06   1.2138598e+06  7.75e+00  7.61e-09  2.76e-02

num_best
1445714.46525

Теперь у меня есть несколько вопросов относительно вывода, которые тесно связаны:

1) Ясно, что это не объективное значение для напечатанного двойного симплекса. Почему это так, если я установил в качестве решателя двойной симплекс ?!

2) Как мне теперь получить доступ к результатам для двойного симплекса? Поскольку объективное значение меньше, меня бы больше интересовали эти результаты.

3) Гарантирует ли статус num_best, что все ограничения соблюдены, т. Е. Действительно ли решение, но только не гарантировано, что оно будет оптимальным?

4) Primal Obj и Dual Obj очень сильно различаются. Есть ли стратегия минимизировать их разницу?


person Cleb    schedule 18.04.2016    source источник
comment
Я не думаю, что это журнал из двойного симплекса, а скорее из барьерного метода. Также обратите внимание, что решение QP обычно не выполняется с помощью метода Simplex LP.   -  person Erwin Kalvelagen    schedule 19.04.2016
comment
@ErwinKalvelagen: спасибо за комментарий! Что бы вы порекомендовали вместо этого?   -  person Cleb    schedule 19.04.2016
comment
Сначала я хотел бы рассмотреть некоторые возможные переформулировки. Постарайтесь переместить как можно больше логики из цели в линейные ограничения (например, (x + y) ^ 2 можно записать как z ^ 2 с z = x + y). Также посмотрите на масштабирование. Попробуйте опцию Cplex numericalEmphasis.   -  person Erwin Kalvelagen    schedule 19.04.2016
comment
Хорошая идея, спасибо!   -  person Cleb    schedule 19.04.2016


Ответы (1)


  1. Насколько мне известно, get_objective_value всегда возвращает лучшую первичную границу (независимо от метода lp).
  2. Информацию о двойном решении можно получить с помощью get_dual_values ​​.
  3. Статус решения num_best означает, что решение доступно, но нет доказательства его оптимальности (см. здесь). Это, наверное, самый важный момент по отношению к остальным вопросам.
  4. Вы можете попробовать включить числовой акцент, чтобы проверить, поможет ли это. Вы также можете настроить различные допуски (например, допуск оптимальности).

Обратите внимание, что все ссылки, которые я использовал выше, относятся к C Callable Library (которую Python API вызывает внутренне) для CPLEX 12.6.3.

person rkersh    schedule 18.04.2016
comment
Спасибо за этот подробный ответ (я проголосовал за него и принимаю позже)! Что касается пункта 3, просто чтобы убедиться: возвращенное решение является действительным (ни одна из границ не нарушена), но невозможно доказать, является ли оно оптимальным. Это верно? К настоящему времени я думаю, что было бы лучше выразить разницу между переменными не как (x1 - x2)^2 + (x2-x3)^2 + ..., а как abs(x1-x2) + abs(x2-x3) + .... Разумеется, последнее выражение необходимо линеаризовать. Вы знаете примеры, когда сумма абсолютных различий была сведена к минимуму? - person Cleb; 18.04.2016
comment
Нет, со статусом решения num_best я не думаю, что вы можете предположить, что решение действительно. Если я правильно понимаю, вы можете найти этот блог на абсолютном ценности интересные. В объектно-ориентированном API (C ++, Java, .NET) вы можете использовать abs. - person rkersh; 18.04.2016
comment
Хорошо, спасибо, эта запись в блоге действительно полезна. Успели проверить пункт 1)? - person Cleb; 19.04.2016
comment
Я поспрашивал и провел некоторое тестирование с обратным вызовом и установкой ограничений итераций. Я считаю, что пункт 1) верен, и я сделал здесь утверждение немного сильнее. - person rkersh; 19.04.2016
comment
Ссылка на метод abs не работает. Есть ли планы включить это также в API Python? - person Cleb; 08.01.2019
comment
Обновленную ссылку для метода IloModeler.abs можно найти здесь. Если он снова устареет, его можно найти, перейдя в Справочное руководство CPLEX Java ›ilog.concert› Интерфейсы ›IloModeler› abs. - person rkersh; 08.01.2019
comment
Хотя abs недоступен в CPLEX Python API (API низкого уровня), он доступен в DOcplex (язык моделирования Python, который работает поверх CPLEX Python API или может использоваться для решения в облаке). См. Метод docplex.mp.model.abs здесь. - person rkersh; 08.01.2019
comment
Большое спасибо за ссылки! DOcplex на первый взгляд выглядит довольно привлекательно, посмотрю; действительно может значительно упростить мою текущую проблему. - person Cleb; 09.01.2019