AppliedMath LexFlow: Deterministic Lexicographic Flow Allocation on Lossy Capacitated Trees

Abstract

Exact, reproducible software for deterministic lexicographic flow allocation on lossy, capacitated rooted trees, and for the inverse rehabilitation-design problem posed on the same model. The allocation module implements the three-stage lexicographic model of the AppliedMath article Three-Stage Lexicographic Allocation on Directed Irrigation Trees with Conveyance Losses and Capacity Constraints: A Closed-Form Stage-1 Fairness Guarantee and Operator–Balance Equivalence: the closed-form Stage-1 bottleneck value, the loss-aware net-to-gross operator and its node–balance equivalent, the weighted Stage-2 and smoothing Stage-3 linear programs, the exact progressive-filling leximin selector, the invariant variation range and the price of fairness. It ships the five exact rational benchmarks, the 36-node, 16-period Gone Abat Jap controlled scenario, the deterministic scaling generator up to 500 users and 1022 edges, and the scripts that regenerate every published table and figure. The design module implements the inverse problem behind the conference paper Bottleneck-Targeted Rehabilitation Planning for Lossy Irrigation Canal Networks: An Exact Guarantee–Budget Curve: the closed-form minimum-cost widening plan and its budget function, the epsilon-bottleneck-set ascent for lining, and exact-rational relief sets and minimum-cost transversals with a laminarity certificate. Version 0.5.0 added bench/scale_timing.py, which measures the runtime of the closed-form Stage-1 evaluation against the equivalent sparse HiGHS linear program, and revised the published figures following peer review. Version 0.5.1 adds bench/robustness_suite.py, a randomized suite of 200 instances in seven families that re-evaluates every acceptance gate outside the fixed benchmark construction, and bench/weight_sweep.py, which sweeps the Stage-2 service weights geometrically and applies three auditable weighting rules to the controlled canal scenario. It also redraws the surveyed canal network as the linear canal scheme used by the operating organization, with every offtake on the bank from which it actually takes water. Version 0.5.2 answers the second report of the third reviewer. The randomized suite now has 400 instances in ten families, 140 of them with source and reach capacities drawn independently of their own loads and 60 more that are not prescribed multiples of their own loads either; on every instance the bottleneck named by the closed form is confirmed by the Stage-1 linear program alone, and the suite records whether multiplicity of the Stage-2 optimum was detected by a one-sided face probe and whether Stage 3 changes the allocation. New modules compare the hierarchy with total-delivery maximization, equal proportional allocation, a weighted single objective and full leximin (comparison.py), solve Stage 3 with four smoothness criteria and block-specific variation limits (smoothing.py), perturb demands, efficiencies and capacities of the controlled scenario (perturbation.py, bench/perturbation.py) and apply five weighting rules with per-block winners and losers (weights.py). bench/scale_timing.py now times each phase separately in 30 runs and records the environment. Data/README.md states, for every shipped instance, which parameters come from the published Gone Abat Jap dataset (doi:10.17632/xt3gsf89n9.1) and which were imposed by the authors, and Data/design/ holds the scripts that re-derive every imposed parameter from the rule stated in the article; the test suite requires them to reproduce the shipped instance files exactly. Version 0.5.3 answers the third and fourth review rounds. The perturbation study records, with every draw, the departure of the accepted Stage-3 solution from the Stage-2 optimum, its shortfall below the Stage-1 guarantee and the largest relative excess of a source or reach load over its capacity, and reports the maximum of each over all draws and over the draws that needed a relaxed feasibility tolerance. solve_three_stage can be run without the Stage-1 verification linear program, which verifies the closed form and is not a step of the allocation, so bench/compare_rules.py times the hierarchy both ways. lp_bottleneck_test takes its comparison value from the Stage-1 linear program rather than from the closed form, which supplies only the prediction under test. No model, benchmark or result value changes. Version 0.5.5 renames the two families whose capacities are not prescribed multiples of their own loads from "Independent capacities" to "Untied capacities", matching the article; only the label column of the two Table A3 files changes. Version 0.5.4 corrects the provenance documentation of the controlled scenario. The per-period source allocations are imposed by the authors, not taken from the published dataset; Data/design/build_gone_abat_jap_capacities.py now re-derives them together with the reach capacities and the test suite checks both. The nominal design volumes are the design discharges of 7, 3 and 2 cubic metres per second over a period of ten days, or eleven days in periods 15, 20 and 25. No model, benchmark or result value changes. Version 0.5.6 renames the memory figure of bench/scale_timing.py to what tracemalloc actually reports, the peak of the Python allocations it traces; the internal allocations of HiGHS are compiled code and are not traced, the script sets no CPU affinity and does not restrict the number of threads HiGHS may use, and results/timing/environment.json now records all three. Figure 9 is redrawn with larger type. This record, CITATION.cff and Data/README.md are aligned with the associated article: the rehabilitation-design module of the package is not part of it. This file also becomes valid JSON again, which it had not been since v0.5.5. No model, benchmark or result value changes. Version 0.5.7 answers the eleventh review round. It renames the machine-readable Stage-2 diagnostics to what the one-sided face probe actually establishes (stage2_multiplicity_not_detected and stage3_inactive_multiplicity_detected in place of names containing "unique"), documents that the randomized generator scales each resource class by the lower median of its own positive full-demand loads, and adds a sixty-instance family whose source and reach volume scales are fixed before any draw from the declared family parameters alone, so that no capacity is a function of a realized load. The family is generated on its own seed and reported in its own tables; the 400 instances of the existing suite are bit-for-bit unchanged and no previously reported value changes. The loss operator, the closed-form Stage-1 value and the acceptance gates are evaluated in exact rational arithmetic and the Stage-2 and Stage-3 linear programs in double precision; inputs, outputs and the environment carry SHA-256 hashes.