discopt

discopt#

discopt logo

A Mixed-Integer Nonlinear Programming (MINLP) solver built on a Rust core with Python orchestration. Solves MINLPs by spatial Branch & Bound [Belotti et al., 2013, Land and Doig, 1960] over rigorous convex relaxations, with an in-house primal/dual simplex for the per-node LPs and a Rust automatic-differentiation tape for objective/gradient/Jacobian/Hessian evaluation.

Architecture#

Model.solve()  -->  Python orchestrator  -->  Rust B&B kernel / TreeManager
                        |                          |
                  NLP evaluation:            Node pool / branching / pruning
                    POUNCE AD tape           In-house primal/dual simplex (node LPs)
                    (default, JAX-free)      Zero-copy numpy arrays (PyO3)
                  NLP backends:
                    pounce  (pure-Rust Ipopt port)  [default]
                    cyipopt (Ipopt)                 [fallback]

Rust backend (crates/discopt-core): Expression IR, Branch & Bound tree (node pool, branching, pruning), the native spatial B&B kernel, in-house primal/dual simplex with a sparse LU basis (feral), .nl file parser, FBBT/presolve (interval arithmetic, probing, Big-M simplification).

NLP evaluation (python/discopt/_tape_nlp_evaluator.py, _nl_expr_compiler.py): objective, gradient, constraints, Jacobian, and Lagrangian Hessian (dense and sparse) from a POUNCE Rust AD tape, with no JAX on the path. Expressions with no tape opcode fall back to the JAX evaluator, and DISCOPT_NLP_EVAL=jax selects it wholesale. A tape-representable solve does not import JAX – not on the LP, QP, MIQP and simplex-MILP paths, and not on the nonlinear ones either (measured over eight nonlinear corpus instances: zero jax modules in sys.modules after each solve). Those eight are all tape-representable, so they do not license the unconditional claim: the fallback lives on the default path, and a plain Model.solve() of a dm.external nested inside another one’s argument, with no caller-side import jax, takes sys.modules from 0 to 222 jax entries. (dm.norm(X, 2) of a matrix used to be the example; since #1903 the spectral norm and dm.external are numpy-evaluated holes in the tape and import no JAX.) JAX is the optional discopt[jax] extra (#1873): without it that model refuses with an ImportError naming the construct the tape has no opcode for and the extra, and every other JAX-only feature refuses the same way.

Relaxation layer (python/discopt/_relax): DAG compiler, the uniform factorable relaxation engine, the LP-form McCormick relaxation [McCormick, 1976] with a univariate envelope table (sigmoid, softplus, tanh, …), alphaBB, and cutting planes. The default uniform factorable engine is numpy, not JAX: a nonconvex MINLP whose expressions are tape-representable does not import JAX when solved through Model.solve() (measured — "jax" in sys.modules is False after a spatial-B&B solve to certified optimality). 16 of the 75 top-level modules in this directory import JAX, 12 of them at module scope (measured after #1873 retired the McCormick-NLP route and 22 JAX modules with it; it was 41 of 85 before), and they are off the default path, with one exception that matters: _relax/nlp_evaluator is the legacy JAX evaluator the tape falls back to, so a model with no tape opcode reaches it from an ordinary Model.solve(). The directory was named _jax before the removal, so its name is not a guide to what it runs on. dm.register_function(name, lower) lets a caller declare a named univariate composite the engine envelopes as a single atom instead of relaxing its expansion term by term — the route a plugin uses to hand the relaxer structure that generic factorable reformulation would throw away.

Solver wrappers (python/discopt/solvers): POUNCE (pure-Rust Ipopt port) for LP/QP/NLP, the in-house simplex LP/MILP backends, cyipopt for Ipopt [Wächter and Biegler, 2006], AMP, the MIP-NLP decomposition family, GDPopt-LOA, the derivative-free backends, and an optional Gurobi backend. highspy is used only on the OA/GDP paths.

ML model embedding (python/discopt/ml): embeds trained ML predictors as algebraic MINLP constraints [Ceccon et al., 2022] — feedforward networks via full-space (smooth activations), ReLU big-M MILP [Anderson et al., 2020], and reduced-space strategies, and decision trees/ensembles via a per-leaf MILP encoding [Mišić, 2020]; interval arithmetic bound propagation; ONNX, scikit-learn and PyTorch model import. (Imported as discopt.nn before 0.9.0; that name still works as a deprecated alias.)

Generalized disjunctive programming (python/discopt/_relax/gdp_reformulate.py): reformulates GDP models — BooleanVar, propositional logic operators, either_or(), if_then() — into standard MINLP via big-M, multiple big-M (LP-tightened), convex hull, or Logic-based Outer Approximation.

Piecewise-linear functions (python/discopt/modeling/_piecewise.py): Model.piecewise(x, breakpoints, values) declares a tabulated univariate function and lowers it, at declaration, to an exact MILP encoding — incremental [Markowitz and Manne, 1957], logarithmic [Vielma and Nemhauser, 2011], disaggregated convex combination, or a native SOS2 set [Beale and Tomlin, 1970] — following Vielma et al. [2010]. Because the table is the function, the model solved is the model declared and the certificate carries over; an input whose domain escapes the breakpoint span is refused, not clamped. Its approximating counterpart, dm.nonlinear_to_pwl(model) (python/discopt/modeling/_pwl_transform.py), replaces univariate nonlinear terms by piecewise-linear constructs: mode="outer" builds a rigorous outer approximation (interval-arithmetic error bands with interval-AD mean-value tapers), so its bound is valid for the original model and a certificate requires a verified incumbent to meet it, with adaptive partition refinement [Misener et al., 2011, Nagarajan et al., 2019]; mode="approximate" never claims a bound. See Piecewise-Linear Functions.

Modeling surface (python/discopt/modeling): the expression DAG, plus the blocks that let one model stand inside another. dm.argmin(inner, ...) embeds an inner NLP as a block of an outer model — its forward pass is a POUNCE solve and its derivatives are sIPOPT KKT sensitivities — with dm.argmin_kkt as the lowered arm of the same block. Model.mcp(F, z, lb=..., ub=...) declares the box-bounded mixed-complementarity relation (represented, and deliberately refused by solve rather than lowered through a two-branch encoding; see Complementarity semantics — the source contract). dm.solve_batch(models, workers=8) runs many small independent global solves and returns one SolveResult per model in input order. Saved .dopt models and result files carry FAIR provenance and a validation report.

Orchestrator (python/discopt/solver.py): End-to-end Model.solve() connecting all components. At each B&B node: solve continuous NLP relaxation with the interior-point method [Nocedal and Wright, 2006], prune infeasible nodes, fathom integer-feasible solutions, branch on most fractional variable. solve(warm_start=prev) now reuses the dual side as well as the primal point: on the single-NLP routes whose backend reports them, SolveResult.kkt carries the terminal KKT residuals (scaled and _unscaled) and the interior-point barrier_parameter that seeds the next solve; it is None on every branch-and-bound route.

Certified-global MINLP via AMP (python/discopt/solvers/amp.py): Adaptive Multivariate Partitioning [Nagarajan et al., 2019] for nonconvex MINLPs (bilinear, signomial, concave). Iterates a piecewise-McCormick / convex-hull MILP relaxation against an NLP subproblem (Ipopt), refining the partition where the relaxation gap is largest. At every iteration LB_k <= global_opt <= UB_k, so termination yields a certified suboptimality bound. Invoked with Model.solve(solver="amp"); see Certified-global MINLP with AMP.

Parameter estimation (python/discopt/estimate.py): Model-based parameter estimation via weighted least-squares NLP with exact sensitivity Jacobians via JAX autodiff (no finite differences), Fisher-Information-based covariance, and confidence intervals [Franceschini and Macchietto, 2008]. Optimal design of experiments (FIM-based D/A/E-optimal design, sequential DoE, identifiability analysis) lives in the standalone discopt-doe plugin, which shares the same Experiment interface.

Try it without installing anything#

discopt runs in the browser — the whole solver, compiled to WebAssembly, with an editor and a console. See Run discopt in your browser, or go straight to the solver page:

→ Open the in-browser solver

Quick Start#

from discopt import Model

m = Model("example")
x = m.continuous("x", lb=0, ub=5)
y = m.continuous("y", lb=0, ub=5)
z = m.binary("z")

m.minimize(x**2 + y**2 + z)
m.subject_to(x + y >= 1)
m.subject_to(x**2 + y <= 3)

result = m.solve()
print(result.status)     # "optimal"
print(result.objective)  # 0.5
print(result.x)          # {"x": 0.5, "y": 0.5, "z": 0.0}

Parameter Estimation#

discopt includes model-based parameter estimation using exact JAX autodiff for Fisher Information Matrix computation. (Optimal experimental design on the same Experiment interface is provided by the discopt-doe plugin: pip install discopt-doe.)

from discopt.estimate import Experiment, ExperimentModel, estimate_parameters
import discopt.modeling as dm
import numpy as np

# Define an experiment: y = k * x
class MyExperiment(Experiment):
    def create_model(self, **kwargs):
        m = dm.Model("exp")
        k = m.continuous("k", lb=0.01, ub=20)
        x = m.continuous("x", lb=0.1, ub=10)
        return ExperimentModel(
            model=m,
            unknown_parameters={"k": k},
            design_inputs={"x": x},
            responses={"y": k * x},
            measurement_error={"y": 0.1},
        )

# Estimate k from data
exp = MyExperiment()
data = {"y": 6.0}  # observed at some x
result = estimate_parameters(exp, data)
print(result.parameters)  # {"k": ...}
print(result.confidence_intervals)

NLP Backend Comparison#

Model.solve() accepts these nlp_solver selectors:

Backend

Implementation

Use Case

pounce (default)

Pure-Rust Ipopt port

Universal default: LP/QP/MILP/MIQP/NLP/MINLP

ipopt / cyipopt

Ipopt via cyipopt

NLP node and continuous solves; most robust

simplex

Pure-Rust warm-started simplex B&B

MILP; the fully JAX-free MILP path

ipm / sparse_ipm

Back-compat aliases

Simplex-first LP/MILP routing; resolve to POUNCE for NLP/MINLP

The pure-JAX interior-point method has been retired. nlp_solver="ipm" is kept as an alias so existing scripts keep working: it selects the simplex-first matrix routing for LP/MILP and resolves to POUNCE for NLP/MINLP. See NLP Backend Comparison: POUNCE vs Ipopt for a measured comparison.

result = model.solve()                       # default: POUNCE
result = model.solve(nlp_solver="pounce")    # POUNCE (pure-Rust Ipopt port)
result = model.solve(nlp_solver="ipopt")     # Ipopt via cyipopt
result = model.solve(nlp_solver="simplex")   # pure-Rust simplex MILP B&B

Contents#

Tutorials — Problem Classes

Tutorials — Solver Backends

Tutorials

Advanced Features

Solver Backends

Applications

API Reference

Appendix