Краткое содержание

arXiv:2511.12986v1 Тип: новая работа Аннотация: Метод ветвей и границ (B&B) является основным точным методом решения задач смешанного целочисленного линейного программирования (MILP), однако его экспоненциальная временная сложность создает значительные трудности для задач крупного масштаба. Растущие возможности машинного обучения стимулируют попытки улучшить B&B за счет обучения стратегий ветвления на основе данных. Однако большинство существующих подходов основаны на обучении с подкреплением путем имитации (Imitation Learning, IL), которое часто переобучается на демонстрациях эксперта и плохо обобщается на структурно разнородные или ранее не встречавшиеся экземпляры задач. В данной работе мы предлагаем Tree-Gate Proximal Policy Optimization (TGPPO), новую структуру, которая использует Proximal Policy Optimization (PPO), алгоритм обучения с подкреплением (Reinforcement Learning, RL), для обучения стратегии ветвления, направленной на улучшение обобщения для разнородных экземпляров MILP. Наш подход основан на параметризованном представлении пространства состояний, которое динамически отражает изменяющийся контекст дерева поиска. Эмпирические оценки показывают, ч