В чем разница между симплексным методом и сетевым симплексом?

Question

Я использую сеть Simplex для решения проблемы максимального потока в ориентированных графах.Чтобы сравнить время выполнения для нескольких алгоритмов маршрутизации, мне нужно использовать реализацию симплекс-метода Данцига Джорджа.

У меня вопрос : может ли симплекс-метод решить проблему максимального потока вданный ориентированный граф?

Есть ли хорошая документация, объясняющая симплекс-метод в теории графов?

Answer 1

Сетевой симплекс-метод является узкоспециализированной формой общего симплекс-метода: он может решать только сетевые проблемы.

Конечно, стандартный симплекс-метод для линейного программирования может также решить проблемы сети, просто сформулировав проблему сети как проблему LP.

Для сравнения вам может понадобиться взглянуть на Cplex: у него есть реализации (простого и двойственного) симплекс-метода для линейного программирования и сетевой симплекс-метод.

Интересно, что у Гуроби нет сетевого симплекс-метода. За этим стоит мысль, что LP-решатели стали настолько быстрыми, что специализированные сетевые решатели утратили некоторые из своих преимуществ в скорости.

Хороший справочник: Ахаджа, Магнанти и Орлин, Сетевые потоки.