- Машинное обучение для резки плоскостей в целочисленном программировании: обзор (arXiv)
Автор: Арно Деза, Элиас Б. Халил.
Аннотация: мы рассматриваем недавние работы по методам машинного обучения (ML) для выбора секущих плоскостей (или разрезов) в линейном программировании смешанных целых чисел (MILP). Несмотря на наличие различных классов разрезов, задача выбора набора разрезов для добавления к релаксации линейного программирования (ЛП) в заданном узле дерева ветвей и границ (B&B) не поддается как формальным, так и эвристическим решениям. дата. Машинное обучение предлагает многообещающий подход к улучшению процесса выбора разрезов за счет использования данных для определения многообещающих сокращений, которые ускоряют решение экземпляров MILP. В этом документе представлен обзор темы, в котором освещаются последние достижения в литературе, общие подходы к сбору данных, оценке и архитектуре моделей машинного обучения. Мы анализируем эмпирические результаты в литературе, пытаясь количественно оценить достигнутый прогресс, и в заключение предлагаем направления для будущих исследований.
2. Улучшение квантовых алгоритмов для максимального сокращения с помощью целочисленного программирования (arXiv)
Автор: Фридрих Вагнер, Йонас Нюссляйн, Фрауке Лиерс.
Аннотация: На сегодняшний день квантовые вычисления обещают потенциал для будущего ускорения комбинаторной оптимизации по сравнению с классическими алгоритмами целочисленного программирования, которые — наряду с определением релаксации — обычно также включают некоторую умную перечислительную часть. Методы целочисленного программирования могут эффективно вычислять сильные границы даже для больших экземпляров, однако, возможно, придется перечислить большое количество подзадач для определения оптимального решения. Если потенциал квантовых вычислений реализуется, можно ожидать, что, в частности, поиск больших пространств решений можно будет выполнять быстро. Однако квантовое оборудование ближайшего будущего значительно ограничивает размер решаемых задач, а также подвержено шуму. В этой работе мы делаем один шаг к интеграции возможностей квантовых и классических методов целочисленной оптимизации. Мы предлагаем квантово-классический гибридный алгоритм для задачи максимального разреза на взвешенных графах. Алгоритм основан на классической релаксации линейного программирования, основанной на неравенствах нечетного цикла. Для случаев, которые слишком велики для решения на доступных квантовых машинах, мы уменьшаем размер задачи в соответствии с решением релаксации линейного программирования. Редуцированную задачу можно решить с помощью квантовых компьютеров ограниченного размера. Возвращаемые решения расширяются до допустимых решений исходного экземпляра. Кроме того, мы улучшаем применимость QAOA, хорошо известного параметризованного квантового алгоритма, путем получения оптимальных параметров для особых случаев взвешенной задачи о максимальном разрезе, которая мотивирует оценку параметров для произвольных случаев. Мы представляем многочисленные результаты вычислений на реальном квантовом оборудовании для экземпляров, основанных на физике, с числом узлов до 100, что превышает доступные возможности квантового оборудования. Хотя все случаи могут быть легко решены с помощью классических компьютеров, они обеспечивают доказательство работоспособности предлагаемого метода.
