Недостатки избегания кроссовера после решения барьера в линейной программе

Question

Я запускаю большой LP (приблизительно 5 М без нулей), и я хочу ускорить процесс решения. Я попытался выполнить параллельную работу, чтобы проверить, какой алгоритм решает мою проблему быстрее всего, и я обнаружил, что метод барьера является явным победителем (solver = Xpress MP, но я думаю, что это было бы одинаково для других решателей).

Однако я хочу еще больше ускорить его. Я заметил, что решение реального барьера занимает менее 1% от общего времени решения. Остальная часть времени тратится на кроссовер (~ 40%), а первичный решает (найти угловое решение на новом основании) (~ 60%). К сожалению, я не мог найти настройки, чтобы сказать ему сделать двойной кроссовер (есть один в Cplex, но у меня нет лицензии на Cplex). Поэтому я не мог сравниться, если это будет быстрее.

Поэтому я попытался отключить кроссовер, который дает огромное увеличение скорости, но есть некоторые недостатки в соответствии с документацией. До сих пор недостатки, о которых я знаю, являются следующими:

• Барьерные решения, как правило, являются решениями средней части.
• Барьер без кроссовера не создает базового решения (хотя в настройках решателя упоминается, что «Полное первичное и двойное решение доступно независимо от того, используется ли кроссовер»).
  • Без основы вы не сможете повторять одинаковые или подобные проблемы повторно, используя расширенную начальную информацию.
  • Без основы вы не сможете получить информацию о диапазоне для проведения анализа чувствительности.

Мой вопрос (ы) является (являются) просто. Какие еще недостатки важны для оправдания очень неэффективного шага кроссовера (как Cplex, так и Xpress MP позволяют использовать кроссовер в качестве настройки по умолчанию). В качестве альтернативы, является ли моя проблема исключительной и является ли кроссовер очень быстрым в других проблемах? Наконец, что не так с помощью решений средней части (это означает, что оптимальный угол также не уникален)?

Источники:

• http://www.cs.cornell.edu/w8/iisi/ilog/cplex101/usrcplex/solveBarrier2.html (Барьер теория алгоритмов высокого уровня)
• http://tomopt.com/docs/xpress/tomlab_xpress008.php (настройки решателя Xpress MP)

Answer 1

Главный недостаток: решение будет "некрасиво", то есть много 0,000001 и 0,9999999 в значениях решения. Во-вторых, вы можете получить несколько разные дуальности. Наконец, требуется основа для быстрого «горячего запуска». Одним из возможных способов ускорения работы больших моделей является использование симплекс-метода и использование расширенной основы от типичного базового прогона.