Расширенное решение LP

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

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

Концепции

В этом разделе представлены ключевые концепции расширенного использования решателей LP. Мы предполагаем, что читатели знакомы с понятием двойственности в ЛП .

Семейства алгоритмов LP

Следующие классы алгоритмов для LP доступны через OR-Tools.

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

    1. Первичный симплекс совершает шаги по вершинам первичной допустимой области. Этот вариант особенно эффективен при решении последовательности задач ЛП с различными целевыми функциями, то есть когда основная допустимая область фиксирована.
    2. Двойной симплекс совершает шаги по вершинам двойственной допустимой области. Этот вариант особенно эффективен при решении последовательности задач ЛП, где двойственная допустимая область фиксирована, например, когда меняются только границы переменных. По этой причине двойной симплекс широко используется в решателях MIP .

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

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

В таблице ниже перечислены решатели LP, доступные в OR-Tools, и указано, какое из трех семейств алгоритмов реализовано в каждом решателе.

Решатель Симплекс Барьер Первый заказ
Клп Икс Икс
КПЛЕКС Л Икс Икс
Глоп Джи Икс
ГЛПК Икс Икс
Гуроби Л Икс Икс
ПДЛП Г Икс
Экспресс Л Икс Икс

G означает, что решатель разработан Google. L указывает, что решателю требуется лицензия, выданная соответствующим сторонним разработчиком.

См. Рекомендации , чтобы узнать, какие решатели и алгоритмы использовать.

Что на самом деле означает решение?

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

Допуски

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

Рассмотрим задачу линейного программирования

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

и соответствующая двойственная задача

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Эта пара задач имеет единственное оптимальное простое решение $x_1=1, x_2=0$ и двойственное решение $y=-2$. Какие решения могут быть приняты решателем как оптимальные? Чтобы ответить на этот вопрос, определим следующие величины:

  • Разрыв двойственности — это разница между значением первичной цели и значением двойной цели, в данном случае $ |(-2x_1 - x_2) - y| $.
  • Первичные недопустимости — это нарушения первичных ограничений, в данном случае $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2 , 0\}) $.
  • Двойственные недопустимости — это нарушения двойственных ограничений, в данном случае $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \} ) $.

Решатель объявляет решение оптимальным, если разрыв двойственности, основные и двойственные невозможности меньше заданного допуска. 1

Примечательно, что применение допусков варьируется как по естественным, так и по особым причинам в зависимости от решателей и алгоритмов. Например, разрыв двойственности в симплексном алгоритме обусловлен только числовой неточностью, в то время как прямая и двойственная невозможности присутствуют даже в точной арифметике. Некоторые методы напрямую реализуют связанные ограничения $ x_1 \ge 0, x_2 \ge 0, $ и $ y \le 0 $, в то время как другие обрабатывают нарушения связанных ограничений иначе, чем нарушения линейных ограничений, таких как $x_1 + x_2 \le 1$. Для некоторых решателей допуски абсолютны ; то есть существует параметр $\epsilon$, и решения считаются оптимальными, если разрыв двойственности и все простые и двойственные невозможности меньше или равны $\epsilon$. Для других решателей допуски являются относительными , то есть они масштабируются в зависимости от размера коэффициентов задачи.

В качестве примера влияния допусков рассмотрим абсолютный допуск $ \epsilon = \frac{1}{2} $, примененный к вышеуказанной паре «простой-двойственный». Решение $ x_1 = 1,5, x_2 = 0, y = -3 $ имеет нулевой разрыв двойственности и все недопустимости, меньшие или равные $ \epsilon $, поэтому решатель может объявить это решение «оптимальным». Тем не менее, его целевое значение (-3) отличается на 1 от истинного оптимального целевого значения -2. Типичные значения по умолчанию $\epsilon$ находятся в диапазоне от $10^{-6}$ до $10^{-8}$, что делает такие крайние примеры редкими, но не невозможными.

Типы решений

Проблемы ЛП могут иметь более одного оптимального решения, особенно с учетом допусков. Мы кратко обсудим свойства решений, возвращаемых тремя различными семействами алгоритмов ЛП, представленными выше.

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

Барьерные методы и методы первого порядка обычно не возвращают вершины. (Теория предоставляет дополнительные характеристики, выходящие за рамки данного руководства.)

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

Рекомендации

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

Масштабирование проблемных данных

Решатели могут столкнуться с медленной сходимостью или сбоями в моделях из-за числовых проблем. Такие проблемы могут возникнуть по многим причинам; здесь мы приведем один пример.

В моделях ЛП часто встречаются очень маленькие или большие числовые константы. Расширяя приведенный выше пример, если \(x_1\) и \(x_2\) представляют долю клиентов, назначенных «поставщику 1» или «поставщику 2», и если мы хотим максимизировать выгоду от обслуживания этих клиентов, мы могли бы написать следующую целевую функцию ,

$$ \min -c_1x_1 - c_2x_2 $$

где:

  • $c_1$ — выгода от закрепления клиентов за поставщиком 1.
  • $c_2$ — выгода от закрепления клиентов за провайдером 2

Дуальные модели, удовлетворяющие следующим ограничениям, будут считаться возможными с абсолютным допуском $\epsilon$:

  • $y\le -c_1 +\epsilon$,
  • $y\le -c_2 +\epsilon$.

Если единицы выгоды $c_1$ и $c_2$ представляют собой небольшие дробные значения, находящиеся в том же масштабе, что и $\epsilon$, то двойственные условия осуществимости становятся довольно слабыми, следовательно, оптимальным может быть объявлен очень неоптимальный простой принцип.

Если, с другой стороны, единицами пособия являются «микродоллары» (1 000 000 микродолларов = 1 доллар), полученные в результате очень большие абсолютные значения требуют очень высокой точности решения, возможно, неоправданно высокой, учитывая пределы чисел с плавающей запятой. Решатели могут не сойтись, если задача сформулирована таким образом. При формулировании четко поставленной задачи опытным разработчикам моделей следует учитывать, масштабируются ли данные задачи таким образом, чтобы это соответствовало допускам их решателя.

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

О допусках Glop см. primal_feasibility_tolerance , dual_feasibility_tolerance и solution_feasibility_tolerance в GlopParameters . Обратите внимание, что primal_feasibility_tolerance и dual_feasibility_tolerance используются в алгоритме, а solution_feasibility_tolerance проверяется после решения, чтобы отметить числовые проблемы. Для PDLP см. eps_optimal_absolute и eps_optimal_relative .

Дополнительную информацию по этим типам проблем см. в Руководстве Гуроби по числовым проблемам . Хотя рекомендации написаны для пользователей Gurobi, многие принципы применимы в целом.

Выбор решателей и алгоритмов

Мы начнем с примера того, насколько большим может быть влияние выбора решателей и алгоритмов, а затем представим руководство по выбору решателей LP.

Вариативность на практике

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

Прямые и двойственные симплексные методы Glop сравниваются с барьерным методом Гуроби (с кроссовером и без него, который находит вершинное решение) и PDLP, методом первого порядка, с высокой и низкой точностью. В таблице ниже указано время решения в секундах с ограничением в 20 минут (1200 секунд).

Пример Глоп
Первичный симплекс		 Глоп
Двойной симплекс		 Барьер Гуроби
с кроссовером		 Барьер Гуроби
без кроссовера		 ПДЛП
Высокая точность		 ПДЛП
Низкая точность
ex10 >1200 >1200 79,7 63,5 8.2 2.7
nug08-3rd >1200 252,8 144,6 3.2 1.1 0,9
савшед1 >1200 >1200 156,0 22,6 46,4 32,4
широкий15 >1200 20,8 >1200 >1200 916,4 56,3
зданиеэнергия 178,4 267,5 12,8 12.3 >1200 157,2
с250р10 12.1 520,6 15.2 16,4 >1200 >1200
Версия решателя OR-Инструменты 9.3 OR-Инструменты 9.3 Гуроби 9.0 Гуроби 9.0 OR-Инструменты 9.3 OR-Инструменты 9.3
solver_specific_parameters (по умолчанию) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

Из этих результатов мы делаем следующий вывод.

  • Относительная производительность алгоритмов и решателей может варьироваться на порядки в одном экземпляре.
  • Ни один алгоритм и решатель не являются одинаково лучшими, чем другие.
  • Кроссовер (включен по умолчанию) увеличивает время решения, иногда существенно.
  • PDLP может решать задачи с низкой точностью иногда в 10 раз быстрее, чем с высокой точностью.

Краткое руководство по выбору решателей ЛП

Учитывая, что ни один алгоритм или решатель LP не является лучшим, мы рекомендуем следующие шаги, чтобы определить, что лучше всего подходит для вашего случая использования. Начните с первого шага и переходите к следующему, если производительности недостаточно.

  1. Попробуйте Глоп. Почему : Glop — это собственная реализация простых и двойных симплексных методов Google. Glop — это продукт с открытым исходным кодом, которому доверяют производственные рабочие нагрузки Google.
    • Если конфигурация по умолчанию (основной симплекс) не работает должным образом, попробуйте переключиться на двойной симплекс, используя use_dual_simplex: true .
  2. Если лицензия доступна, попробуйте коммерческий решатель (CPLEX, Gurobi или Xpress). Поэкспериментируйте с симплексным и барьерным методами. Почему: эти решатели являются отраслевыми стандартами и высоко оптимизированы. Также барьерные методы дополняют симплексные алгоритмы, предлагаемые Glop.
    • При использовании барьера отключите «пересечение», если вам не нужно решение вершин.
  3. Попробуйте ПДЛП. Настройте допуски сходимости в соответствии с вашим приложением. Почему: PDLP предназначен для решения самых серьезных задач, когда симплексные и барьерные методы достигают пределов памяти или работают слишком медленно. PDLP работает лучше всего, когда приблизительное, но быстрое решение предпочтительнее точного, но медленного решения.
  4. Если вы зашли так далеко, то теперь вы продвинутый пользователь LP! Для получения дополнительной помощи ознакомьтесь с вариантами поддержки OR-Tools.

  1. Зачастую это сложнее. Решатели обычно проверяют эти условия на преобразованной/упрощенной версии задачи, называемой предварительно решенной задачей. В некоторых случаях решение предварительно решенной проблемы может быть далеко от решения входной проблемы. Эта ситуация может привести к необычным статусам, таким как OptimalInfeas CPLEX или IMPRECISE Glop. ↩