The Automatic Decomposition Advisor#
Many optimization models have structure a solver can exploit: fixing a few complicating variables disconnects the problem into independent recourse blocks (Benders decomposition [Benders, 1962], and its nonlinear generalization GBD [Geoffrion, 1972]); a few coupling constraints link otherwise-independent blocks (Lagrangian relaxation [Geoffrion, 1974], Dantzig–Wolfe [Dantzig and Wolfe, 1960]).
Historically the modeler had to recognize the structure and rewrite the model
by hand. The Decomposition Advisor automates that: it analyzes a model,
discovers exploitable structure as a graph problem, scores candidate
decompositions, explains its recommendation, and produces a solvable reformulation
— a compiler-style transformation pass on the same footing as presolve. See the
design spec in docs/design/decomposition-advisor.md; for a broader survey of
Benders methods see Rahmaniani et al. [2017].
This notebook walks the advisor’s analysis surface end to end. It is pure analysis — no solve is triggered — so it runs without the compiled solver backend; running the chosen decomposition is covered in the Benders and Lagrangian tutorials.
import discopt.modeling as dm
from discopt.decomposition import RecordStore, analyze_decomposition, record_outcome
from discopt.decomposition.learning import ObservedPerformance, Outcome
A two-stage facility model#
Three candidate facilities: binary build[i] decides whether to open facility
i (first stage), continuous x[i] is its production (recourse). Production is
gated by the build decision, and a budget limits how many we open — the budget
row couples the binaries, so the model is not already block-diagonal. But
once the binaries are fixed, the recourse splits into three independent blocks:
the textbook Benders structure.
m = dm.Model("facility")
# Scalar variables so each facility is a distinct node in the structure graph.
b = [m.binary(f"b{i}") for i in range(3)] # first-stage: open i?
x = [m.continuous(f"x{i}", lb=0, ub=10) for i in range(3)] # recourse: production
for i in range(3):
m.subject_to(x[i] <= 10 * b[i]) # production gated by build
m.subject_to(b[0] + b[1] + b[2] <= 2) # budget couples the binaries
m.minimize((x[0] + x[1] + x[2]) - 3 * (b[0] + b[1] + b[2]))
print(m)
Model: facility
Variables: 6 (3 continuous, 3 integer/binary)
Constraints: 4
Objective: minimize (((x0 + x1) + x2) - (3 * ((b0 + b1) + b2)))
Parameters: 0
Analyze the structure#
model.analyze_decomposition() returns a DecompositionAdvisor. Its
StructureReport summarizes the exploitable structure in one pass — sizes,
integer localization (how many recourse blocks appear once the integers are
fixed), coupling density, and more.
adv = m.analyze_decomposition()
print(adv.structure().summary())
StructureReport
size: 6 vars, 4 cons, 9 incidences
blocks: 1 (block-diagonal=False)
integer: 3 (50%); projection blocks=3
coupling: 1 constraints (density=25.0%)
bridges: 1; articulation vars=3
nonlinear: False; annotated=False
elements: blocks=1; projection blocks=3; coupling=1
Candidate decompositions#
The advisor discovers candidate decompositions with a cheap-first cascade of
generators. Each candidate reuses the existing DecompositionStructure, so it
can drive the shipping solvers directly. The monolithic no-decomposition
baseline is always included.
for c in adv.candidates():
print("-", c.summary())
- No decomposition [proven_equivalent] — baseline
- Classical Benders [proven_equivalent, 3 blocks] — integer-variable projection
- Lagrangian relaxation [relaxation, 3 blocks] — bridge-constraint scan
Score and rank#
Scoring is method-aware and measured against the no-decomposition baseline (anchored at 0): a decomposition must beat solving the model as written. The score carries an analytic performance estimate (an Amdahl-style speedup capped by load balance) and a confidence. Unsound candidates are vetoed, not down-weighted.
for cand, sv in adv.scores():
print(f"{cand.method.label:22s} {sv.summary()}")
Classical Benders score=+1.52 (confidence 0.75) — ~2.0x speedup, 100% parallel efficiency over 3 blocks, ~11 iters [confidence 0.75]
Lagrangian relaxation score=+1.32 (confidence 0.54) — ~2.0x speedup, 100% parallel efficiency over 3 blocks, ~50 iters [confidence 0.60]
No decomposition score=+0.00 (confidence 1.00)
The recommendation, explained#
Every recommendation is explainable — the reasons are backed by the same metrics the scorer used, with concerns and the runner-up alternatives. The explanation renders as text, markdown, or JSON (the JSON feeds tooling / the LLM layer).
print(adv.explain())
Recommended: Classical Benders
────────────────────────────────────────
Why:
• Fixing 3 integer variable(s) disconnects the model into 3 recourse blocks.
evidence: integer_localization=1.0, components_after_projection=3
• Recourse subproblems are linear (Benders).
Estimated:
• ~2.0x speedup, 100% parallel efficiency over 3 blocks, ~11 iters [confidence 0.75]
Alternatives considered:
• Lagrangian relaxation (score +1.32) — feasible but relaxation; ranked lower
• No decomposition (score +0.00) — baseline (solve as written)
print(adv.explain("json"))
{
"recommendation": "benders",
"headline": "Recommended: Classical Benders",
"confidence": 0.75,
"reasons": [
{
"claim": "Fixing 3 integer variable(s) disconnects the model into 3 recourse blocks.",
"evidence": {
"integer_localization": 1.0,
"components_after_projection": 3
}
},
{
"claim": "Recourse subproblems are linear (Benders).",
"evidence": {}
}
],
"concerns": [],
"score": {
"num_blocks": 3.0,
"block_size_cv": 0.0,
"coupling_density": 0.25,
"parallel_efficiency": 1.0,
"estimated_speedup": 2.0,
"integer_localization": 1.0,
"expected_cut_strength": 0.9,
"est_communication_cost": 0.5,
"warm_start_potential": 1.0
},
"performance": {
"estimated_speedup": 2.0,
"parallel_efficiency": 1.0,
"num_blocks": 3,
"est_iterations": 11
},
"alternatives": [
{
"method": "lagrangian",
"aggregate": 1.325,
"reason": "feasible but relaxation; ranked lower"
},
{
"method": "none",
"aggregate": 0.0,
"reason": "baseline (solve as written)"
}
]
}
Counterfactuals: “why not method X?”#
The advisor also explains why a method was not chosen — including the missing structural precondition. Here the budget row couples the binaries, so the model is not already block-diagonal and an independent-block decomposition does not apply. (Lagrangian relaxation, by contrast, is a viable alternative — it appears as a runner-up above, since the budget row can be dualized.)
print(adv.explain(method="independent_blocks"))
Independent blocks was not applicable: the model is not already block-diagonal (removing no constraints, it stays connected)
Reformulate: build a solvable decomposition#
decompose() turns the recommended candidate into a DecomposedModel — a
master/subproblem partition with a soundness certificate and an
original-space variable mapping. Its solve() (not called here) dispatches to
the shipping Benders / GBD / Lagrangian drivers.
dcmp = adv.decompose()
print(dcmp.summary())
print()
print("variable roles:")
for name in ["b0", "b1", "b2", "x0", "x1", "x2"]:
print(f" {name}: {dcmp.var_map.role(name)}")
DecomposedModel: Classical Benders
Classical Benders: proven_equivalent — classical Benders reproduces the monolithic optimum for linear recourse
master (Classical Benders): 3 complicating vars, 1 coupling constraint(s)
3 subproblem block(s)
subproblem[0]: 1 vars, 0 cons
subproblem[1]: 1 vars, 0 cons
subproblem[2]: 1 vars, 0 cons
variable roles:
b0: master
b1: master
b2: master
x0: block0
x1: block1
x2: block2
Parallel execution plan#
The independent recourse blocks run on a pluggable communication backend
(sequential or thread pool today), ordered biggest-first to avoid stragglers. The
SchedulingGraph reports the load-balance speedup cap; map_subproblems runs a
per-block function and reduces results back into block order, so the answer is
deterministic regardless of backend. Here we map a trivial pure-Python function
(the block size) rather than a real solve.
print(dcmp.schedule().summary())
block_sizes = dcmp.map_subproblems(lambda sp: sp.size, backend="threads")
print("recourse block sizes (block order):", block_sizes)
SchedulingGraph: 3 blocks, total_cost=3, critical_path=1, ideal_speedup=3.00x, master=True
recourse block sizes (block order): [1, 1, 1]
Learn from experience#
Every solve can be recorded — the instance’s features, the chosen method, what
was predicted, and what was observed — so the advisor’s own error is
measurable and future recommendations can improve. Records persist as local JSON
lines; an InstanceBasedPolicy retrieves nearest past instances to bias
selection (deferring safely to the rule-based policy until enough data accrues).
store = RecordStore() # in-memory; pass a path to persist as JSONL
record_outcome(
adv,
store,
observed=ObservedPerformance(wall_clock_s=1.8, iterations=6),
outcome=Outcome.OPTIMAL,
timestamp=0.0,
)
rec = store.all()[0]
print("chosen :", rec.chosen)
print("predicted speedup:", rec.predicted_speedup)
print("features :", rec.features.to_dict())
chosen : benders
predicted speedup: 2.0
features : {'num_vars': 6, 'num_constraints': 4, 'num_incidences': 9, 'integer_fraction': 0.5, 'coupling_density': 0.25, 'num_blocks': 1, 'blocks_after_integer_projection': 3, 'nonlinear': False}
Structure the array view cannot see#
The analysis above treats each array variable as one vertex of the
variable–constraint graph. That is cheap, but it hides structure that lives
inside arrays: if every scenario’s recourse is stored in one array x[s, t],
the array view sees a single block, even when fixing the first-stage decisions
splits the model per scenario.
The advisor therefore also reads the model one level down, with one vertex per
scalar column and per constraint row (discopt.decomposition.graph.element),
taken from the model’s own evaluator. Each vertex keeps its array name and index,
which is what index coarsening needs: merging the elements of an array along
chosen axes (“over time, keep the scenarios”) gives a small graph in which the
decomposable structure stays visible [Allen and Westerberg, 1976, Kalamaris and Maravelias, 2026].
The report records both views, and candidates that only the element view finds
carry an element_view.
S, T = 3, 4
ts = dm.Model("shared_array_two_stage")
build = ts.binary("build", shape=(S,)) # first stage
x = ts.continuous("x", shape=(S, T), lb=0, ub=10) # ONE array for all scenarios
for s in range(S):
for t in range(T):
ts.subject_to(x[s, t] <= 10 * build[s])
ts.subject_to(dm.sum(x[s, :]) >= 3 + s)
ts.subject_to(dm.sum(build) <= S)
ts.minimize(5 * dm.sum(build) + dm.sum(x))
adv_ts = ts.analyze_decomposition()
print(adv_ts.structure().summary())
pick = next(r.candidate for r in adv_ts.ranked() if r.recommended)
print("\nrecommended:", pick.summary())
print("subproblem 1 holds:", adv_ts.decompose().subproblems[1].variables)
StructureReport
size: 2 vars, 16 cons, 28 incidences
blocks: 1 (block-diagonal=False)
integer: 1 (50%); projection blocks=1
coupling: 0 constraints (density=0.0%)
bridges: 0; articulation vars=0
nonlinear: False; annotated=False
elements: blocks=1; projection blocks=3; coupling=1 (array level hides blocks)
recommended: Classical Benders [proven_equivalent, 3 blocks] — integer-variable projection (element level)
subproblem 1 holds: ('x[1, 0]', 'x[1, 1]', 'x[1, 2]', 'x[1, 3]')
Choosing the complicating variables: find_separators#
When neither the integers nor a single coupling constraint split a model,
Kalamaris and Maravelias [2026] choose the complicating features directly: an
integer program over a (coarsened) graph that picks a vertex set \(R\) so that the
rest falls into at least \(|C|\) balanced components, trading component imbalance
against \(\epsilon\,|R|\). find_separators implements that program. Every
separator it returns is lifted back to the original columns and its split is
re-measured, so a sub-optimal answer costs speed, never correctness; a variable
separator can be used as a Benders first stage through
DecompositionStructure.master_columns.
It is a tool you call yourself, not something the advisor runs: measured on two-stage stochastic LPs, the decompositions it found were slower than solving the model as written, so the advisor’s use of it was retired (design spec §4.1 records the measurements). Unlike the rest of this notebook, the cell below solves: the partitioning program and a Benders run need the compiled solver backend.
import dataclasses
import numpy as np
from discopt.decomposition import solve_benders
from discopt.decomposition.graph.element import ElementGraph
from discopt.decomposition.graph.separator import find_separators
from discopt.decomposition.structure import detect_decomposition
def capacity_expansion(G=2, P=2, S=3, T=4, seed=0):
"""Design capacities K[g,p], L[p] shared by S scenarios of operations."""
rng = np.random.default_rng(seed)
alpha = rng.uniform(0.6, 1.0, size=(G, P, T))
demand = rng.uniform(2, 6, size=(P, S, T)) * (1 + 0.3 * np.arange(S))[None, :, None]
m = dm.Model("capacity_expansion")
K = m.continuous("K", shape=(G, P), lb=0, ub=20)
L = m.continuous("L", shape=(P,), lb=0, ub=20)
Q = m.continuous("Q", shape=(G, P, S, T), lb=0, ub=40)
I = m.continuous("I", shape=(P, S, T), lb=0, ub=40)
U = m.continuous("U", shape=(P, S, T), lb=0, ub=200)
for p in range(P):
for s in range(S):
for t in range(T):
prev = (I[p - 1, s, T - 1] if p > 0 else 1.0) if t == 0 else I[p, s, t - 1]
m.subject_to(prev - I[p, s, t] + Q[0, p, s, t] + Q[1, p, s, t] + U[p, s, t]
== float(demand[p, s, t]))
for g in range(G):
m.subject_to(Q[g, p, s, t] <= float(alpha[g, p, t]) * K[g, p])
m.subject_to(I[p, s, t] <= L[p])
m.minimize(3 * dm.sum(K) + dm.sum(L) + (0.2 * dm.sum(Q) + 5 * dm.sum(U)) / S)
return m
g = ElementGraph.from_model(capacity_expansion())
# Index coarsening: merge Q over generators and time, I and U over time.
coarse = g.coarsen({"Q": (0, 3), "I": (2,), "U": (2,)})
seps = find_separators(g, "variables", max_components=3, skip_covered=False, coarse=coarse)
for sep in seps:
print(f"|C|={sep.num_components}: {sep.weight} columns -> {sep.blocks} blocks",
[g.col_label(j) for j in sep.columns][:6])
design = next(s for s in seps if {g.var_names[int(g.col_var[j])] for j in s.columns} == {"K", "L"})
m = capacity_expansion()
st = dataclasses.replace(detect_decomposition(m), complicating_vars=["K", "L"],
master_columns=design.columns)
benders = solve_benders(m, structure=st)
mono = capacity_expansion().solve()
print(f"\nBenders over the design columns: {benders.status}, {benders.objective:.6f}")
print(f"monolithic solve: {mono.status}, {mono.objective:.6f}")
Running HiGHS 1.16.0 (git hash: f3f113d): Copyright (c) 2026 under MIT licence terms
Includes third-party software components, see THIRD_PARTY_NOTICES.md for full details
Benders iteration 6 added no separating cut (degenerate or missing duals); stall=1.
|C|=2: 10 columns -> 7 blocks ['K[0, 0]', 'K[0, 1]', 'K[1, 0]', 'K[1, 1]', 'L[0]', 'L[1]']
|C|=3: 6 columns -> 3 blocks ['K[0, 0]', 'K[0, 1]', 'K[1, 0]', 'K[1, 1]', 'L[0]', 'L[1]']
Benders over the design columns: optimal, 70.130032
monolithic solve: optimal, 70.130032
Summary#
The advisor took a model and, without any manual rewriting, discovered its
two-stage structure, scored the candidates against the no-decomposition baseline,
recommended Benders with an evidence-backed rationale, and produced a
solvable DecomposedModel with a soundness certificate and a parallel execution
plan — then recorded the outcome for future learning.
Future directions (design spec §14) include automatic hypergraph partitioning for block-angular models [Karypis and Kumar, 1998], learned decomposition policies, and graph-neural-network structure prediction.