Модель ограничений

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

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

Область применения

Алгоритмы программирования в ограничениях лежат в основе систем класса APS (Advanced Planning and Scheduling), MES (Manufacturing Execution System), WMS (Warehouse Management System), а также модулей оптимизации в ERP-системах. Типовые сценарии прикладной автоматизации в 1С:Предприятие:

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

Типовые задачи

Назначение (assignment)

Сопоставление элементов одного множества элементам другого: «работник → задача», «заказ → поставщик», «студент → группа». Формулируется через матрицу булевых переменных «выбрано/не выбрано» с ограничениями на количество единиц в строках и столбцах.

Раскраска и разбиение

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

Расписание сотрудников

Назначение смен сотрудникам с учётом ограничений по последовательности (например, отсутствия двух ночных смен подряд), часам нагрузки и пожеланиям персонала. Формулируется средствами булевой логики и конечных автоматов.

Расписание работ цеха (jobshop)

Каждая работа состоит из операций, выполняемых на разных станках; на одном станке в один момент времени выполняется не более одной операции; внутри работы установлен порядок операций. Задача характерна для оперативного производственного планирования. Формулируется через интервалы и ограничения на запрет перекрытий.

Раскрой и упаковка (1D, 2D)

Размещение элементов фиксированных или варьирующихся размеров в ограниченных контейнерах без перекрытий. Формулируется через интервалы и прямоугольники.

Управление запасами

Ресурс, изменяющийся во времени за счёт приходов и расходов, остаток которого должен оставаться в допустимом диапазоне. Формулируется через резервуары.

Логические головоломки

Sudoku, N ферзей, кроссворды, расстановки фигур по правилам. Класс задач, удобный для отработки техник моделирования.

Глоссарий

Термин	Определение
Переменная	Целочисленная неизвестная величина, значение которой определяет решатель. Бывает полной (с широким диапазоном), диапазона, домена или булевой.
Константа	Переменная с одним возможным значением; используется как именованное число в выражениях и ограничениях.
Домен	Множество допустимых целых значений: диапазон, перечислимый список, объединение или пересечение нескольких множеств.
Линейное выражение	Линейная комбинация переменных вида a₁·x₁ + a₂·x₂ + ... + c. Ограничения и целевая функция формулируются над выражениями.
Ограничение	Условие, которому должно удовлетворять решение. Может быть обязательным или условным (активируется булевой переменной).
Булева переменная	Переменная со значениями {0, 1}. Используется как индикатор активации ограничения, флаг существования интервала, признак выбора альтернативы, индикатор использования дуги графа.
Интервал	Тройка переменных «начало + размер = конец», базовая конструкция расписаний. Бывает обязательным или опциональным.
Прямоугольник	Пара интервалов по осям X и Y, базовая конструкция упаковки 2D.
Потребность интервала	Привязка интервала к ресурсу с указанием количества единиц ресурса, требуемых интервалом.
Резервуар	Ресурс с динамически изменяющимся остатком, описываемый событиями накопления.
Конечный автомат	Объект, описывающий разрешённые последовательности состояний через явный набор переходов.
Целевая функция	Линейное выражение, минимум или максимум которого ищет решатель. Если не задано — выполняется поиск любого допустимого решения.
Решение	Набор значений всех переменных, найденный решателем.
Допустимое / оптимальное решение	Допустимое — удовлетворяет всем ограничениям; оптимальное — также имеет минимум или максимум целевой функции, доказанный решателем за время поиска.

Принцип работы

Решение прикладной задачи моделью ограничений выполняется в следующей последовательности действий разработчика:

1. Формализация задачи. Из прикладной задачи выделяются неизвестные величины, условия их совместимости и — если требуется не любое допустимое решение, а оптимум — критерий выбора лучшего варианта.
2. Создание объекта модели. Через фасад О2.Модели().МодельОграничений().СоздатьМодель() создаётся пустой контейнер, в котором затем регистрируются переменные и ограничения.
3. Регистрация переменных. Каждой неизвестной величине ставится в соответствие переменная подходящего типа: булева — для «да/нет», целочисленная или диапазона — для количеств, домена — для перечислимых наборов значений. Значения переменных не задаются — их вычисляет решатель.
4. Описание ограничений. Условия задачи формулируются методами менеджера ограничений — арифметические соотношения над линейными выражениями, попарная различность, булева логика, интервалы и ресурсы для расписаний, прямоугольники для упаковки, автоматы для последовательностей. Любое ограничение можно сделать условным — активируемым булевой переменной-индикатором.
5. Задание целевой функции (опционально). Задаётся линейное выражение и направление поиска: минимизация или максимизация. Без целевой функции решатель ищет любое допустимое решение.
6. Передача подсказок и предположений (опционально). Стартовое решение или ожидаемые значения переменных ускоряют поиск, не изменяя множества допустимых решений.
7. Запуск поиска и обработка решения. Вызов Модель.Решить() инициирует направленный перебор с отсечением: ветви, заведомо не содержащие решений, не посещаются. Из объекта решения извлекается статус (оптимальное, допустимое, отсутствие решения, ошибка модели) и значения переменных, по которым восстанавливается прикладной ответ.

Шаги 3–6 выполняются в произвольном порядке и могут чередоваться: переменные допустимо регистрировать по мере появления связанных с ними ограничений. Существенным остаётся лишь то, что к моменту вызова Модель.Решить() в модели зарегистрированы все переменные, на которые ссылаются ограничения и целевая функция.

Сильные и слабые стороны

Сильные стороны

• Гибкость. Пять семейств ограничений (значения и комбинации, булева логика, интервалы и ресурсы, графы и автоматы, последовательности) покрывают большинство дискретных задач без необходимости моделировать условия «вручную» через пары переменных.
• Универсальность. Одна модель применяется и к расписаниям, и к упаковке, и к назначениям, и к комбинаторным задачам — нет необходимости переключаться между разными API в зависимости от класса задачи.
• Опциональность. Булевы переменные-индикаторы и опциональные интервалы позволяют моделировать условные элементы решения («эта работа выполняется только если…») без перестройки модели.
• Многокритериальная оптимизация. Несколько критериев сворачиваются в одно линейное выражение через взвешенную сумму с настраиваемыми приоритетами.
• Условные ограничения. Любое ограничение можно сделать активным только при истинности набора булевых выражений — этим переключаются «ветви» правил без дублирования кода.

Слабые стороны и пределы применимости

• Только целочисленные значения. Дробные величины (стоимость с копейками, время с долями часа) моделируются через масштабирование. Для задач, существенно опирающихся на непрерывные количества, применяются линейные модели.
• Нелинейный рост времени поиска оптимума. На больших задачах доказательство оптимальности может быть существенно дороже нахождения первого допустимого решения. На таких задачах применяется ограничение времени поиска и работа с подсказками.
• Косвенная поддержка нелинейности. Произведение двух переменных, индексирование массива по переменной, абсолютное значение — выражаются через вспомогательные переменные и специальные ограничения (ПроизведениеРавно, ЭлементРавен, АбсолютноеЗначениеРавно), а не задаются записью «x * y» в линейном выражении.

Ориентиры по объёмам данных

Точные оценки времени поиска зависят от структуры задачи и качества формулировки, однако качественные диапазоны таковы:

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

Сравнение со специализированными моделями

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

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

Класс задачи	Рекомендованная модель	Почему специализированная модель эффективнее
Выбор подмножества предметов в один контейнер по «весу» и «ценности», без учёта порядка	Задача о ранце	Использует алгоритмы динамического программирования и специализированных эвристик с теоретическими гарантиями.
Маршруты транспортных средств с матрицами расстояний, депо, грузоподъёмностью, временными окнами	Модель маршрутизации	Применяет двухфазный поиск со специализированными стратегиями построения первого решения (PathCheapestArc, Savings, Christofides) и метаэвристиками локального поиска (GuidedLocalSearch, TabuSearch); см. Параметры поиска. Масштабируется до тысяч узлов при сохранении качества решения.
Количества с дробными значениями, распределение ресурсов, планирование с непрерывными переменными	Линейные модели	Применяют симплекс-метод и метод ветвей и границ с непрерывной релаксацией; обеспечивают высокую скорость на задачах с большим числом ограничений и переменных.
Максимальный поток в сети с пропускными способностями	Модель максимального потока	Использует алгоритмы максимального потока с полиномиальной сложностью.
Минимальная стоимость потока с заданными источниками и стоками	Модель потока минимальной стоимости	Использует алгоритмы поиска потока минимальной стоимости с полиномиальной сложностью.

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

Составные части модели

• Создание объекта модели
• Переменные
• Домены
• Линейные выражения
• Ограничения
• Целевая функция
• Управление поиском
• Решение модели

Примеры использования модели

• Составление оптимальной диеты
• Составление графика работы сотрудников
• Оперативное производственное планирование
• Поиск оптимального маршрута (задача коммивояжёра)
• Размещение товаров на плоскости
• Назначение исполнителей с балансировкой нагрузки
• Решение задачи N ферзей
• Решение головоломки Судоку

Программный интерфейс

Полное описание методов модели ограничений приведено в разделе Программный интерфейс — Модель ограничений.