Conflict analysis and no-good cuts

Branch-and-bound spends most of its effort re-discovering infeasibility: the same hopeless combination of binary choices is fixed, propagated, and rejected again and again in different parts of the tree. Conflict analysis turns each such dead end into a reusable fact. When a partial assignment of binaries is proven infeasible — no feasible solution sets those binaries that way — discopt derives a no-good cut that forbids exactly that assignment, so the same conflict is never re-explored elsewhere in the tree [Achterberg, 2007].

For an assignment \(a\) over a subset \(S\) of binaries, the no-good cut is

\[ \sum_{j \in S:\, a_j = 1} (1 - x_j) \;+\; \sum_{j \in S:\, a_j = 0} x_j \;\ge\; 1 . \]

It is violated only by the exact assignment \(a\) (where the left-hand side is \(0\)) and is satisfied by every other \(0/1\) combination of the involved variables. It therefore removes one proven-dead leaf and nothing else — the global optimum is untouched.

This is the mixed-integer analogue of clause learning in modern SAT and constraint solvers: a discovered conflict is recorded as a learned clause that prunes the rest of the search [Marques-Silva and Sakallah, 1999]. Achterberg adapted this idea to mixed-integer programming, where conflict constraints generalise learned clauses to the LP/MIP setting [Achterberg, 2007, Achterberg et al., 2020]. A no-good cut is the simplest such conflict constraint: a single clause over binaries.

import discopt.modeling as dm
from discopt.conflict import find_conflict_cuts, add_conflict_cuts, no_good_cut

Detecting conflicts

Consider three binaries under a set-packing constraint \(x_0 + x_1 + x_2 \le 1\): at most one may be on. Every assignment that turns two of them on is jointly infeasible, even though no single variable is fixed. find_conflict_cuts probes subsets of binaries up to max_order, fixes each candidate assignment, and runs FBBT as the infeasibility oracle. Each FBBT-proven conflict yields a no-good cut. The cuts are returned (not yet added to the model) so you can inspect them.

m = dm.Model("packing")
x = [m.binary(f"x{i}") for i in range(3)]
m.maximize(x[0] + 2 * x[1] + 3 * x[2])
m.subject_to(x[0] + x[1] + x[2] <= 1)   # at most one binary may be on

cuts = find_conflict_cuts(m, max_order=2)
print(f"{len(cuts)} no-good cut(s) derived:")
for c in cuts:
    print("  ", c)

3 no-good cut(s) derived:
   (1 - ((1 - x0) + (1 - x1))) <= 0.0
   (1 - ((1 - x0) + (1 - x2))) <= 0.0
   (1 - ((1 - x1) + (1 - x2))) <= 0.0

Each derived cut forbids one of the three pairwise “both on” assignments — \((x_0{=}1, x_1{=}1)\), \((x_0{=}1, x_2{=}1)\), \((x_1{=}1, x_2{=}1)\) — written in the no-good form \((1 - x_i) + (1 - x_j) \ge 1\). The detector keeps only minimal conflicts: an assignment is skipped if a shorter, already-found conflict is a subset of it, so it never reports a redundant superset of a conflict it has already learned.

Building a no-good cut by hand

If you already know an assignment is bad — say from a callback, a heuristic, or domain knowledge — you can construct the cut directly with no_good_cut. It takes a list of (variable, value) pairs and returns the corresponding constraint, which you then add to the model like any other. Here we forbid the specific assignment \(a = 1,\ b = 0\).

m2 = dm.Model("by_hand")
a = m2.binary("a")
b = m2.binary("b")

cut = no_good_cut([(a, 1), (b, 0)])   # forbids exactly (a=1, b=0)
print("derived cut:", cut)

m2.subject_to(cut, name="forbid_a1_b0")
print("constraints now in model:", m2.num_constraints)

derived cut: (1 - ((1 - a) + b)) <= 0.0
constraints now in model: 1

The cut \((1 - a) + b \ge 1\) is violated only by \(a = 1, b = 0\) and satisfied by the other three combinations — exactly the clause that excludes a single leaf.

Detecting and injecting in one step

add_conflict_cuts combines the two operations: it detects conflicts and adds the resulting no-good cuts straight to the model, returning the number added. Because every cut excludes only an FBBT-proven infeasible assignment, the feasible region — and the optimum — is unchanged; only dead subtrees are pruned.

m3 = dm.Model("inject")
y = [m3.binary(f"y{i}") for i in range(3)]
m3.maximize(y[0] + 2 * y[1] + 3 * y[2])
m3.subject_to(y[0] + y[1] + y[2] <= 1)

before = m3.num_constraints
n_added = add_conflict_cuts(m3, max_order=2)
print(f"cuts added: {n_added}")
print(f"constraints: {before} -> {m3.num_constraints}")

cuts added: 3
constraints: 1 -> 4

Relationship to IIS and FBBT

Conflict analysis sits between two tools documented elsewhere in this book.

Versus IIS. An Irreducible Infeasible Subsystem answers why an already-infeasible model has no solution: it returns a minimal set of constraints and bounds that conflict, computed by deletion filtering [Chinneck, 2008]. Conflict analysis answers a different question on a feasible model: which partial assignments of binaries can never extend to a solution? Its output is a set of no-good cuts over variables, meant to be added back to accelerate the search rather than to explain a failure. IIS is a diagnostic you run once when solve() returns infeasible; conflict cuts are valid inequalities you add to a feasible model to prune the tree. Both rest on a minimality principle — IIS over constraints, conflict analysis over the fixed binaries in each assignment.

Built on FBBT. The infeasibility oracle for conflict detection is feasibility-based bound tightening. When a candidate assignment is fixed, find_conflict_cuts runs fbbt_box; if propagation collapses some variable’s interval to empty, the assignment is provably infeasible [Puranik and Sahinidis, 2017]. Because FBBT only ever derives valid bounds, it never reports a feasible subproblem as infeasible — so a no-good cut emitted from an FBBT-proven conflict never excludes a feasible point, and in particular never cuts off the global optimum.

Summary

Conflict analysis converts proven-dead binary assignments into reusable no-good cuts, so a contradiction discovered once need never be re-explored. no_good_cut builds a single clause by hand, find_conflict_cuts discovers minimal conflicts via FBBT, and add_conflict_cuts injects them in one call — each cut sound by construction, pruning the search without altering the feasible region [Achterberg, 2007].