Interactive Branch-and-Bound Debugger

Interactive Branch-and-Bound Debugger#

discopt ships an interactive debugger for its branch-and-bound search: a “pdb for B&B”. It pauses a solve at well-defined node-lifecycle checkpoints, lets you inspect the tree, incumbent, bounds, and per-node relaxations, set breakpoints (by iteration, by condition, or on solver events), and safely steer the search. It drives the same batch B&B loops that power discopt’s spatial-McCormick search for nonconvex MINLP [Belotti et al., 2009, McCormick, 1976] and its LP/NLP-based integer searches in the tradition of Land and Doig [1960] and Dakin [1965].

Two design rules shape everything below:

  1. Zero effect when detached. Every fire-site in the solver is a single None check, so a solve without a debugger attached is bit-for-bit identical to one built without the debugger at all. This is enforced by exact-equality regression tests (identical node counts and objectives).

  2. The certificate is untouchable. A global solver’s product is its optimality certificate. Steering can reorder work (branching hints) or offer validated incumbents, but no debugger action can loosen a bound, fabricate an incumbent, or turn a correct verdict into an incorrect one.

There are three ways in:

Entry point

Use case

m.solve(debug=True) or debug="repl"

human REPL on a TTY

m.solve(debug="on-error")

enter only when the solve fails to certify

m.solve(debug="json") / JsonFrontend

newline-delimited JSON protocol for agents, scripts, GUIs

 
import discopt as do
from discopt import debug

A model worth debugging#

A small nonconvex MINLP (a bilinear constraint plus a transcendental equality) that routes to the spatial-McCormick branch-and-bound loop and needs a handful of iterations to certify.

def make_model():
    m = do.Model("debug_demo")
    x = m.continuous("x", lb=0.1, ub=4.0)
    y = m.continuous("y", lb=0.1, ub=4.0)
    z = m.integer("z", lb=0, ub=3)
    m.subject_to(x * y + z >= 3.0)
    m.subject_to(y == do.exp(x) - 1.0)
    m.minimize(x + 0.5 * y + 0.3 * z)
    return m


baseline = make_model().solve(time_limit=30.0)
print(baseline.status, baseline.objective)

optimal 1.0525854590378239

Scripted REPL sessions#

On a TTY, m.solve(debug=True) drops you into the REPL at the first pause. In a notebook (or a test) there is no TTY, so we feed the same REPL a script of commands. The session pauses at the first checkpoint, executes commands until a resume verb, and detaches automatically when the script is exhausted. REPL output goes to stderr.

The command language in one screen: flow control (step, stepi, continue, run N, stop-at <checkpoint>, detach, quit), breakpoints (break N, tbreak N, break if <metric op value [&& ...]>, break on <event>), inspection (info, print incumbent|bound|gap|stats|nodes|node <i>|relax <i>|created, watch <target>), and steering (inject <i>, hint <node_id> <var>).

print node <i> and print nodes also show where each node sits in the search tree: its parent, depth and the branch that created it (x <= 0.5, or root), and print created at after_process lists every child the batch made, including those pruned before they were ever selected, with the status each one closed in.

script = [
    "help",
    "info",
    "break if gap<0.5 && nodes>=2",   # conditional breakpoint (AND-only)
    "continue",
    "print bound",
    "print nodes",
    "continue",
]
debug.attach(debug.make_session(script=script))
try:
    res = make_model().solve(time_limit=30.0)
finally:
    debug.detach()
print(res.status, res.objective)

discopt debugger — 'help' for commands, 'c' to continue

── paused at iter_start  (step)  iter=0 nodes=1 incumbent=none bound=1.04943

(discopt-dbg) help

flow:   step(s/n) stepi(si) continue(c) run N stop-at <cp> detach quit(q)

breaks: break N | tbreak N | break if <m op v [&& ...]> | break on <event>

        break (list) | break del N | break clear [cond|events]

watch:  watch <target> | watch | watch clear

look:   info(i) | print(p) incumbent|bound|gap|stats|nodes|node <i>|relax <i>

steer:  inject <i>   (validate relax sol of batch node i; adopt if feasible)

        hint <node_id> <var>

metrics: bound, elapsed, gap, incumbent, iter, nodes, open

checkpoints: iter_start, after_select, before_import, after_process, incumbent_found, terminated

(discopt-dbg) info

[iter_start] iter=0 nodes=1 open=1 incumbent=none bound=1.04943 gap=none t=0.01s

(discopt-dbg) break if gap<0.5 && nodes>=2

break if gap<0.5 && nodes>=2

(discopt-dbg) continue

── paused at iter_start  (condition: gap<0.5 && nodes>=2)  iter=1 nodes=3 incumbent=1.05259 bound=1.04943

(discopt-dbg) print bound

bound = 1.04943

(discopt-dbg) print nodes

no batch live at this checkpoint

(discopt-dbg) continue

── paused at terminated  (stop-at terminated)  iter=2 nodes=5 incumbent=1.05259 bound=1.05259

detached; solve runs to completion

optimal 1.0525854590378239

Checkpoints#

Checkpoints mirror the lifecycle of one batch iteration of the B&B loop. Every name below has at least one live fire-site; the JSON handshake never advertises a pause point that cannot fire.

Checkpoint

Fires

iter_start

top of a batch iteration

after_select

open-node boxes/ids exported from the tree

before_import

relaxations solved, results not yet imported — the steer point

after_process

prune/branch/fathom applied by the tree

incumbent_found

event: a strictly better incumbent was adopted

terminated

once, after the search ends (with the final status)

step resumes to the next iter_start; stepi to the next checkpoint of any kind; stop-at <name> adds a checkpoint to the always-pause set (aliases: start, select, steer, import, process, branch, incumbent, end).

For programmatic control you can skip the REPL entirely and hand the session a custom frontend: any object with an interact(ctx, session) method. The context exposes the aggregate tree state (node_count, open_nodes, incumbent_obj, best_bound, gap) plus, at batch checkpoints, the per-node boxes and relaxation results.

from discopt.debug.engine import Control
from discopt.debug.session import DebugSession


class TraceFrontend:
    """Walk every checkpoint and record the certificate state at each pause."""

    def __init__(self):
        self.trace = []

    def interact(self, ctx, session):
        self.trace.append((ctx.checkpoint.value, ctx.iteration, ctx.best_bound, ctx.incumbent_obj))
        return Control.CONTINUE if ctx.checkpoint.value == "terminated" else Control.STEPI


fe = TraceFrontend()
debug.attach(DebugSession(fe))
try:
    res = make_model().solve(time_limit=30.0)
finally:
    debug.detach()

for cp, it, bound, inc in fe.trace[:8]:
    print(f"iter {it:2d}  {cp:16s} bound={bound:9.5f}  incumbent={inc}")
print(f"... {len(fe.trace)} checkpoints total; final status: {res.status}")

iter  0  iter_start       bound=  1.04943  incumbent=None
iter  0  after_select     bound=  1.04943  incumbent=None
iter  0  before_import    bound=  1.04943  incumbent=1.0525854610331147
iter  0  after_process    bound=  1.04943  incumbent=1.0525854610331147
iter  0  incumbent_found  bound=  1.04943  incumbent=1.0525854610331147
iter  1  iter_start       bound=  1.04943  incumbent=1.0525854610331147
iter  1  after_select     bound=  1.04943  incumbent=1.0525854610331147
iter  1  before_import    bound=  1.04943  incumbent=1.0525854590378239
... 11 checkpoints total; final status: optimal

The trace shows the two halves of the certificate converging: the dual bound only ever rises and the incumbent only ever falls, at every checkpoint, until they meet. That invariant is part of the debugger’s adversarial test suite.

Safe steering#

At the before_import steer point you can influence the search — within strict limits:

  • inject <i> offers batch node i’s relaxation solution as a candidate incumbent. The point is first validated against the original problem with the solver’s own machinery (integrality check and snap, constraint feasibility, true-objective evaluation), exactly like the solver’s internal primal heuristics [Berthold, 2006]. Only a feasible point with its evaluated objective is offered to the tree, which additionally requires strict improvement. An infeasible point is rejected; on solve paths that wire no validator, inject refuses outright rather than trust the caller.

  • hint <node_id> <var> suggests the branching variable for a node — reordering only, in the spirit of branching-rule engineering [Achterberg et al., 2005]. A hint can never prune a region, and hostile hints (unknown nodes, out-of-range variables) are ignored by the tree.

Arbitrary edits of node boxes or bounds are deliberately not offered.

steer_script = [
    "stop-at steer",
    "continue",
    "print relax 0",
    "inject 0",       # validated: adopted only if genuinely feasible + improving
    "hint 999999 0",  # hostile hint: harmless, ignored by the tree
    "continue",
]
debug.attach(debug.make_session(script=steer_script))
try:
    res = make_model().solve(time_limit=30.0)
finally:
    debug.detach()
print(res.status, res.objective)
assert abs(res.objective - baseline.objective) < 1e-6  # certificate unchanged

discopt debugger — 'help' for commands, 'c' to continue

── paused at iter_start  (step)  iter=0 nodes=1 incumbent=none bound=1.04943

(discopt-dbg) stop-at steer

will stop at before_import

(discopt-dbg) continue

── paused at before_import  (stop-at before_import)  iter=0 nodes=1 incumbent=1.05259 bound=1.04943

(discopt-dbg) print relax 0

relax[0] bound=1.04943 feasible=False

  x = [0.1    0.1052 2.9895]

(discopt-dbg) inject 0

inject node[0]: rejected: infeasible for the original problem

(discopt-dbg) hint 999999 0

branch hint: node 999999 -> var 0

(discopt-dbg) continue

── paused at before_import  (stop-at before_import)  iter=1 nodes=3 incumbent=1.05259 bound=1.04943

detached; solve runs to completion

optimal 1.0525854590378239

on-error: a post-mortem debugger#

debug="on-error" stays silent unless the solve terminates without a certified optimum (a limit was hit, the search was interrupted, the outcome is unknown, or infeasibility was certified). It then pauses exactly once, at terminated, with the final status as the reason — useful as an always-on safety net in long experiments.

# A zero time limit forces a failed termination deterministically.
debug.attach(debug.make_session("on-error", script=["info", "continue"]))
try:
    res = make_model().solve(time_limit=0.0)
finally:
    debug.detach()
print(res.status)

discopt debugger — 'help' for commands, 'c' to continue

── paused at terminated  (on-error: time_limit)  iter=0 nodes=0 incumbent=none bound=-inf

(discopt-dbg) info

[terminated] iter=0 nodes=0 open=0 incumbent=none bound=-inf gap=none t=0.00s

(discopt-dbg) continue

No valid dual bound was produced for model 'debug_demo': the relaxation layer could not bound this objective (status=time_limit). The result cannot be certified globally optimal. A nonlinear term with no envelope is the usual cause; an epigraph reformulation (minimize z subject to f(x) <= z) often gives the relaxation something to bound.

time_limit

The JSON protocol for agents#

The second frontend speaks newline-delimited JSON and shares the same command engine as the REPL, so an LLM agent, script, or GUI gets identical semantics. The first output is a hello handshake advertising every checkpoint, event, command, metric, and capability — clients feature-detect from it and need no out-of-band docs. Each command yields a result event echoing the request id, with ok: false when the command failed (unknown verb, raised, or unavailable at this checkpoint). Non-finite floats are coerced to null so the stream is always strict JSON.

A pause event also carries batch (the batch’s ids, parent, depth, branch_var, branch_side, branch_value and status) wherever the route reports lineage, and created in the same layout at after_process, so an agent can follow the tree without issuing one print node per node. The handshake advertises both (pause_batch_lineage, pause_created).

import json

from discopt.debug.jsonproto import JsonFrontend

commands = iter(
    [
        json.dumps({"cmd": "info", "id": 1}),
        json.dumps({"cmd": "break if nodes>=2", "id": 2}),
        "continue",
        json.dumps({"cmd": "print", "args": ["bound"], "id": 3}),
        "continue",
        "continue",
    ]
)
events = []
fe = JsonFrontend(read_fn=lambda: next(commands, None), write_fn=events.append)
debug.attach(DebugSession(fe))
try:
    res = make_model().solve(time_limit=30.0)
finally:
    debug.detach()

print("handshake capabilities:", json.dumps(events[0]["capabilities"], indent=2))
for e in events[1:]:
    if e["event"] == "result":
        print(f"result id={e['request_id']} ok={e['ok']}: {e['output'][:1]}")
    else:
        print(f"{e['event']:11s} checkpoint={e.get('checkpoint')} bound={e.get('bound')}")

handshake capabilities: {
  "inspect": true,
  "safe_steer": true,
  "mutate_iterate": false,
  "conditional_breakpoints": "compound_and",
  "event_breakpoints": true,
  "request_ids": true,
  "rewind": false,
  "resolve": false,
  "progress_events": false,
  "terminal_checkpoint": true
}
pause       checkpoint=iter_start bound=1.0494303314955056
result id=1 ok=True: ['[iter_start] iter=0 nodes=1 open=1 incumbent=none bound=1.04943 gap=none t=0.01s']
result id=2 ok=True: ['break if nodes>=2']
result id=None ok=True: []
pause       checkpoint=iter_start bound=1.0494303314955056
result id=3 ok=True: ['bound = 1.04943']
result id=None ok=True: []
terminated  checkpoint=terminated bound=1.0525854590378123
result id=None ok=True: []

The pure-Rust MILP fast-path#

Pure MILPs can route to a search loop that runs entirely inside the Rust extension. The same debugger drives it through a checkpoint hook across the PyO3 boundary, with two differences: only the aggregate checkpoints fire (iter_start, after_process, incumbent_found, terminated — no per-node batch arrays), and steering is unavailable (inspection and flow control only, including quit). When no debugger is attached, no hook is installed and the Rust search runs its untouched, bound-neutral path.

def knapsack():
    m = do.Model("dbg_milp")
    xs = [m.integer(f"x{i}", lb=0, ub=1) for i in range(10)]
    vals = [8, 5, 3, 6, 4, 7, 9, 2, 5, 6]
    wts = [5, 3, 2, 4, 3, 5, 6, 1, 2, 4]
    m.subject_to(sum(w * xi for w, xi in zip(wts, xs)) <= 14)
    m.maximize(sum(v * xi for v, xi in zip(vals, xs)))
    return m


fe = TraceFrontend()
debug.attach(DebugSession(fe))
try:
    res = knapsack().solve(time_limit=15.0, nlp_solver="simplex")
finally:
    debug.detach()
print(sorted({cp for cp, *_ in fe.trace}))
print(res.status, res.objective)

['after_process', 'after_select', 'incumbent_found', 'iter_start', 'terminated']
optimal 24.0

Guarantees and caveats#

  • Bound-neutral when detached (and under pure inspection): attaching a no-op debugger, or stepping through every checkpoint with read-only commands, leaves the node count and certified objective exactly unchanged.

  • Certificate-safe steering: inject validates against the original problem before the tree sees a point; quit produces a valid, uncertified partial result (unknown when nothing was proven — never a false optimal or infeasible), and no fallback engine silently resumes a solve you stopped.

  • Thread-local: debug.attach() affects only solves started on the attaching thread, so concurrent solves can each carry their own debugger.

  • Outermost solve only: the solver runs nested solve_model calls internally (restricted sub-MINLP heuristics, warm starts); those never fire checkpoints into your session.

  • Not instrumented: purely continuous NLPs route around the B&B loops entirely, so an attached debugger simply never fires there. on-error does not trigger on the pure-Rust MILP fast-path (its hook carries no final status).

  • Ctrl-C at a REPL prompt resumes the solve; Ctrl-C while a JSON frontend is blocked on input aborts the solve and re-raises KeyboardInterrupt, on the Rust path included.