СТОЛП (Стандартные Технологии Организации Линейного Программирования) или
Быстрый поиск ошибки в задаче ЦЛП.
#алгоритмы #mip #opensource

При разработке ЦЛП есть такая проблема, что их очень неудобно отлаживать. Нельзя дебаггером пройтись и понять, в каком уравнении сделал ошибку.
При написании модели они часто оказываются несовместными (infeasible), и надо искать, где именно произошла ошибка. У коммерческих солверов для этого есть механизм поиска минимального набора несовместных ограничений. Но это очень неудобная штука. Они там просто в каждое ограничение добавляют слак переменную, и дальше минимизируют их набор. Задача оказывается почти всегда сильно более сложной, и я почти никогда не дожидался, когда она доработает.

А я придумал другой подход. Я просто беру lp файл и ищу какое-нибудь несовместное ограничение бинарным поиском. То есть удаляю половину ограничений и смотрю есть ли решение или нет. Если нет, удаляю половину оставшихся ограничений и т.д.

Этот метод оказывается на практике очень быстрым и полезным. Задачки обычно считаются моментально и можно быстро найти ограничение, на котором падает и это часто наводит на мысли.

Я пошел дальше и сделал функцию, которая это делает за меня автоматически. Увидеть как программа сама находит некорректное ограничение, это просто кайф❤️‍🔥.

А потом я пошел еще немного дальше и сделал свободную библиотеку СТОЛП, куда положил эту функцию.
https://gitlab.com/tarasov.alexey/stolp/

Если кто так же настрадался копаясь в инфизиблах, милости прошу использовать. Буду очень рад, если эта штука еще кому-то пригодится.

P.S. У меня есть еще разные ноухау, которыми я планирую делиться и выкладывать их в этот проект. По мере свободного времени буду это делать.

#текучка #opensource #сотрудники
О пользе опенсорса.

Я делал библиотеку Столп, чтобы повышать репутацию в сообществе и таким образом получать резюме и новых сотрудников.
Метод и правда работает, вчера новый человек вышел на работу!! 🍾
Нас уже 8 человек, правда не все фултайм. Задач перегруз, так что надо продолжать расти.