ИИ и сложнейшие проблемы мира · Теоретическая информатика · arXiv · 2026-10-22
Интерпретируемый выбор отсекающих плоскостей для смешанно-целочисленного линейного программирования с помощью генетического программирования
Оригинальное название: Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
Отсекающие плоскости — ключевой компонент решателей смешанного целочисленного линейного программирования (MILP), однако существующие стратегии отсечений, созданные вручную, статичны, а обучаемые стратегии на основе нейронных сетей обладают ограниченной интерпретируемостью и не дают гарантий сходимости. Авторы предлагают GPSCS — первый фреймворк на основе обучения, обобщающий эвристики ручной разработки в полностью интерпретируемую политику: генетическое программирование эволюционирует символьную функцию оценки, ранжирующую кандидатов в отсечения, а лёгкий механизм на основе статистики адаптивно определяет, сколько отсечений из числа наиболее высоко ранжированных добавлять в каждом раунде сепарации. Протестированный в SCIP на семи классах синтетических и реальных бенчмарков, оценочные экземпляры которых в среднем в 41 раз сложнее обучающих, GPSCS сокращает среднее время решения на 6% по сравнению с настройкой SCIP по умолчанию и обеспечивает двукратное ускорение как относительно недавнего нейросетевого подхода, так и относительно базового варианта без отсечений.