Программный выход PuLP

Question

Я работаю с соавтором над определенным проектом по оптимизации, включающим линейное программирование. Мы оба используем Coin-OR для решения этой задачи. Я создаю файл .LP, используя пакет PuLP на основе Python. Я не совсем уверен, как соавтор создает свой файл .LP (определенно не использующий Python), но, по сути, у нас есть две разные системы, генерирующие файлы .LP для одной и той же задачи - т.е. целевая функция, переменные, ограничения абсолютно одинаковы .

Обычно я решаю свою проблему в Python (myProblm.solve()), но я также генерирую файл .LP и вызываю решатель CBC из командной строки, чтобы решить этот файл (проблема). Затем я сравниваю вывод, полученный от моей системы (Python или из командной строки), с тем, что получает мой соавтор. [Обратите внимание, что вывод проблемы на моей стороне равен точно одинаково, независимо от того, решен ли он в PuLP или в командной строке.]

Значения целевой функции хорошо совпадают между нами, но другие детали не совсем совпадают. Например, если бы мы решили эту проблему смешивания Whiskas , общая стоимость ингредиентов была бы точно такой же, но соотношение ингредиентов различалось. Любая идея, почему это будет?

Я вручную сравнил наши файлы .LP и заметил несколько отличий. Для начала, последовательность ограничений и переменных отличается. Другими словами, если есть 5 ограничений, мой файл перечисляет их как C1,C2,C5,C4,C3, тогда как те же ограничения будут перечислены как C1,C2,C3,C4,C5. Кроме того, мой код Python округляет все числа до 10, а его система округляет их до 1. Следовательно, коэффициенты некоторых переменных имеют немного разные значения.

Эти различия играют роль в точном выводе решателя?

Кроме того, следующий вопрос по расширению: что мы должны сделать, чтобы получить точно такой же результат при решении задачи оптимизации линейного программирования? Какие факторы влияют на решение проблем ЛП? Играют ли такие факторы, как структура файла .LP? Смогу ли я получить одинаковые выходные данные, если на разных компьютерах я буду запускать один и тот же файл LP с одинаковыми условиями?

Answer 1

Поскольку существует множество решений задачи ЛП с одной и той же оптимальной целевой функцией, разные решатели не могут гарантировать, что они вернут одно и то же решение. Эта проблема становится еще более сложной, когда проблемы MIP используют переходы и привязку. Использование многопоточности или многопроцессорности делает это практически невозможным.

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