Скорость CPLEX против CPLEX с использованием SCIP

Question

Я новичок в LP и только кратко использовал PuLP в Python.

1. Почему разница в скорости между SCIP 3.2.1 - CPLEX 12.63 а также CPLEX 12.6.3? Разве SCIP все еще не использует CPLEX для решения?

2. Почему кто-то будет использовать SCIP с решателем CPLEX, а не использовать CPLEX напрямую?

Answer 1

В чем эта разница

На этом графике показан не LP-тест, а тест на смешанное целочисленное программирование.

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

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

SoPlex является реализацией LP-solver команды SCIP. Имея в виду:

• SCIP - SoPlex будет использовать алгоритм SCIP для MIP (обработка ветвления, генерации срезов и др.) С использованием SoPlex в качестве решателя для внутренних подзадач LP
• SCIP - CPLEX будет использовать алгоритм SCIP для MIP с использованием CPLEX в качестве решателя для внутренних подзадач LP

Зачем использовать SCIP с CPLEX (вместо использования чистого подхода CPLEX)

Почему это не так просто объяснить.

• Имейте в виду, что все MIP-решатели основаны на эвристике и в некоторых случаях SCIP будет быстрее, чем CPLEX(несмотря на выбранный базовый LP-решатель).

  Ключевые слова для некоторой теории:NP-твердость(MIP) и теорема об отсутствии бесплатного обеда

  • Быстрее может означать: быстрее благодаря стратегиям, основанным на MIP, а не скорости основного LP-решателя, так что вы можете даже получить общее ускорение, используя CPLEX для подзадач!

• Два решателя (MIP-решатели), вероятно, также сильно различаются в отношении параметров и доступности (внутренних алгоритмических компонентов). Очевидно, что вы можете настроить SCIP гораздо более общим способом, чем CPLEX (потому что он с открытым исходным кодом)

• Как упомянул в комментариях mattmilten: SCIP и CPLEX также различаются в отношении поддержки проблемных классов, которые могут быть решены. Одним из примеров этого может быть возможность для некоторых специальных нелинейных ограничений (приводящих к MINLP). Используя SCIP для подобных проблем, все еще можно использовать LP-решатель CPLEX для внутреннего использования (те же аргументы, что и выше)