Непредсказуемая сложность MIP

💡 Есть такая особенность в задачах целочисленного линейного программирования (Mixed Integer Programming - MIP), что по её виду не совсем понятно насколько сложной она будет.

🤔 Бывает так, что задача с миллионами переменных и ограничений решается на десктопе быстрее, чем за час, а бывают задачи с тысячами переменных/ограничений, которые до сих пор вообще никак не решены любыми средствами и солверами (в т.ч. коммерческим Gurobi).

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

📦 Датасет.
💻 Код для построения картинки.
@fminxyz