MathIdeasResearch in progressRepository ↗
← Research catalogOriginal Markdown ↓
On this page

Bounded integer-flow scenario and flexibility analysis

Decision: Prototype finite model diagnostics; defer a practical unrestricted counting/sampling backend. Edition: 9 October 2026 Australia/Brisbane. Buyer demand, useful scenario law and profitable delivery remain unvalidated.

Research finding

Family 115's cell-bounded-table paper has a full bounded integral-flow corollary. It claims an FPRAS for integer arc-value vectors in explicitly listed finite directed multigraphs with finite binary integer lower/upper bounds and prescribed balances. Loops and parallel arcs are allowed. A separate approximate sampler always returns a feasible vector when one exists, has total-variation error at most tau from uniform feasible vectors, and bounded bit cost polynomial in input length and 1/tau. It asserts neither exact bounded-flow sampling nor logarithmic-only accuracy cost.

The reduction shifts lower bounds, subdivides every arc through a private vertex and encodes the balance through row/column margins and forced diagonal slack. This preserves each arc-value vector once, rather than counting its path/cycle decompositions. The selected Comparator lists uncapped table sampling and capped table counting; it does not separately select the flow reduction/sampler. This corollary is a reviewed paper claim, with source proof/import/program acceptance unverified.

Problem and buyer

A logistics, capacity-planning or network-model team may have many feasible integer configurations and want to know which arcs are mandatory, how much feasible flexibility a restriction removes, or whether a scenario generator follows its stated law. A standard minimum-cost-flow result gives one optimized assignment. Configuration diversity and uniform feasibility scenarios answer another question, and their usefulness depends on the team's actual decision.

The candidate buyer must have a single-commodity integer model with explicit arc identities/bounds/balances, a reason to inspect configuration counts or marginals, and a recurring task. A free loop or a change of integer units can alter the count without improving operational resilience. Counts alone do not establish failure probabilities or business value.

What the finding could enable

A scenario-analysis plugin could take a network model, preserve signed lower bounds and parallel arcs, compare feasible-vector counts under declared restrictions, report exact small-model marginals, and distinguish a sampler's intended uniform law from optimizer output or path-weighted scenarios. If the source backend becomes practical, it could extend approximate counts and near-uniform generation to broad binary-capacity models.

The implemented bounded_flow_reference.py supplies the source-oriented reduction and a conventional small-table exact engine. It reports exact arc vectors/histograms on tiny cases and unknown when counting or diagnostics exceed limits. It is not the source FPRAS or approximate sampler. A shared model/evidence adapter is presently more credible than a new production network optimizer.

Technical and commercial limits

The conversion caps 16 original vertices/16 arcs and signed integers at 256 magnitude bits. The exact table engine permits dimension six, total 128, 50,000 memo states and one million count work units; diagnostics permit 2,000 flows/four million unranking work units. A valid reduction can greatly exceed these exact limits. K=1+2*sum(upper-lower)+sum(abs(shifted balance)), table dimension q=|V|+|E| and total qK+sum(positive shifted balance) make this explicit. Large capacity is kept in binary rather than expanded into unit arcs.

Multicommodity constraints, global cost ceilings, uniform optimal-cost configurations, actual disruption risk and continuous flows require separate models/results. Uniform integer vectors depend on the chosen units and allowed circulations; they need not be realistic scenarios. A zero approximate count is not a feasibility certificate. Sampling's polynomial 1/tau dependence cannot inherit the uncapped table sampler's polynomial accuracy-bit bound or its exactness.

Minimal architecture

Explicit graph/arc identity and unit convention -> lower-bound shift and balance checks -> private-vertex table reduction -> existing feasibility proposer with separate exact bounds/balance validation -> bounded exact count/diagnostics or separately reviewed approximate backend -> explicit scenario-law/restriction report -> planner decision record. Preserve source/model/backend versions, exact feasible support and count/diagnostic unknown states. Costs and optimization objectives remain a distinct model layer.

Existing alternatives and differentiation

NetworkX network_simplex solves minimum-cost flow, using net inflow as demand; the source uses net outflow as balance, so the integration sets demand to minus the shifted balance. The local NetworkX 3.4.2 MultiDiGraph baseline retains parallel arc IDs and proposes checked vectors on generated fixtures. Its intended output is one vector, not a uniform sample. Primary API.

OR-Tools also supplies a minimum-cost-flow solver and a public five-node/nine-arc example. Its original cost objective is kept in the existing-solver baseline. The source count concerns all capacity/balance-feasible vectors; adding a cost constraint would change that set. The proposed differentiation must be useful configuration/law evidence, not replacing an already adequate optimizer. Official model.

Monetization hypothesis

Hypothesis: AUD 6,000–10,000 for a bounded scenario/model assessment integrated with an existing planner. At an assumed AUD 8,000 fee and 30 hours at AUD 180/hour, AUD 2,600 remains before support, sales and overhead; 50 hours cost AUD 9,000 and exceed the fee. These are experimental prices and labor assumptions, not quotes or revenue. A recurring subscription needs demonstrated repeated value and low support effort. This module overlaps the shared evidence/data/allocation platform and must not be counted as an additional independent customer.

Validation experiment

460 controls compare the reduction with direct Cartesian arc enumeration across 144 signed/loop/parallel/balance cases, forward/inverse identities, small fixtures, invalid inputs and distinct budget states. Two parallel unit arcs have two feasible vectors and half-mass zero/saturation events. A signed loop from -2 to 2 has five states while cancelling from balance. A two-route unit network has two feasible vectors. A capacity 2^200 remains a three-by-three reduction, with its finite-reference count unknown.

13 existing-solver controls validate NetworkX proposals on four generated cases, generated infeasibility and the public model. The public reduction is 14-by-14 with total 3,422, so its count/feasibility stay unknown in the exact reference even though an existing solver supplies a separately checked feasible vector. Saved comparison. OR-Tools was not executed; optimum certification, runtime superiority, actual planning outcomes and buyer value were not measured.

Conditions to reject or defer

Defer a production unrestricted counting/sampling backend until practical subroutines/constants and realistic workloads exist. Reject the commercial idea if configuration counts do not improve a decision, circulation/unit artifacts dominate, or existing sensitivity tools suffice. Reject exact/log-precision/multicommodity/cost-optimal sampling badges from this corollary. A valid source reduction and tiny exact marginals do not establish production resilience or profitability.

Next concrete action

Run the two-route fixture through the reference, inspect the public capacity model and record which missing restrictions make it a useful operational scenario. Compare a useful restriction's effect on an actual decision before pricing an integration. Inspect the source count/sampler practical parameters independently; preserve its paper-level status. Flow documentary contract and illustrative scope report expose model and badge gaps without certifying evidence.

Pinned source evidence