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.

Module Contents

class discopt.tightening.BoundTightening

Result of an FBBT bound-tightening pass.

Attributes

lb, ubnp.ndarray

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

infeasiblebool

True if propagation derived an empty interval for some variable, which proves the problem infeasible.

n_tightenedint

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) → 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.

Parameters

modelModel

The model whose bounds to tighten.

max_iterint

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

tolfloat

Numerical tolerance for empty-interval (infeasibility) detection.

Returns

BoundTightening