Мне нужно минимизировать субмодулярную функцию в семействе множеств, удовлетворяющих определенным ограничениям.Я знаю, что один из способов сделать это - написать формулировку целочисленного программирования (IP), в которой каждая переменная является индикатором набора и вести вектор затрат с таким количеством записей, как наборы.Однако, учитывая масштаб проблемы, над которой я работаю, мне было интересно, есть ли более эффективные решения.
Чтобы быть более конкретным, мне нужно решить задачу минимального покрытия обложек, где число наборов сопоставимок размеру вселенной элементов, которые я хочу охватить.Это делает число множеств порядка от $ 10 ^ 6 $ до $ 10 ^ 9 $.Это делает IP очень тяжелым (и поскольку решение может состоять из более чем одного набора, перечисление определенно не может быть и речи).
Мой вопрос заключается в том, существуют ли известные методы для этого.Теоретически вы можете минимизировать субмодулярные функции за время полиномии (для хороших семейств множеств), но я хотел бы знать практический алгоритм для этого;как люди решают субмодульную минимизацию в реальной жизни ?или на самом деле IP - лучший путь?Кстати, мне нужно точное решение, а не приближение.
Я работаю в Julia и Python, поэтому, если вы знаете пакет или реализацию на любом из этих языков, это было бы здорово.
Спасибо!