Наведите мост между исследованием операций и машинным обучением

На протяжении десятилетий исследование операций (ОИ) и машинное обучение (МО) развивались как две относительно независимые области исследований. Люди в области науки о данных и искусственного интеллекта, вероятно, больше знакомы с ML, чем с OR, хотя каждый практикующий ML должен знать по крайней мере несколько методов оптимизации, поскольку каждая проблема машинного обучения по сути является проблемой оптимизации. В этой статье я рассмотрю OR и ML как целостную тему, рассмотрю связи между ними и поделюсь некоторыми недавними достижениями в синергии между этими двумя областями, чтобы использовать лучшее из обоих миров.

В качестве предварительного просмотра на диаграмме ниже показаны связи между OR и ML с трех точек зрения: OR помогает обучать модели ML, ML предоставляет входные данные для OR, а ML улучшает подходы к решению OR. В следующем параграфе будет подробно рассмотрена каждая из этих трех точек зрения.

ИЛИ помогает обучать модели машинного обучения

В основе OR лежит оптимизация. Исследователи OR разработали множество методов для нахождения оптимального значения переменных решения, чтобы минимизировать или максимизировать имеющуюся целевую функцию. В зависимости от того, имеет ли задача оптимизации ограничения или нет, задачи оптимизации можно разделить на оптимизацию с ограничениями и оптимизацию без ограничений. Основываясь на формулировке целевой функции и ограничений, задачи оптимизации можно грубо разделить на линейную оптимизацию и нелинейную оптимизацию.

Возможно, проблема оптимизации, с которой чаще всего сталкиваются в ML, — это нелинейная оптимизация, поскольку функция потерь обычно находится в нелинейной форме по отношению к параметрам модели ML как для классификации (например, перекрестная энтропия), так и для регрессии (например, среднеквадратическая ошибка) в обучении с учителем. Алгоритмы на основе градиентного спуска обычно эффективны при решении этих проблем. Если существуют условия регуляризации, мы приходим к проблеме нелинейной оптимизации с ограничениями (например, гребневая регрессия, LASSO, машина опорных векторов). В таких случаях мы применяем множитель Лагранжа и работаем над лагранжевой релаксацией исходной задачи оптимизации с ограничениями, что является типичным методом ИЛИ для решения усложняющих ограничений. Например, в гребневой регрессии мы пытаемся решить следующую задачу:

где y—вектор наблюдений выходной переменной, X — матрица наблюдений входных переменных, b — вектор подбираемых коэффициентов, а t — параметр, используемый для управления уровнем регуляризации. Непосредственно решить эту формулировку непросто, поэтому мы применяем множитель Лагранжа λ и преобразуем исходную формулировку в ее лагранжеву релаксацию:

что далее сводится к:

Теперь можно применять методы неограниченной оптимизации для получения оптимального значения b.

Каждая проблема ML — это, по сути, проблема оптимизации, в которой функция потерь является целевой функцией, а параметры модели — переменными решения. В этом смысле OR усиливает ML, поскольку лучшие подходы к решению задач нелинейной оптимизации определенно повышают точность и эффективность процесса обучения моделей машинного обучения. Это взаимодействие между OR и ML показано синей стрелкой на диаграмме, приведенной в начале этой статьи.

ML предоставляет входные данные для OR

В отличие от применения методов ИЛИ в ML, доминирующими моделями OR в реальных приложениях являются модели линейного программирования (LP) и смешанного целочисленного линейного программирования (MILP). Задача LP — это задача оптимизации с линейной целевой функцией и линейными ограничениями, где переменные решения могут принимать непрерывные значения. Хотя задача MILP также имеет линейную целевую функцию и линейные ограничения, некоторые из ее переменных решения должны принимать целые значения. LP и MILP имеют широкий спектр применения в различных отраслях. Например, в управлении цепочками поставок MIP обычно используются для выбора местоположения объекта, планирования производства, маршрутизации транспортных средств и т. д. Такие задачи обычно имеют линейную функцию затрат в качестве целевой функции с большим количеством ограничений, удовлетворяющих спрос клиентов, обеспечивая минимальное использование ресурсов и т. д. На самом деле, специалисты по ОР склонны не формулировать реальные проблемы как задачи нелинейной оптимизации, поскольку их значительно сложнее решить, особенно с множеством ограничений.

В таких приложениях OR модели ML, в первую очередь модели контролируемого обучения, обычно служат для оценки известных параметров в моделях LP и MILP. Например, в области управления цепочками поставок мы можем построить контролируемую модель обучения для прогнозирования потребительского спроса, который затем становится известным параметром либо в ограничениях, либо в целевой функции моделей LP и MILP. Прогноз потребительского спроса может быть как точечной, так и вероятностной оценкой, связанной либо с детерминированной, либо со стохастической задачей оптимизации. Поскольку модели ML будут влиять на точность входных параметров приложений OR, качество моделей ML также влияет на успешность приложений OR. Это взаимодействие между OR и ML показано зелеными стрелками на схеме, приведенной в начале статьи.

Ниже я покажу вам простой пример задачи выбора местоположения объекта, чтобы проиллюстрировать, как выходные данные модели машинного обучения служат входными данными для MILP. Предположим, что компания хочет рассмотреть вопрос о строительстве распределительных центров среди Iкандидатов на отправку готовой продукции J клиентам. С каждым сайтом i связана емкость для хранения готовой продукции с максимальным количеством m_i единиц продукции. Строительствокаждого участкаi требует фиксированной платы за строительство в размере f_i. Доставка каждой единицы продукта с сайта i клиенту j воблагается стоимостью доставки c_ij. У каждого клиентаj есть спрос d_j, и спрос всех клиентов должен быть удовлетворен. Пусть двоичная переменная y_i обозначает, строим ли мы предприятие на участке i, а x_ijобозначает объем продукции, которая будет отгружена с участкаi покупателюj. Задачу оптимизации с целью минимизировать общие затраты можно сформулировать следующим образом:

Здесь y_i и x_ij — это переменные решения, представляющие решения, которые нам нужно принять, которые неизвестны до того, как мы попытаемся решить проблему. Остальные переменные являются известными параметрами, которые необходимо знать, прежде чем мы попытаемся решить задачу. Роль машинного обучения в этой проблеме заключается в том, что оно может предоставлять прогнозы спроса, оценку d_j. Прогнозирование спроса относится к области прогнозирования временных рядов, поскольку данные о спросе обычно поступают в виде временных рядов. Здесь можно применить различные алгоритмы, начиная от традиционных моделей временных рядов (например, ARIMA, экспоненциального сглаживания и т. д.) и заканчивая моделями машинного обучения (например, LightGBM, нейронные сети), чтобы получить достоверную оценку d_j. Модели машинного обучения также можно использовать для оценки других параметров, таких какc_ij, f_i и т. д., но я лично видел больше применений для прогнозирования спроса, чем для других параметров. Вышеупомянутая задача оптимизации может быть решена с помощью любого коммерческого решателя, такого как CPLEX, Gurobi и Xpress, и некоммерческого решателя, такого как SCIP.

ML улучшает подходы к решению OR

Точно так же, как OR влияет на процесс обучения ML, ML также может играть роль в процессе решения моделей OR. В последние годы наблюдается растущий интерес исследователей к использованию машинного обучения для повышения эффективности алгоритма ветвей и границ для решения смешанных целочисленных программ (MIP). Ветвь и граница — это алгоритм, широко используемый для решения MIP и работающий как алгоритм поиска по дереву. Предположим, мы решаем задачу минимизации. В корневом узле алгоритм решает LP-релаксацию исходной задачи (отбрасывание ограничений целостности в MIP преобразует исходную проблему в ее LP-релаксацию). Затем из корневого узла развиваются две ветви, в результате чего получаются две новые вершины, и к каждой ветви добавляется дополнительное ограничение с использованием ближайших целых чисел. Рисунок ниже дает краткую иллюстрацию процедуры разработки ветвей в алгоритме ветвей и границ.

Возьмите рисунок выше, например, если x_1 = 2,5 в оптимальном решении релаксации LP исходной задачи в корневом узле (т. Е. LP0) и мы выбираем разветвление на нем, мы добавим x_1 ≤ 2 к первой ветви и x_1 ≥ 3 на вторую ветвь. Затем в каждом новом узле мы решаем полученную задачу релаксации ЛП с добавленным ограничением. Вышеупомянутая процедура называется ветвлением, и мы повторяем эту процедуру по мере разработки дерева. Мы достигаем листового узла, если все переменные решения с ограничениями целочисленности являются целыми числами.

Обратите внимание, что при поиске по дереву мы обновляем текущее лучшее решение каждый раз, когда встречаем целочисленное решение в узле. Текущее лучшее решение обеспечивает верхнюю границу оптимального целевого значения MIP. Если в конкретном узле релаксация LP имеет оптимальное целевое значение больше, чем текущее лучшее решение, то нет необходимости в дальнейшем исследовании этого узла, и этот узел будет отсечен. Такая процедура обрезки значительно помогает сократить усилия по поиску дерева, устраняя необходимость достижения каждого конечного узла дерева.

Однако даже с отсечением практические проблемы обычно настолько велики, что выполнение простой версии алгоритма ветвей и границ по-прежнему занимает довольно много времени. Исследователи предложили несколько идей по улучшению алгоритма брендинга и связывания. Одна из идей состоит в том, чтобы добавить разрезы к релаксации LP в некоторых узлах. Разрезы — это ограничения, которые могут исключать нецелочисленные решения, но не целочисленные решения. Добавляя разрезы в некоторых узлах, мы можем уменьшить допустимую область релаксации ЛП и упростить поиск целочисленного решения путем решения релаксации ЛП. Алгоритм, который следует этой идее, называется алгоритмом ветвления и разрезания.

Добавление нарезок — хорошая идея, но иногда поиск хороших нарезок сам по себе — нетривиальная задача. В таких случаях применение эвристики к некоторым узлам весьма полезно для поиска целочисленных решений. Одной из широко используемых эвристик является поиск окрестностей, индуцированный релаксацией (RINS). Эта эвристика рассматривает текущее наилучшее целочисленное решение и дробное решение релаксации LP в текущем узле, фиксирует значение переменных решения, с которыми согласуются два решения, и решает остальные переменные решения как subMIP.

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

Возвращаясь к взаимодействию между OR и ML, основная идея использования ML для улучшения алгоритма ветвей и границ заключается в применении ML к:

  1. Научитесь переходить — на какую переменную решения следует переходить в узлах
  2. научитесь сокращать — как найти эффективные сокращения, чтобы добавить релаксации LP
  3. научитесь находить хорошие эвристики — помогите найти лучшие целочисленные решения
  4. научиться настраивать параметризацию оптимизационного решателя — как настроить решатель (например, критерии завершения, частоту применения эвристики), чтобы проблему можно было решить быстрее

Обычно для обучения модели ML требуется большой набор MIP, а затем модель ML применяет полученные знания к конкретному интересующему экземпляру MIP.

Использование ML для облегчения решения MIP является новой темой исследований, и большая часть работы была сосредоточена на теоретических исследованиях, а не на практических реализациях в коммерческих или некоммерческих решателях MIP. Ниже приведен список полезных ресурсов, чтобы узнать больше об этой точке зрения.

  1. ML4CO — это соревнование, связанное с этой темой, которое посвящено поощрению использования ML для решения задач комбинаторной оптимизации (концепция примерно такая же, как целочисленное программирование). В этом соревновании участникам было предложено три задачи: основная задача, двойная задача и задача конфигурации, каждая из которых была сосредоточена на разных аспектах алгоритма ветвей и границ. Предполагая решение MIP минимизации, основная задача требовала от участников использовать ML для поиска лучших целочисленных решений в корневом узле, чтобы снизить верхнюю границу оптимального решения. В двойной задаче участников просили сосредоточиться на том, как принимать решения о ветвлении с помощью ML, чтобы увеличить нижнюю границу оптимального решения. Наконец, в задаче настройки участники пытались использовать ML, чтобы найти лучшие параметры для некоммерческого решателя SCIP для решения MIP.
  2. В статье «Машинное обучение для комбинаторной оптимизации: методологический тур по горизонту» представлен обзор попыток использовать методы машинного обучения для решения задач комбинаторной оптимизации. Авторы резюмировали два мотива использования ML для решения задач комбинаторной оптимизации: учиться на демонстрациях, предоставленных экспертами, для принятия решений (например, решения о ветвлении в алгоритме ветвей и границ) при поиске оптимального решения и учиться из опыта, что может привести к изучению новых политик принятия решений (например, решений о ветвлении) для продвижения современного уровня техники. Первое понятие совпадает с имитационным обучением, а второе — с обучением с подкреплением. Красные стрелки на диаграмме, приведенной в начале этой статьи, иллюстрируют взаимодействие между OR и ML с этой точки зрения.
  3. Другой примечательной статьей является Решение смешанных целочисленных программ с помощью нейронных сетей», написанная командой Google DeepMind, в которой создается графовое представление MIP, а нейронные сети используются для генерации частичных назначений для целочисленных переменных. (нейронное погружение) и научиться принимать ветвящиеся решения (нейронное ветвление). Были получены многообещающие результаты в отношении повышения эффективности алгоритма ветвей и границ.

Заключение

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