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.