Несколько раз в год отдел оптимизации офисного пространства Альфа‑Банка думает над тем, как разместить сотрудников бэк‑офиса по локациям на несколько лет вперёд. Раньше ребята делали это вручную: было медленно (месяц работы), больно (Excel) и неоптимально (никто не мог гарантировать, что найденная рассадка удовлетворяет всем ограничениям).

Коллеги хотели автоматизировать ручную работу — с этим они и пришли к нам. 

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

Условия задачи и ограничения

Немного контекста.

Бэк‑офис — это внутренние подразделения банка, которые обеспечивают его работу, но не взаимодействуют напрямую с клиентами, например, IT или HR. Сотрудники бэк‑офиса находятся по всей России, но мы будем говорить только про Москву (задача рассадки сотрудников в регионах перед нами пока не стояла).

Москва разделена на локации, например, Комсомольская или Технопарк. Внутри локации есть блоки, в которых обычно по 2-4 офиса. 

Далее есть БЛ — бизнес-линии (что-то вроде департамента), их обычно несколько десятков. Для каждой бизнес-линии есть некоторое количество требуемых мест для рассадки на несколько лет вперед. Нужно найти рассадку, которая учитывала бы множество ограничений:

1. Есть БЛ, которые нельзя делить по разным офисам/блокам/локациям.

2. Некоторые БЛ должны занимать только ближайшие этажи.

3. Нужно учесть количество требуемых кабинетов на этажах и закрытые контуры.

4. И ещё некоторое количество требований, которые мы опустим.

В целом, задача звучала так:

Автоматизировать ручной процесс с учётом множества бизнес-правил и ограничений, найти самое оптимальное решение и в итоге получить план рассадки сразу на несколько лет вперед с учетом роста потребности в местах. 

Рассчитать в Excel такое сложно. Представьте, что в каком-то департаменте в следующем году появится 500 человек и их придется досаживать на ближайшие этажи и брать где-то еще места…

Если вы вдруг возьметесь за эту задачу, то, вероятнее всего, первым делом захотите узнать, как это делают в других компаниях. И не узнаете)) Почему-то такой информацией никто не делится. Сейчас мы это исправим.

Про задачу оптимизации и CP-SAT

Задачу оптимизации в общем виде можно сформулировать следующим образом: 

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

В нашем случае мы должны найти такую рассадку, которая бы удовлетворяла бизнес-требованиям и минимизировала количество нерассаженных сотрудников БЛ.

Посмотрим, как можно решать подобные задачи.

Подход №1: CP (Constraint Programming)

CP (Constraint Programming) использует декларативный подход для решения задач выполнимости — поиска набора значений переменных, удовлетворяющего всем ограничениям (отсюда constraint в названии метода).

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

Как и в декларативном подходе, с помощью CP мы описываем, что хотим получить (а получить мы хотим выполнение правил рассадки) — это называется модель. У модели есть переменные и ограничения. 

Переменные определяют то, что мы ищем. Например, в задаче рассадки бэк‑офиса целевая переменная — сколько мест БЛ занимает на определенной площадке. 

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

Наконец, нужно ввести ограничения, описывающие связи между переменными. Например, если БЛ переехала из Офиса 1 в Офис 2, то переменная с переездом этой БЛ будет равна 1, иначе — 0.

Вообще, в CP есть богатый набор ограничений. Из тех, что я использовала, например:

1. Линейные ограничения (x + y <= 10).

2. Логические ограничения:

   • AddBoolAnd, AddBoolOr — булевы И/ИЛИ;

   • OnlyEnforceIf — логическая импликация (A ⇒ B);

   • AddExactlyOne — ровно одно значение из списка истинно;

   • и др.

3. Мин/макс ограничения: AddMaxEquality (x = max(y, z)).

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

CP-solver перебирает возможные значения переменных, чтобы найти допустимые решения, используя различные оптимизации:

№1. Constraint Propagation (распространение ограничений).

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

Пример: есть ограничение x < z; x,z > 0. Если, например, решатель начинает перебор с x = 3, тогда область определения zсузится до интервала [4, ∞), тем самым решатель исключит из перебора три значения z за один шаг.

№2. Backtracking (поиск с возвратом).

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

Пример: есть ограничения x < y, y = max(x, z), y < 5. Пусть решатель на данном этапе начинает перебор с x = 3 и y = 4:

Подход №2: SAT (Boolean Satisfiability)

SAT (Boolean Satisfiability) — задача булевой выполнимости. Пытается выяснить, существует ли набор значений переменных (каждая из которых может быть истиной или ложью), при котором заданная булева формула принимает значение ИСТИНА. 

Или по-простому: можно ли подобрать такие ИСТИНА и ЛОЖЬ для переменных, чтобы все выражение стало ИСТИНОЙ?

Если такой набор существует, формула называется выполнимой (satisfiable), в противном случае невыполнимой (unsatisfiable). 

Современные SAT-решатели умеют запоминать, почему какой-то вариант не сработал, и больше не пробовать похожие (в отличие от CP-солверов) — этот механизм называется Conflict-Driven Clause Learning (CDCL). Как это работает:

1. Решатель делает предположение (например, x = ИСТИНА).

2. Начинает выводить следствия из этого предположения через распространение ограничений (propagation).

3. После propagation строит implication graph (импликационный граф) — ориентированный граф, в котором: 

   • Вершины — это присвоенные значения переменных, например, x = ИСТИНА.

   • Рёбра — импликации между вершинами: если одна вершина истинна, то из неё следует истинность другой вершины [x] → [y].
     Например, ребро от вершины x = ИСТИНА к y = ИСТИНА означает, что из x = ИСТИНА следует y = ИСТИНА.

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

5. Отрицание предположений, приведших к противоречию, запоминается как conflict clause (или nogood).

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

CP + SAT OR-Tools

С SAT и CP по отдельности разобрались, теперь про их гибрид — решатель CP‑SAT из библиотеки OR‑Tools от Google, который я использовала в задаче рассадки бэк‑офиса.

Суть же метода LCG состоит в том, чтобы добавить к решателю CP возможность обучения и запоминания «плохого опыта» (nogood learning) из SAT-решателя.

SAT-решатель оперирует булевыми переменными и выражениями. В CP-SAT переменные целочисленные, и просто так взять и применить CDCL-алгоритм SAT-решателя к ним нельзя.

LCG решает эту проблему так:

1. Кодирует целочисленные переменные в булевы и накладывает на них clauses (дизъюнкты) для описания отношения между ними.
   Например, для переменной x ∈ [0, 5] получаем:

   • булевы переменные:
     [x ≤ 0], [x ≤ 1], [x ≤ 2], [x ≤ 3], [x ≤ 4]- пороги;
     [x = 0], [x = 1], [x = 2], [x = 3], [x = 4], [x = 5]- равенства.

   • и дизъюнкты:
     [x ≤ d] → [x ≤ d+1]- clause на монотонность порогов;
     только одно из равенств [x = d], [x = d+1],.. истинно - clause на равенства.
     
     (Скобки нужны для того, чтобы получить значения ИСТИНА или ЛОЖЬ от выражения)

2. Распространяет ограничения методом CP для исходных целочисленных переменных и создаёт на их основе новые clauses.
   Например, если есть ограничение x ≥ y и предыдущими итерациями установлено[x ≤ 2], то генерируется clause [x ≤ 2] → [y ≤ 2]. Эти дизъюнкты добавляются в implication graph.

3. Использует nogood learning из SAT.
   На основе графа импликаций выявляются причины конфликта и создаются nogoods (условия, которые приводят к неудаче), чтобы избежать повторения тех же ошибок в будущем.

Также OR-Tools CP-SAT поддерживает распараллеливание вычислений между ядрами процессора через параметр num_search_workers.

Ну и где тут оптимизация?

Важно отметить, что классический CP решает задачу выполнимости (поиска возможного решения), а не оптимизации (поиска оптимального решения с точки зрения целевой функции). 

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

Для решения задачи оптимизации в OR-Tools CP-SAT используется метод ветвей и границ: 

1. Solver находит первое допустимое решение. Допустим, 7 переездов. Это наш текущий рекорд (верхняя граница).

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

3. Решает задачу с новым ограничением: на каждом шаге поиска, исследуя очередную ветвь (подмножество решений), solver оценивает её нижнюю границу — минимум целевой функции, который вообще можно достичь.

4. Если нижняя граница (например, 9) оказывается хуже верхней границы (7 переездов), решатель отсекает эту ветвь. Даже в теории там не может быть значения лучше нашего рекорда.

5. Если же нижняя граница (например, 5) оказывается лучше текущего рекорда (7 переездов), solver ищет в этой ветке реальное целочисленное решение (например, 6).

6. Найдя 6, солвер обновляет рекорд. Теперь он ищет решение меньше 6 переездов.

7. Повторяет пункты 1-6, пока нижняя граница (теоретический минимум) и верхняя граница (текущий рекорд) не сравняются или не будет достигнут лимит по времени, заданным пользователем.

Сервис для размещения рабочих мест

Для бизнеса мы реализовали веб-сервис на не очень нишевом streamlit со следующим сценарием использования:

1. Пользователь загружает файл с исходными данными для рассадки:

   • Данные по офисам.
     Они имеют следующую структуру: локация — блок — офис — этаж.

   • Фиксированные БЛ.
     Здесь пользователем фиксируется рассадка тех БЛ, которые не будут переезжать (например, в каждом офисе должны быть сотрудники IT-сопровождения).

   • Начальная рассадка.
     Рассадка, актуальная на сегодняшний день, относительно которой будем считать переезды.

   • Разбивка по приоритетам БЛ (об этом позже).

2. Пользователь нажимает кнопку «Запустить решатель».

3. Streamlit идет в PostgreSQL и добавляет в таблицу с задачами новую таску, чтобы потом отслеживать статус её выполнения.

4. Запускает фоновый процесс через threading в python - модуль для работы с многопоточностью:

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

   • во-вторых, если страница закроется или перезагрузится (а streamlit любит такое делать — сам решууу), решатель прервется.

5. Запуск решателя CP-SAT OR-Tools, который записывает результат работы в таблицу с тасками.

6. Streamlit раз в пару минут проверяет статус задачи в таблице с тасками, чтобы после завершения работы решателя вывести результат на страницу пользователю.

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

№1. Фиксируем начальную рассадку, заданную пользователем, для последующего подсчета переездов, отталкиваясь от нее.

№2. Для следующих лет сначала рассаживаем фиксированные БЛ, переданные пользователем, которые не будут переезжать и участвовать в динамической рассадке.

№3. Для остальных БЛ задаем в CP-SAT OR-Tools переменные и ограничения для каждого года отдельно.

Переменные:

а) X[(bl_name, o, f)] — количество занятых мест БЛ «bl_name» в офисе «o» на этаже «f»

b) x_unsettled[bl_name] — количество нерассаженных людей (да, такое тоже может быть)

c) Переменные выбора площадки:

• x_office_is_chosen[(bl_name, o)] # 1, если БЛ заняла офис o

• x_block_is_chosen[(bl_name, b)] # 1, если БЛ заняла блок b

• x_loc_is_chosen[(bl_name, l)] # 1, если БЛ заняла локацию l

• x_floor_is_chosen[(bl_name, f)] # 1, если БЛ заняла этаж f

d) Переменные с переездами:

• move_loc_vars[(bl_name, loc1, loc2)] # 1, если БЛ переехала между локациями loc1 и loc2

• move_block_vars # переезд между блоками

• move_office_vars # переезд между офисами

• move_floors_vars # переезд между этажами

e) move_places_var — целевая переменная, которую хотим минимизировать. Представляет собой взвешенную сумму переездов.

Основные ограничения:

a) Количество занятых мест + количество нерассаженных = количество требуемых пользователем:
sum(X[(bl_name,o,f)] for all o,f) + x_unsettled[bl_name] == required_seats

b) Ограничение на переменные выбранной площадки.
Например, если БЛ нельзя делить по разным офисам, только одна переменная x_office_is_chosen должна быть равна 1.

c) Вместимость этажа:
X[(bl_name, o, f)] не может быть больше кол-ва свободных мест на этаже

d) Доступность площадки:
X[(bl_name, o, f)] = 0, если офис «o» ещё не открыт в этом году

e) Ограничения на закрытый контур и кабинеты.
Если бизнес-линия требует закрытый контур, то этаж должен предполагать наличие закрытого контура.
Количество кабинетов на занятых этажах должна быть не меньше требуемого числа.

Затем идет разветвление в решении задачи.

Условие x_unsettled == 0 (все БЛ рассажены в полном объеме):

* для БЛ, в зависимости от её приоритета, заранее задаем допустимый процент нерассаженных (например, для БЛ с приоритетом 5 допустимо до 15% дефицита).

Беды ✨

Во-первых, успех решения задачи сильно зависит от того, как вы задали переменные и их области определения, описали связи между ними и добавили ограничения. Если при запуске солвера, он буквально через секунду возвращает статус INFEASIBLE, скорее всего это значит, что не очень аккуратно объявлены переменные и ограничения. Есть полезная статья Подробный гайд: Оптимизация моделей Constraint Programming (CP) про то, как этого избежать.

Спустя несколько дней ресерча я нашла не медь, а золото — CPMpy, про который почему-то не так много упоминаний. 

CPMpy — это библиотека Python для решения задач CP, которая позволяет:

• во‑первых, описать задачу на удобном Python‑языке,

• а во‑вторых, запустить её решение на различных встроенных солверах (в том числе ortools), не подстраиваясь под их синтаксис и используя автоматическую декомпозицию высокоуровневых ограничений, если выбранный решатель их не поддерживает.

Наконец, она предоставляет explanation tools — инструменты для поиска несовместных (конфликтующих) ограничений.

В частности, там есть метод MARCO, который ищет все MCS (Minimal Correction Sets) исследуемой модели. Таким образом, мы предоставляем пользователю несколько наборов ограничений, чтобы он сам выбрал, какие из них убрать/смягчить, чтобы рассадить всех коллег.

Алгоритм поиска следующий:

1. Пытаемся максимизировать количество БЛ, у которых дефицит мест попал в допустимый интервал в зависимости от приоритета.
   Например, у БЛ1 с приоритетом 1 допустимый процент нерассаженных сотрудников 5%, а у БЛ2 с приоритетом 2 — 10%. Тогда хорошим вариантом будет, если мы попадаем у обеих БЛ в этот допустимый интервал.

2. Найденный максимум фиксируем как новое ограничение модели, и для него пытаемся найти минимум нерассаженных.

3. Для найденного минимума нерассаженных минимизируем переезды.

4. Итоговое решение с учётом дефицита выдаём пользователю.

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

Получаем довольно гибкое решение.

Ещё более гибким его может сделать только поиск нескольких оптимальных вариантов. По просьбе бизнес-заказчиков наш сервис также умеет возвращать несколько (обычно 5-7) решений вблизи оптимума.

Для этой цели можно создать свой класс, унаследовав его от CpSolverSolutionCallback из CP-SAT OR-Tools, и вручную собирать решения в список. Этот класс возвращает решения, которые решатель перебирает при поиске самого оптимального. При этом, так как CP-SAT-солвер отсекает ветви, которые не ведут к оптимизации целевой функции, каждое следующее найденное решение будет лучше предыдущего. Поэтому мы просто возьмем конец списка и выведем его пользователю.

На этой все, спасибо за внимание!