discopt.tightening

discopt.tightening#

Public bound-tightening utilities (feasibility-based / row-activity).

discopt’s solver already runs a sophisticated bound-tightening stack during presolve and at the root node — feasibility-based bound tightening (FBBT, iterated to a fixpoint), implied row-activity propagation, duality-based tightening (DBBT), and optimization-based bound tightening (OBBT) over the McCormick relaxation. This module exposes the sound, LP-free core of that stack — FBBT — as a small public API for analysis and for building custom workflows (e.g. conflict detection).

FBBT propagates the row activity of each constraint under the current variable bounds: for a constraint g(x) ⋈ rhs it computes the interval the body can take, then isolates each variable to derive an implied bound, iterating across constraints until a fixpoint. It only ever derives valid bounds, so the tightened box always contains the entire feasible region — it never removes a feasible point, and in particular never excludes the optimum. If propagation produces an empty interval, the (sub)problem is proven infeasible.

Classes#

BoundTightening

Result of an FBBT bound-tightening pass.

Functions#

fbbt_box(→ BoundTightening)

Tighten model's variable bounds with feasibility-based bound tightening.

probe_box(→ BoundTightening)

Tighten model's bounds with FBBT plus per-node probing (P3).

Module Contents#

class discopt.tightening.BoundTightening#

Result of an FBBT bound-tightening pass.

Variables:

  • ub (lb,) – Tightened flat (per-scalar) variable bounds. Always a subset of the input box (each bound intersected, never loosened).

  • infeasible (bool) – True if propagation derived an empty interval for some variable, which proves the problem infeasible.

  • n_tightened (int) – Number of scalar variables whose lower or upper bound was strictly improved.

lb: numpy.ndarray#
ub: numpy.ndarray#
infeasible: bool#
n_tightened: int#
discopt.tightening.fbbt_box(model: discopt.modeling.core.Model, *, max_iter: int = 20, tol: float = 1e-09, repr_: Any = None) → BoundTightening#

Tighten model’s variable bounds with feasibility-based bound tightening.

Runs FBBT (iterated to a fixpoint, up to max_iter sweeps) over the model’s constraints and returns the tightened flat bounds. The per-block bounds from the Rust FBBT engine are expanded to per-scalar bounds and intersected with the model’s current bounds, so the result is always a sound subset of the input box. A model with array variables is also propagated per element (#1752), so x[0] <= 2 tightens x[0] alone.

Parameters:

  • model (Model) – The model whose bounds to tighten.

  • max_iter (int) – Maximum FBBT sweeps (cross-constraint propagation reaches a fixpoint when a sweep changes nothing).

  • tol (float) – Numerical tolerance for empty-interval (infeasibility) detection.

  • repr (ModelRepr, optional) – A model_to_repr result for model the caller already built; built here when omitted.

Return type:

BoundTightening

discopt.tightening.probe_box(model: discopt.modeling.core.Model, *, max_iter: int = 8, tol: float = 1e-09, max_vars: int = 64, incumbent: float | None = None) → BoundTightening#

Tighten model’s bounds with FBBT plus per-node probing (P3).

This is the sound, LP-free branch-and-reduce reduction: after an FBBT sweep, each discrete variable is tentatively fixed at a bound and FBBT is re-run; a proven-infeasible fixing contracts the domain (binaries are forced to the surviving value, integer endpoints are peeled). It is strictly at least as tight as fbbt_box() and, like it, only ever derives valid bounds — the returned box always contains the entire feasible region, so it never removes a feasible point and in particular never excludes the optimum. An empty interval proves the (sub)problem infeasible.

Parameters:

  • model (Model) – The model whose bounds to tighten.

  • max_iter (int) – FBBT inner-loop iteration cap (used both for the outer sweep and for the per-fixing FBBT solves inside probing).

  • tol (float) – Numerical tolerance for tightening / empty-interval detection.

  • max_vars (int) – Budget: at most this many discrete variables are probed.

  • incumbent (float, optional) – A valid incumbent objective, in the model’s own objective sense (the value of f at a feasible point, positive-as-written for a MAXIMIZE model – NOT the internal -f). The Rust kernel builds the cutoff row against the repr’s objective under the repr’s declared sense, so it reads this value in the model’s space; passing an internally-negated value to a maximize model prunes the wrong half and can cut off the optimum (#1373). When given, probing becomes optimality-aware via a cutoff constraint (objective ⋈ incumbent); a fixing whose sub-box cannot reach the incumbent is discarded. Sound because the incumbent bounds the optimum.

Return type:

BoundTightening

Notes

Reductions are applied PER SCALAR through the Rust in-tree kernel (#1513): each element of an array variable is propagated and probed individually. (Before #1513 this passed one hull interval per block, which lost every per-element bound and – with probing – fixed a whole binary array block at once, so z[0] + z[1] == 1 over a binary z of shape (2,) was reported infeasible.) The returned bounds are intersected with the model’s current bounds, so the result is a sound subset of the input box.