За любой математической моделью стоит субъект-создатель, который имеет свое видение моделируемых процессов, свою креативность и виртуозность владения мат. аппаратом. Эти и другие источники субьективности формируют определенный почерк автора-разработчика. Но все ли модели хороши?

Выпущено множество книг-рекомендаций про то, как писать "хороший" программный код: "Чистый код", "Совершенный код", "Программист-прагматик", "Чистая архитектура" и др. Такого рода литература задает некоторый стандарт качества и очертания "идеала".

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

Слаковые переменные

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

Одним из направлений борьбы с этой проблемой можно рассмотреть "смягчение" ограничений - допустить возможность нарушения правил. Для оценки объема нарушений использовать слаковые переменные. В зависимости от критичности нарушения возможно сформировать приоритеты и с соответствующим весом штрафовать их в целевой функции задачи. По этому принципу работает метод релаксации Лагранжа.

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

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

Готовые решатели производят инициализацию таких переменных самостоятельно без вмешательства пользователя.

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

Пользовательские переменные

Читабельность и легкая интерпретируемость модели - это то, к чему стоит стремиться, но не во вред производительности.

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

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

Пусть на входе имеем набор заявок к перевозке с указанием даты, локации отправки/прибытия и кол-ва заявок, известно начальное распределение транспортных средств (ТС) по сети с указанием даты и места освобождения. Транспорт можно перемещать между узлами в холостую. Цель: максимизировать покрытие заявок. Воспользуемся моделью потоков в сети для формализации задачи. Узлом сети будем называть пару (локация, дата), ребро - груженый (по заявке) или холостой (ХП) переход из одного узла в другой.

Математическая модель задачи.

Индексы

- множество узлов типа отправитель (кодируется парой дата-локация);

- множество узлов типа получатель (кодируется парой дата-локация);

Постоянные

- изначальное кол-во транспортных средств (ТС) в узле ;

- объем заказов на ребре ;

Переменные

- целочисленная переменная, поток холостого перегона ТС из узла в узел ;

- целочисленная переменная, поток груженных переходов ТС из узла в узел ;

- целочисленная переменная, переменная замыкания потоков (кол-во ТС, которые завершают свою работу в узле );

- целочисленная переменная, кол-во невыполненных заказов (та самая пользовательская переменная).

Ограничения

1. Уравнение баланса ТС в узлах:

2. Кол-во запланированных заказов к выполнению не превышает кол-во заказов:

3. Кол-во ТС на истоке равно кол-ву ТС на стоке (замыкание потоков):

4. Агрегирующее ограничение: кол-во невыполненных заказов:

Вспомогательной переменной в поставленной задаче является переменная , которая соответствует объему невыполненных заявок. Целевая функция с такой переменной может принять вид: - минимизация кол-ва невыполненных заявок.

Эту же целевую функцию можем записать в явном виде, без вовлечения переменной-посредника: - максимизация кол-ва выполненных заказов.

Время нахождения оптимального результата задач на трех MIP солверах получилось не однозначным. Поэтому избегать "пользовательские переменные" - всего лишь рекомендация. Добавлю чеклист по работе с пользовательскими переменными:

• Оценивайте необходимость каждой переменной;

• Проводите тестирование производительности с разными формулировками;

• Документируйте причины введения дополнительных переменных;

• Рассматривайте возможность вычисления некоторых метрик после решения модели.

Плюсы пользовательских переменных:

• Подсчёт суммарных показателей в модели;

• Агрегация ключевых метрик задачи;

• Упрощение извлечения статистики.

Негативное влияние на эффективность решения задачи:

• Увеличивают размерность задачи;

• Создают дополнительные ограничения;

• Могут ухудшать структуру матрицы ограничений.

Обезличивание и симметрия

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

Выбор максимально допустимой степени абстракции объектов в оптимизационной модели залог повышенной скорости решаемости задачи

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

В такой задаче достаточно рассматривать объединенные группы по типам транспорта и локациям. Необходимости моделировать каждый ресурс в отдельности - нет.

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

Вариант реализации 1:

- бинарная переменная, назначение ресурса на заявку ;

- на каждый ресурс необходимо назначить не более одной заявки;

- на каждую заявку необходимо назначить не более одного ресурса.

Вариант реализации 2:

- целочисленная переменная, кол-во задействованных ресурсов;

- целочисленная переменная, кол-во заявок запланированных к выполнению;

- кол-во задействованных ресурсов равно кол-ву заявок к выполнению;

- ограничение на кол-во ресурсов;

- ограничение на кол-во доступных заявок.

Проанализируем модели.

• В первом варианте имеем 9 бинарных переменных и 6 ограничений, во втором варианте - 2 целочисленные переменные и 3 ограничения.

• В случае целевой функции максимизации кол-ва выполненных заявок у первой модели 6 различных решений, у второй модели - всего 1.

• Во второй постановке убрали симметричные решения, так как в задаче нет факторов, которые вносят влияние отдельно выбранного ресурса на целевую функцию. Поэтому обезличивание ресурсов в постановке №2 вполне оправдано.

По формулировке первая модель имеет классическую постановку задачи о назначениях, вторая модель - близка к транспортной задаче или задаче потока минимальной стоимости.

Рассмотрим другую задачу (Crew scheduling problem). Пусть имеем оценочный штат водителей и набор работ к покрытию водителями. Каждая работа имеет время-место начала и окончания движения. Для каждого водителя из штата сотрудников строим все возможные переходы в виде потоков в сети с учетом режима труда и отдыха (допустимые графики работы). Холостые возможности переходов для всех водителей одинаковые. Цель: покрыть весь объем работ минимальным кол-вом водителей.

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

Не гарантировано, но устранение такой симметрии может привести к ускорению в поиске оптимального решения. Для этого можно ввести следующие ограничения устранения симметрии:

1. По номеру водителя: если выбран водитель №2, то должен быть выбран водитель №1

2. По нагрузке на водителя: водитель №1 работает не меньше, чем водитель №2

где сумма по - сумма по работам, а длительность работы.

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

Плюсы от устранения симметрии

• Сокращение времени поиска решения;

• Уменьшение размера пространства поиска;

• Повышение эффективности алгоритмов оптимизации;

• Упрощение анализа результатов.

Больше строк в матрице ограничений всегда плохо?

Существует определенный тип ограничений, который предоставляют вариацию формулировки:

где и бинарные переменные.

Другой, эквивалентный (в целочисленной постановке) способ задания указанного выше ограничения (назовем развернутыми):

Рассмотрим частный пример этих ограничений и их влияние на область допустимых решений расслабленной задачи. Пусть имеем переменные и .

В случае точки для расслабленной задачи имеем следующую ситуацию с ограничениями:

Влияние на решение

Агрегированная форма создает более широкую область допустимых решений в расслабленной задаче, что может привести к:

• Большему количеству итераций в алгоритме ветвей и границ;

• Быстрее решает задачу ЛП.

Развернутая форма обеспечивает:

• Более точную границу допустимых решений;

• Быстрее нахождение целочисленного решения;

• Возможное увеличение времени решения ЛП.

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

Исследование влияния формулировки такого рода ограничений разбирал в статье Разделяй и запускай: делим тестовый стенд между департаментами. В материале рассказываю об опыте применения агрегированных и развернутых ограничений.

Типовые модели

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

Академические постановки задач в виде "как есть" редко получается переиспользовать без доработок. Приходится модифицировать модели ограничениями от заказчика. Однако модели можно использовать как балванки для разработки собственной или выстраивать ансамбль из нескольких типовых моделей в комплексное решение.

Почему стоит обратить внимание на типовые модели? Одним из аргументов может быть любопытное поведение при решении некоторых типовых задач ЦЛП:

После решения расслабленной задачи процесс решения целочисленной задачи моментально сваливается в оптимум.

Иначе говоря, поставленная NP-полная задача решается за полиномиальное время. Маленькая победа!

Большинство таких случаев объясняется тем, что множество допустимых решений расслабленной задачи совпадает с выпуклой оболочкой допустимых решений задачи ЦЛП. Как следствие, оптимальное решение расслабленной задачи = оптимальному решению целочисленной задачи. Назовем его - эффект совпадения.

Есть алгоритмический способ добиться такого эффекта? Есть! Процедура Chvátal-Gomorry, в рамках которой добавляются сечения Gomorry. Эта процедура внедрена во многие ЦЛП солверы. Но задачи ЛП (полиномиальное время) и ЦЛП (NP-полная) разной весовой категории, а процедура Chvátal-Gomorry всего лишь еще одна не гарантированная возможность сорвать джекпот.

Может ли разработчик модели добиться эффекта совпадения? Конечно! Если сможет сформулировать ограничения задачи в виде вполне унимодулярной матрицы. А здесь как раз могут помочь типовые модели:

• транспортная задача,

• задача о назначениях,

• задача потока минимальной стоимости

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

• задача о разбиении множества,

• задача покрытия,

• задача упаковки множеств

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

Немного больше информации по переходу к вполне унимодулярной матрице ограничений можно найти в семинаре в рамках сообщества NoML по теме Искусство математического моделирования.

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

Вывод

«Все модели ошибочны, но некоторые полезны» Дж. Бокс

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

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

• Пользовательские переменные — это дополнительные переменные, которые вводятся в модель для упрощения интерпретации результатов или агрегации данных;

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

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

• Типовые модели — это проверенные временем математические конструкции, которые эффективно решают определённые классы задач. Они являются фундаментом для создания более сложных оптимизационных решений.

На этом у меня все! Интересно ознакомиться с вашими практиками и подходами к формализации оптимизационных математических задач.

Ссылки

• Семинар: Искусство математического моделирования

• Разделяй и запускай: делим тестовый стенд между департаментами

• Моделирование нелинейных функций и ограничений в задачах линейного программирования

• H. Paul Williams, Model Building in Mathematical Programming

• Converting weak to strong MIP formulation

• Converting weak to strong MIP formulation Part II

• Jupyter блокнот статьи