Размещение с конфликтами в OR-Tools CP-SAT: исправляем импликации на клаузы

OR-Tools CP-SAT: как корректно задать запреты соседства без add_implication — используем add_exactly_one и клаузы add_at_least_one; пример на размещении.

Размещение объектов с попарными конфликтами в соседние слоты — классическая задача для constraint programming. Компактная модель в OR-Tools CP-SAT строится на булевых переменных назначения и правилах соседства. Однако на практике на первый взгляд естественная схема с add_implication может не подсветить существующие допустимые раскладки. Ниже — самодостаточный разбор: сначала воспроизводим проблему, затем показываем устойчивую формулировку, которая прозрачно выявляет все допустимые размещения.

Минимальная модель, на которой проявляется проблема

Сюжет: четыре собаки, четыре клетки, выстроенные в линию, и несколько несовместимых пар, которым нельзя сидеть в соседних клетках. В начальном варианте запреты соседства кодируются через add_implication.

from ortools.sat.python import cp_model
# Данные
pets = ["Lulu", "Abby", "Boone", "Kensey"]
slots = ["cage_A", "cage_B", "cage_C", "cage_D"]
# Несовместимые пары (не могут стоять рядом)
clashes = [("Boone", "Lulu"), ("Boone", "Abby")]
# Линейное соседство как упорядоченные пары
neighbors = [("cage_A", "cage_B"), ("cage_B", "cage_C"), ("cage_C", "cage_D")]
# Модель
cp = cp_model.CpModel()
# Булево назначение: питомец p в слоте s
assign = {}
for p in pets:
    for s in slots:
        assign[(p, s)] = cp.new_bool_var(f"y_{p}_{s}")
# Каждый питомец ровно в одном слоте
for p in pets:
    cp.add(sum(assign[(p, s)] for s in slots) == 1)
# В каждом слоте не более одного питомца
for s in slots:
    cp.add(sum(assign[(p, s)] for p in pets) <= 1)
# Ограничения соседства (импликации)
for a, b in clashes:
    for s1, s2 in neighbors:
        cp.add_implication(assign[(a, s1)], assign[(b, s2)].Not())
        cp.add_implication(assign[(b, s2)], assign[(a, s1)].Not())
# Поиск одного решения
engine = cp_model.CpSolver()
status = engine.Solve(cp)
# Отчет
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("Solution:")
    for p in pets:
        for s in slots:
            if engine.value(assign[(p, s)]):
                print(f"  {p} -> {s}")
else:
    print("No solution found.")

Что именно идет не так

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

Рабочая формулировка и исправление

Правила можно сформулировать прямо. Во‑первых, смоделировать двудольное назначение с помощью add_exactly_one — и по питомцам, и по слотам. Во‑вторых, каждое табу на соседство задать как дизъюнкцию отрицательных литералов: по меньшей мере одно из двух соседних назначений должно быть ложным. Это реализуется через add_at_least_one на отрицаниях BoolVars. С такими ограничениями перебор решений чисто раскрывает допустимое пространство; на этих данных находятся четыре решения.

from ortools.sat.python import cp_model
# Данные
pets = ["Lulu", "Abby", "Boone", "Kensey"]
slots = ["cage_A", "cage_B", "cage_C", "cage_D"]
clashes = [("Boone", "Lulu"), ("Boone", "Abby")]
neighbors = [("cage_A", "cage_B"), ("cage_B", "cage_C"), ("cage_C", "cage_D")]
# Модель
cp = cp_model.CpModel()
assign = {(p, s): cp.new_bool_var(f"y_{p}_{s}") for p in pets for s in slots}
# Совпадение один к одному: ровно один слот для каждого питомца
for p in pets:
    cp.add_exactly_one(assign[(p, s)] for s in slots)
# Совпадение один к одному: ровно один питомец для каждого слота
for s in slots:
    cp.add_exactly_one(assign[(p, s)] for p in pets)
# Запрет соседства как клаузы: не могут быть истинны одновременно
for a, b in clashes:
    for s1, s2 in neighbors:
        cp.add_at_least_one(~assign[(a, s1)], ~assign[(b, s2)])
        cp.add_at_least_one(~assign[(b, s1)], ~assign[(a, s2)])
# Поиск одного решения
engine = cp_model.CpSolver()
status = engine.Solve(cp)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("Solution:")
    for p in pets:
        for s in slots:
            if engine.value(assign[(p, s)]):
                print(f"  {p} -> {s}")
else:
    print("No solution found.")

При такой записи модели становится просто перечислять все допустимые назначения. В одном запуске было получено четыре различных решения, например Boone назначен в cage_A с Kensey по соседству, или Boone назначен в cage_D, а Kensey — рядом с другой стороны. Остальные варианты, не противоречащие данным, устроены аналогично.

Почему это важно знать

В CP-SAT важна выразительность формы ограничений. Шаблоны точного покрытия выигрывают от add_exactly_one, поскольку они недвусмысленно говорят решателю, что структура — это перестановка. Для запретов соседства прямые клаузы через add_at_least_one на отрицательных литералах задают «не оба сразу» в форме, которая естественна для SAT-ядра. Это помогает чисто проявить допустимую область и делает перечисление решений предсказуемым.

Итог

Для задач назначения с локальными конфликтами задавайте соответствие через add_exactly_one в обоих измерениях, а пары «не могут быть соседями» выражайте как клаузы с add_at_least_one на отрицательных литералах. Такая постановка компактна, проста для отладки и без сюрпризов возвращает допустимые назначения для этих данных.