Вывод программирования PuLP

Я работаю с соавтором над определенным проектом оптимизации, связанным с линейным программированием. Мы оба используем решатель 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? Получу ли я точно такой же результат, если запустить один и тот же LP-файл с одинаковыми условиями на разных компьютерах?


python coin-or-cbc pulp
person bluetooth    schedule 24.04.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

person Stuart Mitchell    schedule 25.04.2018