Получение 10 лучших неоптимальных решений, вычисленных решателем GLPK для LP в python

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

Моя проблема в том, что я хочу получить и неоптимальные решения. Есть ли способ получить 10 лучших неоптимальных решений от GLPK?

Лучший


python routes network-traffic glpk linear-programming
person Shahrooz Pooryousef    schedule 16.11.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Для чистого LP (только с непрерывными переменными) концепция поиска следующих лучших решений очень сложна (просто отодвиньте эпсилон, и вы получите другое решение). Мы можем определить это по-другому: найти следующие лучшие угловые точки (также известные как основания). Это не так просто сделать, но есть несколько сложный способ кодирования базисов с использованием бинарных переменных (ссылка).

Если проблема на самом деле является MIP (с двоичными переменными), легче найти следующие лучшие решения. Некоторые продвинутые решатели имеют для этого встроенные средства (называемые: пул решений). Примечание: glpk не имеет этой опции. В качестве альтернативы мы также можем сделать это, добавив отсечение, которое запрещает наилучшее найденное решение, а затем разрешить (ссылка). В данном случае мы использовали некоторую структуру. Общий разрез для переменных 0–1 выводится здесь. Это также можно сделать для общих целочисленных переменных, но тогда все становится немного запутанным.

person Erwin Kalvelagen    schedule 16.11.2020