Решение целочисленных программ на Python с PuLP

Question

Я работаю над пакетом Python для вычисления нескольких инвариантов графа NP-Hard. Текущая версия пакета использует грубую силу почти для всех алгоритмов, но я очень заинтересован в использовании целочисленного программирования, чтобы помочь ускорить вычисления для больших графов.

Например, простая целочисленная программа для решения числа независимости графа n-вершин должна максимизировать учитывая ограничения , где ,

Как мне решить эту проблему с помощью PuLP? Является ли PuLP моим лучшим вариантом, или было бы полезно использовать решатели на другом языке, например, Юлия, и интерфейс может дополнять их?

Answer 1

Я не предлагаю писать вашу полную реализацию для вас, но для решения последнего вопроса о PuLP по сравнению с другими языками.

PuLP предоставляет оболочку Python для целого ряда существующих LP Solvers.

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

Таким образом, нет необходимости изучать другой язык, чтобы получить лучший решатель.