Adjacency conflicts in OR-Tools CP-SAT: robust assignment modeling with add_exactly_one and add_at_least_one

Model adjacency conflicts in OR-Tools CP-SAT: replace add_implication with add_exactly_one and add_at_least_one to enumerate all feasible solutions cleanly.

Placing entities with pairwise conflicts into adjacent slots is a classic constraint programming exercise. A compact way to model it in OR-Tools CP-SAT is with Boolean assignment variables and adjacency rules. Yet a seemingly natural encoding with add_implication may fail to reveal feasible arrangements in practice. Below is a self-contained walkthrough that reproduces the issue and then shows a robust formulation that surfaces all feasible placements clearly.

Minimal model that exhibits the issue

The scenario: four dogs, four cages aligned linearly, and a small set of incompatible pairs that must not sit in adjacent cages. The initial version encodes adjacency bans using add_implication.

from ortools.sat.python import cp_model

# Data
pets = ["Lulu", "Abby", "Boone", "Kensey"]
slots = ["cage_A", "cage_B", "cage_C", "cage_D"]

# Incompatible pairs (cannot be adjacent)
clashes = [("Boone", "Lulu"), ("Boone", "Abby")]

# Linear adjacency as ordered pairs
neighbors = [("cage_A", "cage_B"), ("cage_B", "cage_C"), ("cage_C", "cage_D")]

# Model
cp = cp_model.CpModel()

# Boolean assignment: pet p in slot s
assign = {}
for p in pets:
    for s in slots:
        assign[(p, s)] = cp.new_bool_var(f"y_{p}_{s}")

# Each pet in exactly one slot
for p in pets:
    cp.add(sum(assign[(p, s)] for s in slots) == 1)

# Each slot holds at most one pet
for s in slots:
    cp.add(sum(assign[(p, s)] for p in pets) <= 1)

# Adjacency constraints (implications)
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())

# Solve one solution
engine = cp_model.CpSolver()
status = engine.Solve(cp)

# Report
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.")

What actually goes wrong

The objective here is to forbid adjacent placements for specific pairs, while ensuring a perfect matching between dogs and cages. In the variant above, those adjacency bans are expressed via implications. The observed behavior is that the solver may not return one of the truly feasible assignments for this data, even though they exist. The formulation below avoids this by posting the constraints directly as clauses and by enforcing an exact cover on both axes.

Working formulation and fix

The rules can be stated more directly. First, model the bipartite assignment with add_exactly_one both per pet and per slot. Second, encode each adjacency ban as a disjunction of negated literals, i.e., at least one of the two adjacent placements must be false. This uses add_at_least_one on the negated BoolVars. With this, iterating solutions reveals the feasible space cleanly; on this dataset, four solutions are found.

from ortools.sat.python import cp_model

# Data
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")]

# Model
cp = cp_model.CpModel()
assign = {(p, s): cp.new_bool_var(f"y_{p}_{s}") for p in pets for s in slots}

# Perfect matching: exactly one per pet
for p in pets:
    cp.add_exactly_one(assign[(p, s)] for s in slots)

# Perfect matching: exactly one per slot
for s in slots:
    cp.add_exactly_one(assign[(p, s)] for p in pets)

# Adjacency bans as clauses: not both true
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)])

# Solve one solution
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.")

With the model written this way, it becomes straightforward to enumerate all feasible assignments. In one run, four distinct solutions were reported, such as Boone assigned to cage_A with Kensey next to him, or Boone assigned to cage_D with Kensey adjacent on the other side. The remaining options consistent with the data follow the same structure.

Why it is worth knowing

In CP-SAT, clarity of the constraint shape matters. Exact cover patterns benefit from add_exactly_one because they tell the solver unequivocally that the structure is a permutation. For adjacency bans, direct clauses via add_at_least_one on negated literals state “not both” in the form the SAT core handles naturally. This helps expose the feasible region cleanly and makes solution enumeration behave as expected.

Bottom line

For assignment problems with local conflicts, encode the matching as add_exactly_one in both dimensions and express pairwise “cannot be adjacent” as clauses with add_at_least_one on the negated literals. This formulation is compact, debuggable, and yields the feasible assignments for this dataset without surprises.