Авторы Давид Шмойс и Шуцзин Ван

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

Распределение вознаграждений - обычная тема в Lyft. Например, мы рассылаем водителям рекламные купоны и бонусы водителям в надежде на оптимизацию целевых функций, таких как максимальное увеличение количества дополнительных поездок или часов вождения. В этом контексте основными ограничениями являются (1) общее бюджетное ограничение на то, сколько мы можем потратить на поощрения, а иногда (2) требование, чтобы каждому гонщику или водителю могло быть предоставлено не более одного стимула. Такие проблемы распределения могут быть легко сформулированы как задачи целочисленного программирования, которые можно дополнительно ослабить, чтобы они были линейными. Хотя такие проблемы имеют простую структуру, размер их проблемы может легко возрасти (например, может быть много стимулов или большое количество гонщиков). Поэтому мы задаемся вопросом: есть ли быстрый и эффективный способ решения этой проблемы, который может превзойти решатели с открытым исходным кодом? Ответ положительный. В этом конкретном случае использования мы разрабатываем алгоритмическую идею, основанную на двойственности.

Постановка проблемы

Для простоты рассмотрим сценарий раздачи купонов гонщикам. Мы определяем следующее:

Затем мы можем сформулировать задачу с релаксацией линейного программирования (P) следующим образом, где ограничение целочисленности переменных опущено. Мы знаем, что в этой релаксации мы получим не более одной переменной с дробным решением (хорошее свойство LP), что приемлемо в обмен на эффективность решения этой проблемы:

Здесь мы предварительно обработали данные, поэтому мы можем предположить, что

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

От первичного к двойственному

Чтобы решить релаксацию линейного программирования, мы сначала решим ее двойственное линейное программирование. Мы определяем следующие двойственные переменные:

Тогда двойственное (D) выглядит следующим образом:

Пусть D (λ) обозначает двойную линейную программу (D) для фиксированного значения λ ≥ 0. Рассматривая этот LP, обратите внимание, что задачи оптимизации для каждого райдера i = 1,. . . , m, - независимая (тривиальная) задача: мы просто устанавливаем

и, следовательно, оптимальное значение для D (λ) равно

чтобы решить (D), нам просто нужно найти λ, который минимизирует это выражение (E).

Решение двойного LP

Мы показываем, как компактная форма двойственного выражения, заданная как нахождение λ для минимизации (E), обеспечивает прямой способ решения этой LP. А пока сосредоточьтесь на одном всаднике i и соответствующем члене в (E). Мы наблюдаем следующее:

Поэтому мы хотим создать список точек останова для райдера i, проверяя каждое из пересечений линий k ᵢ, начиная с пересечения j = 1 и j = 2. Ключевым моментом здесь является то, что мы сохраняем только те точки останова, которые монотонно уменьшаются. После этого процесса мы можем предположить без ограничения общности, что каждый гонщик i, у которого теперь остается gᵢ (gᵢ ≤ k ᵢ) поощрения, содержит список допустимых купонов и точек останова, удовлетворяющих

На рисунке ниже представлено графическое объяснение, а математическое доказательство мы оставляем заинтересованным читателям.

Теперь рассмотрим, что мы узнали о целевой функции (E). Для фиксированного райдера i соответствующий член в суммировании дает кусочно-линейную функцию с точками останова gᵢ. Следовательно, при рассмотрении суммы в (E) мы снова получаем кусочно-линейную функцию с объединением этих значений точек останова (по всем вариантам i) в качестве результирующих точек останова. Пусть 0 = ρ₀ ‹ρ₁‹ ··· ‹ρn - объединение этих точек останова. Между любой парой точек останова функция D (λ) является аффинной функцией (т.е. имеет вид αλ + β); кроме того, D (λ) является выпуклым, а наклон этих частей является возрастающей функцией λ. Для достаточно большого λ (больше, чем ρn) наклон явно равен C; при λ = 0 наклон равен

что можно предположить отрицательным. В противном случае мы бы просто назначили каждому гонщику их купон на максимальную стоимость (который также является купоном на максимальную стоимость), поскольку это не исчерпывает бюджет и, следовательно, явно является оптимальным. Во всех остальных случаях существует точка останова ρ *, для которой наклон для λ ‹ρ * отрицательный, а для λ› ρ * положительный. В этом случае D (λ) минимизируется, когда λ = ρ *.

Алгоритм оптимизации Dual LP

На высоком уровне алгоритм вычисления оптимального двойного решения LP работает следующим образом: поддерживать точки останова в виде m отсортированных списков и перебирать весь набор точек останова в убывающем порядке, вычисляя текущую сумму. уклон, до первой точки, в которой склон переключает знак. Обратите внимание, что повторение точек останова в порядке убывания делает алгоритм (относительно простым) расширением случая, когда выбор наибольшего соотношения цены и качества для каждого гонщика исчерпывает бюджет (и, опять же, явно оптимален, когда каждый гонщик, кроме одного который использует последний бит бюджета, гарантировано интегральное назначение).

Для каждого гонщика мы сохраняем указатель на самый большой элемент в отсортированном списке точек останова, который еще предстоит обработать. Начнем с активного набора точек останова, по одной для каждого пассажира i = 1,. . . , m, изначально равняется vᵢ ₁ / cᵢ ₁ (что является наибольшим соотношением цены и качества для данного пассажира). Мы инициализируем текущий наклон, который на λ больше, чем все точки останова, равный C, и вводим обозначение, что cᵢ ₀ = 0, i = 1,. . . , m, для последнего использования (хотя это не соответствует ни одному варианту купона). Мы сохраняем активные в настоящее время точки останова в очереди приоритетов и на каждой итерации извлекаем максимальную оставшуюся точку. Предположим, что текущая извлеченная точка останова соответствует купону j * для райдера i *. Нам известен наклон двойной целевой функции, больший, чем эта точка останова, и мы хотим вычислить наклон чуть меньше этого значения. Для этого нам нужно отразить изменение от старого вклада в наклон для i * к его новому: новый - это вариант j *, а старый один из них - вариант j * - 1. Если мы позволим OLD обозначить стоимость купона j * - 1 для гонщика i *, а NEW обозначить стоимость купона j * для райдер i *, то изменение стоимости СТАРЫЙ-НОВЫЙ. Чтобы заменить точку останова, извлеченную для i *, мы вставляем следующую точку останова i * в очередь приоритетов (если она доступна), и алгоритм переходит к следующей итерация. Мы продолжаем итерацию, пока не уменьшим наклон с C до ниже нуля.

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

От оптимального двойного решения к оптимальному первичному LP

Мы получили оптимальное двойственное решение. Мы уже предполагали, что наклон D (λ) при λ = 0 отрицательный, и, следовательно, λ * ›0. Чтобы вычислить оптимальное прямое решение, мы воспользуемся условиями дополнительной нестационарности для основных и двойных оптимумов ЛП, что дает нам следующее:

Случай, когда каждая точка останова соответствует отдельному уникальному гонщику, легко понять. В этом случае оптимальное значение λ * для (D) - это точка останова, соответствующая ровно одному гонщику i *, и находится между точками останова для всех остальных гонщиков. Таким образом, для всех других гонщиков, кроме гонщика i *, существует уникальный максимум j (i), достигнутый в сроке, соответствующем i в сумма (E); следовательно, соответствующая опция должна быть установлена ​​равной 1 для этого гонщика. Этот аргумент можно распространить на случай, когда оптимальная точка останова соответствует нескольким гонщикам.

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

Краткое описание алгоритма

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

Заключение

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

Если вам понравился этот пост, подписывайтесь и рекомендуйте! Чтобы узнать больше, ознакомьтесь с другими нашими публикациями о науке.

Как всегда, Lyft нанимает! Если вы увлечены разработкой современных моделей машинного обучения / оптимизации или построением инфраструктуры, которая их поддерживает, прочтите наши Роли в науке и технике и свяжитесь с нами.

Мы хотели бы поблагодарить Кедара Таккара, Лей Динга, Алекса Вуд-Даути и Хосе Абеленду за их вклад / поддержку в этой работе. Кроме того, этот пост был бы невозможен без помощи Мэтта Изанта, Хао И Онга, Марка Гровера, Райана Лейна и Алекса Рафтера. Большое спасибо!