2025-11-13T22:16:11.184529

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

Li, Chen, Li et al.
By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
academic

Быстрое и интерпретируемое решение смешанных целочисленных линейных программ посредством обучения сокращению модели

Основная информация

  • ID статьи: 2501.00307
  • Название: Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
  • Авторы: Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang
  • Классификация: cs.LG cs.AI
  • Дата публикации: 31 декабря 2024 г. (препринт arXiv)
  • Учреждения: Школа компьютерных наук и инженерии Юго-восточного университета, лаборатория Noah's Ark компании Huawei
  • Ссылка на статью: https://arxiv.org/abs/2501.00307

Аннотация

В данной работе предлагается метод решения крупномасштабных задач смешанного целочисленного линейного программирования (MILP) на основе машинного обучения, использующий корреляцию между структурой MILP и её решением. В отличие от существующих методов обучения решению "конец в конец", данная работа изучает упрощённую эквивалентную модель исходной MILP в качестве промежуточного этапа. Предложен метод обучения сокращению модели на основе предпочтений, учитывающий относительную производительность всех сокращённых моделей для каждого экземпляра MILP в качестве информации о предпочтениях и использующий механизм внимания для захвата этой информации. Экспериментальные результаты показывают повышение точности решения на ~20% по сравнению с передовыми методами сокращения модели на основе ML и ускорение в 2-4 порядка величины по сравнению с коммерческим решателем Gurobi.

Исследовательский контекст и мотивация

Определение проблемы

Смешанное целочисленное линейное программирование (MILP) широко применяется в критических областях, таких как логистика цепи поставок, планирование услуг, управление энергией и транспортное планирование. В практических промышленных приложениях экземпляры MILP обычно включают сотни тысяч переменных решения и ограничений. Существующие коммерческие решатели, основанные на точных методах решения, требуют высоких вычислительных затрат и не могут удовлетворить требования реального времени.

Исследовательская мотивация

  1. Проблемы масштабируемости: Существующие методы ML непосредственно изучают отображение в высокомерное пространство решений, что создаёт проблемы масштабируемости
  2. Отсутствие интерпретируемости: Методы "конец в конец" не могут обеспечить интерпретируемые решения или интуитивное понимание
  3. Недостаточное использование информации о предпочтениях: Существующие методы сокращения модели сосредоточены только на оптимальной сокращённой модели, игнорируя важную информацию о предпочтениях всех сокращённых моделей

Ограничения существующих методов

  • Прямое предсказание решения: Низкая точность предсказания из-за высокой размерности пространства решений
  • Обучение оптимизации: Ограниченная эффективность из-за ограничений горизонта принятия решений
  • Существующие методы сокращения модели: Рассматривают все допустимые сокращённые модели как эквивалентные идеальные метки, не полностью используя информацию о сравнении

Основные вклады

  1. Предложен метод обучения сокращению модели на основе предпочтений: Преобразует производительность сокращённых моделей в информацию о предпочтениях, полностью используя информацию о сравнении в пространстве экземпляр-стратегия
  2. Разработана архитектура механизма внимания: Захватывает корреляцию между экземпляром и предпочтительными сокращёнными моделями, повышая точность обучения
  3. Введена техника обрезки SETCOVER: Контролирует количество сокращённых моделей (меток), генерируя минимальный набор меток, допустимый для всех экземпляров
  4. Достигнуто значительное повышение производительности: Проверено на реальных задачах MILP, повышение точности на 20% по сравнению с существующими методами и ускорение в 2-4 порядка величины по сравнению с Gurobi

Подробное описание метода

Определение задачи

Дана параметризованная задача MILP:

min f(c, x)
s.t. g(A, x) ≤ b
     xI ∈ Z^d, x_{-I} ∈ R^{n-d}

где θ = ⟨A, c, b⟩ обозначает параметры MILP.

Определение оптимальной стратегии: s*(θ) = (T(θ), x*_I(θ)), включающей набор активных ограничений T(θ) и значения целочисленных переменных при оптимальном решении.

Цель: Изучить отображение из параметров θ в оптимальную стратегию s*(θ).

Архитектура модели

1. Этап генерации и обрезки стратегий

  • Генерация стратегий: Использует оценку Good-Turing для определения количества экземпляров до тех пор, пока N₁/N не упадёт ниже порога
  • Обрезка стратегий: Строит двудольный граф экземпляр-стратегия G(V_θ, V_s, E), преобразуя задачу обрезки в задачу SETCOVER
  • Жадный алгоритм: Итеративно выбирает узлы стратегий, покрывающие наибольшее количество непокрытых узлов экземпляров

2. Обучение стратегиям на основе предпочтений

Расчёт предпочтений:

r(θᵢ, sⱼ) = -log(p(θᵢ, sⱼ) + d(θᵢ, sⱼ))

где p(θᵢ, sⱼ) — недопустимость, d(θᵢ, sⱼ) — субоптимальность.

Определение предпочтений:

(θᵢ, sⱼ) ≻ (θᵢ, sₖ) ⇔ r(θᵢ, sⱼ) > r(θᵢ, sₖ)

Кодирование механизма внимания:

A([θᵢ, S^P]) = softmax(QK^T/√d)V

Каждую пару экземпляр-стратегия ⟨θᵢ, sⱼ⟩ рассматривает как токен, извлекая признаки посредством многоуровневого механизма внимания.

Технические инновации

1. Оптимизация выборки предпочтений

Использует транзитивность предпочтений, упорядочивая стратегии по предпочтениям, требуя только M_P упорядоченных образцов предпочтений вместо (M_P choose 2) попарных сравнений, снижая сложность выборки с квадратичной до линейной.

2. Двойная функция потерь

  • Потери предпочтений:
L_p(φ) = -1/N ∑∑[μᵢ,ⱼ log(pᵢ,ⱼ) + (1-μᵢ,ⱼ) log(1-pᵢ,ⱼ)]
  • Потери разности вознаграждений:
L_d(φ) = 1/N ∑∑(r̂ᵢ,σ(j) - r̂ᵢ,σ(j+1) - δᵢ,ⱼ)²
  • Общие потери: L_total(φ) = λ₁L_p(φ) + λ₂L_d(φ)

3. Вывод Top-k стратегий

На этапе онлайн-вывода выбирает Top-k выходных стратегий в качестве кандидатов, оценивая сокращённые модели и выбирая стратегию с наименьшей недопустимостью.

Экспериментальная установка

Наборы данных

  1. MIPLIB: Реальные задачи MILP из 6 сценариев с различной масштабностью и сложностью решения
  2. Задача управления энергией топливных элементов: Регулирование сложности задачи путём увеличения временных шагов T
  3. Задача управления запасами: 5 крупномасштабных реальных промышленных задач со средним числом ~100 тыс. ограничений

Метрики оценки

Метрики точности:

accuracy = 1/N |{θᵢ | p(θᵢ, ŝⱼ) ≤ ε₁ ∧ d(θᵢ, ŝⱼ) ≤ ε₂}|

где допуски недопустимости и субоптимальности установлены на уровне 1×10⁻⁴.

Методы сравнения

  1. Gurobi: Передовой коммерческий решатель (с включённым горячим стартом)
  2. Gurobi Heuristic: Эвристический режим Gurobi (ограничение по времени 1 сек)
  3. MLOPT: Наиболее применимый метод обучения на основе сокращения модели
  4. Predict and Search: Метод на основе предсказания решения

Детали реализации

  • Оптимизатор: AdamW, скорость обучения 0.0001-0.001
  • Затухание скорости обучения: линейное затухание на 0.9 каждые 10 эпох, всего 100 эпох
  • Размер пакета: 128
  • Координирующий параметр λ₁: 0.8-0.9

Экспериментальные результаты

Основные результаты

Набор данных MIPLIB

  • В большинстве сценариев метод показывает производительность, близкую к Gurobi по субоптимальности и допустимости
  • Показывает небольшое преимущество перед MLOPT в допустимости и значительное улучшение в субоптимальности
  • Эвристический метод показывает худшие результаты по нескольким метрикам из-за ограничения по времени

Управление энергией топливных элементов

  • Повышение точности на ~39% на наиболее сложных задачах
  • Значительный эффект обрезки стратегий, особенно с увеличением масштаба задачи
  • Производительность Top-k: улучшение с увеличением k, превосходство над MLOPT при одинаковых значениях k

Задачи управления запасами

  • Сохранение допустимости на всех экземплярах с стабильной точностью ~90%
  • На максимальной масштабной задаче P5 (более 270 тыс. ограничений) улучшение на ~30% по сравнению с MLOPT

Анализ времени вычисления

  • Улучшение времени на 3 порядка величины по сравнению с Gurobi
  • Относительно стабильное время с увеличением масштаба задачи
  • Минимальные различия с MLOPT (при одинаковых значениях k)
  • Вычисление Top-k может быть распараллелено для дальнейшего ускорения

Абляционные исследования

Обучение предпочтениям vs подгонка вознаграждений

На наборе данных топливных элементов метод предпочтений показывает повышение средней точности на ~9% по сравнению с прямой подгонкой вознаграждений, с лучшей производительностью по метрикам недопустимости и субоптимальности.

Упорядоченная выборка vs традиционная выборка

Упорядоченный метод показывает повышение средней точности на ~8% по сравнению с традиционной выборкой парных предпочтений при различных масштабах задач, одновременно значительно снижая затраты на обучение.

Связанные работы

Классификация методов решения MILP на основе ML

  1. Прямое предсказание решения: Непосредственное изучение отображения из экземпляра MILP в решение
  2. Обучение оптимизации: Изучение ускорения традиционных точных/эвристических методов
  3. Обучение упрощению MILP: Изучение предварительной обработки или сокращения масштаба MILP

Связь данной работы с существующими исследованиями

  • По сравнению с методами "конец в конец": Избегает проблемы изучения высокомерного пространства решений
  • По сравнению с обучением оптимизации: Не ограничено горизонтом принятия решений
  • По сравнению с существующим сокращением модели: Полностью использует информацию о предпочтениях, а не только оптимальную стратегию

Заключение и обсуждение

Основные выводы

  1. Обучение сокращению модели на основе предпочтений значительно повышает производительность решения MILP
  2. Техника обрезки SETCOVER эффективно контролирует количество стратегий
  3. Механизм внимания успешно захватывает корреляцию экземпляр-стратегия
  4. На реальных промышленных задачах достигнуто значительное ускорение и повышение точности

Ограничения

  1. Метод применим к однородным задачам MILP с повторяющейся структурой
  2. Требует достаточного объёма обучающих данных для изучения эффективной модели предпочтений
  3. Этап генерации стратегий всё ещё требует коммерческого решателя для получения оптимальных решений
  4. В крупномасштабных задачах пространство стратегий может оставаться очень большим

Направления будущих исследований

  1. Расширение на более широкие типы задач оптимизации
  2. Снижение зависимости от объёма обучающих данных
  3. Дальнейшее повышение эффективности генерации стратегий
  4. Исследование методов без учителя или с частичным учителем

Глубокая оценка

Преимущества

  1. Высокая инновационность: Первая систематическая интеграция обучения предпочтениям в сокращение модели MILP
  2. Прочная теоретическая база: Основана на концепции сокращения модели из теории операционных исследований
  3. Полные эксперименты: Проверка на нескольких реальных наборах данных, включая промышленные задачи
  4. Значительная производительность: Существенные улучшения по сравнению с существующими методами
  5. Хорошая интерпретируемость: Сокращённые модели соответствуют интерпретируемым режимам операции

Недостатки

  1. Ограниченная область применения: Главным образом применима к параметризованным задачам MILP
  2. Затраты на обучение: Всё ещё требует большого объёма помеченных данных (оптимальные решения)
  3. Недостаточный теоретический анализ: Отсутствуют теоретические гарантии сходимости и способности обобщения
  4. Ограниченные базовые методы сравнения: Главным образом сравнивается с одним методом обучения (MLOPT)

Влияние

  1. Академический вклад: Предоставляет новое направление исследований для области ML4CO
  2. Практическая ценность: Имеет потенциал прямого применения в решении промышленных задач MILP
  3. Воспроизводимость: Подробное описание метода и ясная постановка экспериментов
  4. Вдохновляющее значение: Идея обучения предпочтениям может быть расширена на другие задачи оптимизации

Применимые сценарии

  1. Онлайн стохастическое планирование: Требуется быстрое решение похожих экземпляров MILP
  2. Оптимизация цепи поставок: Задачи с изменяющимися параметрами, но фиксированной структурой
  3. Планирование в реальном времени: Приложения со строгими требованиями к времени решения
  4. Крупномасштабная промышленная оптимизация: Задачи, которые коммерческие решатели не могут обработать

Библиография

Статья ссылается на важные работы в данной области, включая:

  • Bengio, Lodi, and Prouvost (2021): Обзор машинного обучения для комбинаторной оптимизации
  • Bertsimas and Stellato (2022): Онлайн смешанное целочисленное программирование
  • Misra, Roald, and Ng (2022): Обучение для оптимизации с ограничениями
  • И большое количество связанных работ по обучению "конец в конец" и обучению оптимизации

Общая оценка: Это высококачественная исследовательская работа, предлагающая инновационный метод обучения предпочтениям в области ML4CO. Несмотря на некоторые ограничения, её теоретический вклад и практическая ценность весьма значительны, предоставляя новый эффективный путь для решения крупномасштабных задач MILP.