eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
//! Cost-scaling push-relabel minimum-cost-flow solver.
//!
//! Implemented from the published literature — Goldberg (1997) for the
//! scaling structure and the efficiency heuristics, Goldberg & Tarjan (1990)
//! for successive approximation, Goldberg & Tarjan (1988) for push-relabel
//! itself. See `docs/ALGORITHM.md` for the implementer's notes.
//!
//! # Sign convention
//!
//! Reduced cost is `c_p(u,v) = c(u,v) − p(u) + p(v)`
//! [cite: AHUJA-MAGNANTI-ORLIN §9.3]. A pseudoflow `f` with prices `p` is
//! **ε-optimal** when every residual arc satisfies `c_p(u,v) ≥ −ε`. A residual
//! arc is **admissible** when `c_p(u,v) < 0`, so `push` moves flow down a price
//! gradient and `relabel` *raises* `p(u)`.
//!
//! ⚠ **Goldberg (1997) uses the mirror convention**, so this marker used to
//! point at the wrong paper. Its §2.1 defines
//! `c_p(v,w) = c(v,w) + p(v) − p(w)`, and its `relabel` correspondingly
//! *decreases* `p(v)` to `max over residual (v,w) of [p(w) − c(v,w) − ε]`
//! (§2.2). The two differ by the sign of `p` and describe the same algorithm;
//! lifting a formula out of that paper without flipping it inverts `relabel`.
//! The form above is Ahuja–Magnanti–Orlin's, and it is the one this whole
//! crate uses, including [`crate::verify`].
//!
//! # Why the answer is exact
//!
//! Costs are multiplied by `n + 1` before scaling begins. With integral costs,
//! a flow that is ε-optimal for `ε < 1/n` is optimal
//! [cite: GOLDBERG-TARJAN-1990 §2.2 Thm 2.3; GOLDBERG-1997 §2.1], so scaling
//! down to `ε = 1` in the multiplied units — i.e. `1/(n+1) < 1/n` in the
//! caller's units — terminates at a provable optimum rather than near one.
//! Nothing is rounded, and the objective is recomputed from the caller's own
//! arcs at the end, not accumulated along the way.
//!
//! The ε-relaxation of complementary slackness this rests on is due to
//! Bertsekas [cite: BERTSEKAS-1988 §2]: Goldberg & Tarjan attribute the
//! `ε < 1/n` theorem to him by name, and Goldberg (1997) §1 names "the
//! relaxation method of Bertsekas" as one of the three ingredients the method
//! combines.
//!
//! # Determinism
//!
//! There is no randomness, no floating point and no hash iteration anywhere on
//! this path, so a given instance always yields the same flow on the same
//! build. [`SolverOptions::deterministic`] goes further and canonicalises the
//! arc order first, so instances that differ only in the order their arcs were
//! declared also yield the same flow.

use crate::arith::{Capacity, Cost, Flow, Objective, Overflow, Price, add, mul, reduced_cost, sub};
use crate::error::SolveError;
use crate::maxflow::FlowNetwork;
use crate::network::{Normalized, normalize};
use crate::problem::Problem;

/// Distance sentinel for a node the global-update sweep never reached.
#[cfg(feature = "heur-global-update")]
const UNREACHED: i64 = i64::MAX;

/// End-of-chain sentinel for the Dial bucket arena, and — since it is the one
/// index no entry may occupy — the arena's capacity limit.
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
const BUCKET_NIL: u32 = u32::MAX;

/// Order in which nodes with excess are selected for discharge.
///
/// The choice affects running time and *which* optimal flow is returned when
/// several are optimal, which is why it is explicit rather than incidental.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum ActiveNodeOrder {
    /// First in, first out. The default: it bounds the number of passes over
    /// the active set and behaves predictably on layered networks.
    #[default]
    Fifo,
    /// Last in, first out. Cheaper bookkeeping, better locality on some
    /// instances, worse worst case.
    Lifo,
}

/// Knobs for a solve. Defaults are the measured-good settings; every field is
/// a documented trade, not a magic number.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct SolverOptions {
    /// Canonicalise the arc order before solving, so permuted-but-equal
    /// instances return the same flow and not merely the same cost.
    ///
    /// Costs one sort of the arc list. The solver is deterministic either way;
    /// this makes it *canonical*.
    ///
    /// # The exact claim
    ///
    /// Canonical **up to permutation within a group of identical parallel
    /// arcs** — arcs agreeing in tail, head, bounds and cost. That caveat is
    /// not an implementation shortcut, it is forced: such arcs are
    /// indistinguishable, so if the flow were required to be identical under
    /// every relabelling of them, they would all have to carry equal flow, and
    /// two identical arcs sharing three units of an integral flow cannot. For
    /// every distinguishable arc the flow is exactly reproducible, and the
    /// multiset of flows over each identical group is too.
    pub deterministic: bool,

    /// Scaling factor α: ε shrinks by this much each phase. Clamped to ≥ 2.
    ///
    /// Larger α means fewer phases doing more work each.
    ///
    /// **The default is 32, which is measured, not inherited** — and, now
    /// that the paper has been verified against, consistent with it: CS 1.0
    /// defaults to α = 12 [cite: GOLDBERG-1997 §4.1] and Goldberg reports the
    /// method robust for α between 4 and 50, with differences usually under
    /// 2× [cite: GOLDBERG-1997 §7]. (An earlier revision of this crate
    /// attributed "8–16" to this paper; the paper says no such thing — that
    /// range appears in Király & Kovács as "8 to 24"
    /// [cite: KIRALY-KOVACS-2012 §3.3].) This crate shipped 8 until it was
    /// measured, at which point α = 32 was 1.9× faster than α = 8 on a
    /// 140×140 grid, monotone from 2 to 64 across every family; re-measured
    /// unchanged with arc fixing and price refinement on (2026-08-07). The
    /// sweep has not been checked against adversarial families, which this
    /// crate does not yet generate.
    ///
    /// Run `cargo run --release --example bench` for the current sweep.
    pub scaling_factor: u32,

    /// Active-node selection order.
    pub selection: ActiveNodeOrder,

    /// Upper bound on pushes plus relabels, after which the solve gives up
    /// with [`SolveError::OperationBudgetExhausted`].
    ///
    /// `None` — the default — means no bound: the algorithm terminates on its
    /// own, and an arbitrary cap would turn a slow solve into a wrong answer.
    /// The engine sets this when it owns a time budget (design law 4).
    pub max_operations: Option<u64>,
}

impl Default for SolverOptions {
    fn default() -> Self {
        Self {
            deterministic: false,
            scaling_factor: 32,
            selection: ActiveNodeOrder::Fifo,
            max_operations: None,
        }
    }
}

impl SolverOptions {
    /// Set [`deterministic`](Self::deterministic).
    ///
    /// The struct is `#[non_exhaustive]`, so adding a knob later cannot break
    /// a caller — which also means it cannot be built with a struct
    /// expression. These setters are how it is configured.
    #[must_use]
    pub fn with_deterministic(mut self, deterministic: bool) -> Self {
        self.deterministic = deterministic;
        self
    }

    /// Set [`scaling_factor`](Self::scaling_factor). Values below 2 are
    /// clamped to 2 at solve time.
    #[must_use]
    pub fn with_scaling_factor(mut self, scaling_factor: u32) -> Self {
        self.scaling_factor = scaling_factor;
        self
    }

    /// Set [`selection`](Self::selection).
    #[must_use]
    pub fn with_selection(mut self, selection: ActiveNodeOrder) -> Self {
        self.selection = selection;
        self
    }

    /// Set [`max_operations`](Self::max_operations).
    #[must_use]
    pub fn with_max_operations(mut self, max_operations: Option<u64>) -> Self {
        self.max_operations = max_operations;
        self
    }
}

/// What the solve did. Trend data for benchmarking; also the evidence that a
/// heuristic changed the *path* to the optimum and not the optimum itself.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct SolveStats {
    /// Scaling phases executed — refines run, plus phases skipped whole by
    /// price refinement (so `refinement_skips ≤ scaling_phases`).
    pub scaling_phases: u32,
    /// Flow-moving operations.
    pub pushes: u64,
    /// Price increases.
    pub relabels: u64,
    /// Global price recomputations (`heur-global-update`).
    pub global_updates: u64,
    /// Relabels triggered by push-lookahead (`heur-push-lookahead`).
    pub lookahead_relabels: u64,
    /// Arcs proved unable to change flow again and retired from every hot
    /// loop at a phase boundary (`heur-arc-fixing`). Counts arcs, i.e. entry
    /// pairs.
    pub arcs_fixed: u64,
    /// Phases skipped entirely because the previous flow re-verified as
    /// ε-optimal for the new ε under adjusted potentials
    /// (`heur-price-refinement`). Each one is a whole refine that never ran.
    pub refinement_skips: u64,
    /// Relaxations the bucket sweep declined to pursue because the improved
    /// distance lay past its ceiling (`heur-bucket-update`). Counts *events*,
    /// not nodes: a node whose over-ceiling label improves repeatedly is
    /// counted each time. Nonzero means the `2n + 1` bucket array is binding
    /// and the sweep is truncating — sound, but a route change against the
    /// unbounded heap sweep, so it is measured rather than assumed.
    pub update_truncations: u64,
    /// The scaling loop stopped early because the flow was already provably
    /// optimal, rather than running every phase down to ε = 1.
    pub early_exit: bool,
}

/// An optimal flow, with the evidence to check it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Solution {
    flows: Vec<Flow>,
    objective: Objective,
    prices: Vec<Price>,
    stats: SolveStats,
}

impl Solution {
    /// Flow on each arc, in the caller's arc order, including lower bounds.
    #[must_use]
    pub fn flows(&self) -> &[Flow] {
        &self.flows
    }

    /// Total cost `Σ wₖ·fₖ`.
    ///
    /// Unique across all optimal flows, which is what makes it the right thing
    /// to compare against an oracle. Two correct algorithms may return
    /// different flows; they may not return different costs.
    #[must_use]
    pub fn objective(&self) -> Objective {
        self.objective
    }

    /// The solver's own final prices.
    ///
    /// Exposed because a caller may want the duals. **Not** an optimality
    /// certificate: prices produced by a buggy solver would certify that same
    /// bug. [`crate::verify`] therefore does not accept them — its entry
    /// points take only the problem and the flow, and recompute potentials
    /// from scratch.
    #[must_use]
    pub fn prices(&self) -> &[Price] {
        &self.prices
    }

    /// Work done reaching this solution.
    #[must_use]
    pub fn stats(&self) -> SolveStats {
        self.stats
    }
}

/// Solve `problem` with default options.
///
/// # Errors
///
/// [`SolveError::Infeasible`] if no flow satisfies the supplies and bounds;
/// [`SolveError::Overflow`] if the scaled costs or prices leave `i64`.
pub fn solve(problem: &Problem) -> Result<Solution, SolveError> {
    solve_with(problem, &SolverOptions::default())
}

/// Solve `problem` with explicit options.
///
/// # Errors
///
/// As [`solve`], plus [`SolveError::OperationBudgetExhausted`] when
/// [`SolverOptions::max_operations`] is set and reached.
pub fn solve_with(problem: &Problem, options: &SolverOptions) -> Result<Solution, SolveError> {
    if !options.deterministic {
        return solve_inner(problem, options);
    }
    // Canonical mode: solve the canonicalised instance, then restate the flow
    // in the caller's arc order. Node ids and supplies are untouched, so the
    // prices come back unchanged.
    let (canonical, perm) = problem.canonical();
    let solved = solve_inner(&canonical, options)?;
    let mut flows = vec![0 as Flow; problem.arc_count()];
    for (canonical_index, &original_index) in perm.iter().enumerate() {
        flows[original_index] = solved.flows[canonical_index];
    }
    Ok(Solution { flows, ..solved })
}

fn solve_inner(problem: &Problem, options: &SolverOptions) -> Result<Solution, SolveError> {
    let normalized = normalize(problem)?;
    check_feasible(&normalized)?;

    let mut engine = Engine::new(normalized, options)?;
    engine.run()?;

    let normalized = engine.normalized;
    let flows = normalized.reconstruct();
    let objective = problem.objective(&flows)?;

    // `certify-on-solve`: prove every answer before returning it. Off by
    // default because certification is O(n·m) — but when it is on it must
    // actually run, and a solve that cannot certify its own output is a defect
    // reported to the caller rather than a result handed over quietly.
    #[cfg(feature = "certify-on-solve")]
    if let Err(error) = crate::verify::certify(problem, &flows) {
        return Err(SolveError::SelfCertificationFailed(error));
    }

    Ok(Solution {
        flows,
        objective,
        prices: engine.price,
        stats: engine.stats,
    })
}

/// Reject infeasible instances before any scaling happens.
///
/// Routes every unit of (post-normalisation) supply to demand through a
/// max-flow computation. Feasible exactly when all of it arrives.
fn check_feasible(normalized: &Normalized) -> Result<(), SolveError> {
    let node_count = normalized.res.node_count;
    let source = node_count;
    let sink = node_count + 1;

    let mut edges: Vec<(u32, u32, Capacity)> = normalized.forward_arcs().collect();
    let mut required: i128 = 0;
    for (v, &excess) in normalized.excess.iter().enumerate() {
        let node = u32::try_from(v).map_err(|_| SolveError::InvariantViolated {
            what: "node index exceeds u32 after a successful build",
        })?;
        match excess.cmp(&0) {
            std::cmp::Ordering::Greater => {
                edges.push((source as u32, node, excess));
                required += i128::from(excess);
            }
            std::cmp::Ordering::Less => {
                let demand = excess
                    .checked_neg()
                    .ok_or_else(|| Overflow::new("node demand after lower-bound substitution"))?;
                edges.push((node, sink as u32, demand));
            }
            std::cmp::Ordering::Equal => {}
        }
    }

    let routable = FlowNetwork::new(node_count + 2, &edges).max_flow(source, sink);
    if routable == required {
        Ok(())
    } else {
        Err(SolveError::Infeasible { routable, required })
    }
}

/// Solver state for one instance.
struct Engine {
    normalized: Normalized,
    price: Vec<Price>,
    /// Current-arc pointer per node: arcs before it are known inadmissible
    /// under the current prices, so a discharge never rescans them.
    current: Vec<u32>,
    queue: std::collections::VecDeque<u32>,
    queued: Vec<bool>,
    selection: ActiveNodeOrder,
    alpha: Cost,
    budget: Option<u64>,
    operations: u64,
    relabels_since_update: u64,
    stats: SolveStats,
    /// Scratch for the global update, held across calls so a solve allocates
    /// them once instead of once per update (`heur-global-update`).
    #[cfg(feature = "heur-global-update")]
    update_dist: Vec<i64>,
    #[cfg(feature = "heur-global-update")]
    update_lifted: Vec<Price>,
    #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
    update_heap: std::collections::BinaryHeap<std::cmp::Reverse<(i64, u32)>>,
    /// Dial buckets for the price-update sweep (`heur-bucket-update`): one
    /// chain head per distance in `0..=2n`. Sized once, reused by every
    /// update.
    #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
    bucket_head: Vec<u32>,
    /// Chain entries as `(node, next)`. One `Vec` rather than two parallel
    /// ones so the two halves cannot drift apart, and `u32` rather than
    /// `usize` because both fields are bounded by the residual entry count:
    /// 8 bytes per entry instead of 12, on the largest node-proportional
    /// allocation the engine makes. Reserved to its bound up front, so a
    /// sweep never reallocates.
    #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
    bucket_arena: Vec<(u32, u32)>,
    /// Highest distance the bucket array can hold, i.e. `2n`.
    #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
    bucket_ceiling: i64,
    /// Scratch for price refinement, held across phases
    /// (`heur-price-refinement`): per-node distances in units of ε, in-degree
    /// counters for the topological pass, the FIFO worklist, and the
    /// candidate prices computed aside.
    #[cfg(feature = "heur-price-refinement")]
    refine_dist: Vec<i64>,
    #[cfg(feature = "heur-price-refinement")]
    refine_indegree: Vec<u32>,
    #[cfg(feature = "heur-price-refinement")]
    refine_queue: std::collections::VecDeque<u32>,
    #[cfg(feature = "heur-price-refinement")]
    refine_price: Vec<Price>,
}

impl Engine {
    fn new(normalized: Normalized, options: &SolverOptions) -> Result<Self, SolveError> {
        let node_count = normalized.res.node_count;
        // `2n + 1` buckets: prices move by O(nε) within a refine, so the
        // sweep never needs to represent a larger distance
        // [cite: GOLDBERG-1997 §3.1; GOLDBERG-1995-SP §6].
        #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
        let bucket_count = node_count.saturating_mul(2).saturating_add(1);
        // One arena entry per deficit seed and per distance-improving
        // relaxation, so the sweep can never need more than this — reserve it
        // once rather than growing inside the hot loop.
        #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
        let arena_bound = node_count.saturating_add(normalized.res.head.len());
        Ok(Self {
            price: vec![0 as Price; node_count],
            current: vec![0; node_count],
            queue: std::collections::VecDeque::with_capacity(node_count),
            queued: vec![false; node_count],
            selection: options.selection,
            alpha: Cost::from(options.scaling_factor.max(2)),
            budget: options.max_operations,
            operations: 0,
            relabels_since_update: 0,
            stats: SolveStats::default(),
            #[cfg(feature = "heur-global-update")]
            update_dist: vec![0; node_count],
            #[cfg(feature = "heur-global-update")]
            update_lifted: Vec::with_capacity(node_count),
            #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
            update_heap: std::collections::BinaryHeap::with_capacity(node_count),
            #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
            bucket_head: vec![BUCKET_NIL; bucket_count],
            #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
            bucket_arena: Vec::with_capacity(arena_bound),
            #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
            bucket_ceiling: (bucket_count - 1) as i64,
            #[cfg(feature = "heur-price-refinement")]
            refine_dist: vec![0; node_count],
            #[cfg(feature = "heur-price-refinement")]
            refine_indegree: vec![0; node_count],
            #[cfg(feature = "heur-price-refinement")]
            refine_queue: std::collections::VecDeque::with_capacity(node_count),
            #[cfg(feature = "heur-price-refinement")]
            refine_price: Vec::with_capacity(node_count),
            normalized,
        })
    }

    /// The scaling loop: multiply costs into the exact range, then refine ε
    /// down to 1.
    fn run(&mut self) -> Result<(), SolveError> {
        let node_count = self.normalized.res.node_count;
        if node_count == 0 || self.normalized.res.head.is_empty() {
            return Ok(());
        }

        // Cost multiplication (see the module note on exactness).
        let scale = Cost::try_from(node_count)
            .ok()
            .and_then(|n| n.checked_add(1))
            .ok_or_else(|| Overflow::new("cost scale factor n + 1"))?;
        let mut max_abs: Cost = 1;
        for slot in &mut self.normalized.res.cost {
            let scaled = mul(*slot, scale, "scaled arc cost")?;
            *slot = scaled;
            let magnitude = scaled
                .checked_abs()
                .ok_or_else(|| Overflow::new("magnitude of scaled arc cost"))?;
            max_abs = max_abs.max(magnitude);
        }

        // f = 0 with p = 0 is max|c|-optimal: every residual arc is a forward
        // arc, and its reduced cost is its cost, which is ≥ −max|c|.
        let mut eps = max_abs;
        loop {
            eps = if eps <= 1 {
                1
            } else {
                (eps / self.alpha).max(1)
            };

            // Price refinement: from the second phase on — earlier there is a
            // pseudoflow, not a flow, and skipping refine would strand its
            // excesses — try to re-verify the standing flow as ε-optimal for
            // the new ε with adjusted potentials, and skip the whole refine
            // when that succeeds. The flow is untouched, so a skipped phase
            // is neutral by construction. Goldberg applies the heuristic on
            // exactly this schedule: every scaling iteration except the first
            // [cite: GOLDBERG-1997 §6].
            #[cfg(feature = "heur-price-refinement")]
            let skipped = self.stats.scaling_phases > 0 && self.price_refine(eps)?;
            #[cfg(not(feature = "heur-price-refinement"))]
            let skipped = false;

            if skipped {
                self.stats.refinement_skips += 1;
            } else if self.refine(eps)? {
                // Already exactly optimal — every remaining phase is a no-op.
                self.stats.scaling_phases += 1;
                self.stats.early_exit = true;
                return Ok(());
            }
            self.stats.scaling_phases += 1;

            // The phase ended with an ε-optimal flow — refine produced one,
            // or refinement proved one — which is the exact hypothesis of the
            // fixing theorem: arc fixing is done after every execution of
            // refine [cite: GOLDBERG-1997 §3.3]. Pointless after the final
            // phase; the solve is over.
            #[cfg(feature = "heur-arc-fixing")]
            if eps > 1 {
                self.fix_at_boundary(eps)?;
            }

            if eps == 1 {
                return Ok(());
            }
        }
    }

    /// Retire every live residual entry whose reduced cost exceeds `2nε`,
    /// together with its partner, at a phase boundary where the flow is
    /// ε-optimal [cite: GOLDBERG-1997 §3.3].
    ///
    /// # Why the flow on such an arc can never change again
    ///
    /// Goldberg states the threshold and attributes the justification to
    /// Goldberg & Tarjan and to Tardos [cite: GOLDBERG-1997 §3.3, citing
    /// GOLDBERG-TARJAN-1990; TARDOS-1985]. The argument, reproduced here so
    /// this crate does not rest on an uncheckable step
    /// (`docs/ALGORITHM.md` §7.4): let `(f, p)` be ε-optimal on the current
    /// live network and `a` a live residual entry with `c_p(a) > 2nε ≥
    /// (2n−1)ε`. Suppose some later flow `f′` of the same (live) problem,
    /// ε′-optimal for any `ε′ ≤ ε`, differs from `f` on `a`. The circulation
    /// `f′ − f` decomposes into simple cycles; one of them, `Γ`, moves flow
    /// on `a` or on its partner.
    ///
    /// * If `f′(a) > f(a)`, then `Γ ∋ a` is residual in `G_f`, so its cost is
    ///   `c(Γ) = Σ_Γ c_p > 2nε − (n−1)ε > nε`; but `Γ` reversed is residual
    ///   in `G_{f′}`, so `c(Γ) ≤ nε′ ≤ nε` — contradiction.
    /// * If `f′(a) < f(a)`, the partner entry would have to be residual in
    ///   `G_f` with `c_p = −c_p(a) < −ε`, contradicting ε-optimality; so the
    ///   flow sits at the bound that direction cannot leave.
    ///
    /// Every subsequent state of this solver — and every optimal flow, which
    /// is 0-optimal — is such an `f′`, so freezing the pair and solving the
    /// reduced problem loses nothing: an optimal flow of the reduced problem
    /// plus the frozen values is an optimal flow of the unreduced one, by
    /// induction over boundaries. The reduced problem stays feasible for the
    /// same reason — the restriction of any optimal flow witnesses it — so
    /// an active node always keeps a live residual path to a deficit and
    /// `relabel` cannot starve. No un-fixing pass is needed at this
    /// threshold: the theorem quantifies over the entire rest of the solve.
    #[cfg(feature = "heur-arc-fixing")]
    fn fix_at_boundary(&mut self, eps: Cost) -> Result<(), SolveError> {
        let node_count = self.normalized.res.node_count;
        let Some(threshold) = Cost::try_from(node_count)
            .ok()
            .and_then(|n| n.checked_mul(2))
            .and_then(|n2| n2.checked_mul(eps))
        else {
            // Unrepresentable threshold: fix nothing. A heuristic must never
            // turn a solvable instance into an error.
            return Ok(());
        };

        for u in 0..node_count {
            let mut i = self.normalized.res.first_out[u] as usize;
            while i < self.normalized.res.active_end[u] as usize {
                let res = &self.normalized.res;
                if res.cap[i] > 0 {
                    let v = res.head[i] as usize;
                    // A heuristic never gets to be the error site: if this
                    // reduced cost overflows, abandon the scan and let the
                    // mainline saturation pass, which computes the very same
                    // value, be the one that reports it.
                    let Ok(rc) = reduced_cost(res.cost[i], self.price[u], self.price[v]) else {
                        return Ok(());
                    };
                    if rc > threshold {
                        self.normalized.res.fix_pair(i, u);
                        self.stats.arcs_fixed += 1;
                        // A live entry was swapped into `i`; re-examine it.
                        continue;
                    }
                }
                i += 1;
            }
        }
        // One pass over the live entries; charge it like the update sweep.
        self.charge_many(node_count as u64)
    }

    /// Try to prove the current *flow* ε-optimal for the new, smaller ε by
    /// adjusting potentials only, and skip the whole refine when it verifies
    /// [cite: GOLDBERG-1997 §3.2; KIRALY-KOVACS-2012 §3.3].
    ///
    /// Follows the pass structure of Goldberg's price refine heuristic. Each
    /// pass topologically sorts the admissible graph — a cycle there fails
    /// the attempt immediately, which is what makes failure cheap — then
    /// computes nonpositive approximate distances `d` in units of ε over the
    /// admissible DAG and raises every price by `−d(v)·ε`. If the flow now
    /// verifies ε-optimal the phase is skipped; otherwise the raise is kept —
    /// following the paper's observation that the work is not lost — and
    /// another pass runs, up to a small cap. Without the bucket sharpening
    /// (below), a kept raise repairs admissible arcs but can push
    /// non-admissible residual arcs further below −ε for the next refine to
    /// saturate; measured across the benchmark families the keep is a large
    /// net win in the default composition (2026-08-07 report), which is why
    /// it stays.
    /// One deliberate simplification against the paper: the bucket-based
    /// sharpening pass over non-admissible arcs (from the scaling
    /// shortest-paths algorithm [cite: GOLDBERG-1995-SP]) is not implemented;
    /// it improves how often a pass suffices, never what a success means.
    ///
    /// **A skip does not rest on the search being right.** Every raise is
    /// computed aside and adopted only whole, and the skip itself is gated on
    /// an explicit `c_p ≥ −ε` re-check of every live residual arc — the
    /// certifier discipline applied inside the solver. A defect in the pass
    /// can only fail to find a certificate, never manufacture one. Overflow
    /// anywhere abandons the attempt without adopting the offending pass's
    /// raise, so every adopted price state is one whose live residual
    /// reduced costs the mainline can compute.
    ///
    /// Prices only ever rise here (`d ≤ 0`), matching the rest of the
    /// solver; under `heur-arc-fixing` the scan covers live arcs only — the
    /// reduced problem is the one being solved, and fixed arcs stay fixed
    /// because the fixing theorem is a statement about flows, indifferent to
    /// potentials.
    #[cfg(feature = "heur-price-refinement")]
    fn price_refine(&mut self, eps: Cost) -> Result<bool, SolveError> {
        // The paper bounds passes by O(n); in practice success comes in the
        // first couple and failure announces itself as an admissible cycle in
        // the very first, so a small cap only trims pathological attempts.
        const PASS_CAP: u32 = 8;

        let node_count = self.normalized.res.node_count;
        for _ in 0..PASS_CAP {
            // Kahn's algorithm over the admissible subgraph (live residual
            // arcs with negative reduced cost). Deterministic: the initial
            // queue is filled in node order and processed FIFO.
            self.refine_indegree.clear();
            self.refine_indegree.resize(node_count, 0);
            for u in 0..node_count {
                for a in self.normalized.res.out_arcs(u) {
                    if self.normalized.res.cap[a] <= 0 {
                        continue;
                    }
                    let v = self.normalized.res.head[a] as usize;
                    // Abandon on overflow rather than erroring the solve: a
                    // heuristic never gets to be the error site, and the
                    // mainline refine computes the same value anyway.
                    let Ok(rc) =
                        reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])
                    else {
                        return Ok(false);
                    };
                    if rc < 0 {
                        self.refine_indegree[v] += 1;
                    }
                }
            }
            self.refine_queue.clear();
            for v in 0..node_count {
                if self.refine_indegree[v] == 0 {
                    self.refine_queue.push_back(v as u32);
                }
            }

            // Process in topological order, relaxing d(w) ≤ d(v) + ⌈c_p/ε⌉
            // over admissible arcs; d ≤ 0, in units of ε. For an admissible
            // arc, ⌈c_p/ε⌉ = −⌊−c_p/ε⌋.
            self.refine_dist.clear();
            self.refine_dist.resize(node_count, 0);
            let mut processed = 0usize;
            while let Some(u) = self.refine_queue.pop_front() {
                let u = u as usize;
                processed += 1;
                let du = self.refine_dist[u];
                for a in self.normalized.res.out_arcs(u) {
                    if self.normalized.res.cap[a] <= 0 {
                        continue;
                    }
                    let v = self.normalized.res.head[a] as usize;
                    let Ok(rc) =
                        reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])
                    else {
                        return Ok(false);
                    };
                    if rc >= 0 {
                        continue;
                    }
                    // ⌈rc/ε⌉ for rc < 0, ε ≥ 1, as (rc + ε − 1) ⌊/⌋ ε — no
                    // negation, so rc = i64::MIN has no panic path; the sum
                    // cannot overflow because rc is negative and ε − 1 ≥ 0.
                    let step = rc.saturating_add(eps - 1).div_euclid(eps);
                    let candidate = du.saturating_add(step);
                    if candidate < self.refine_dist[v] {
                        self.refine_dist[v] = candidate;
                    }
                    self.refine_indegree[v] -= 1;
                    if self.refine_indegree[v] == 0 {
                        self.refine_queue.push_back(v as u32);
                    }
                }
            }
            if processed < node_count {
                // An admissible cycle. Its total reduced cost — equal to its
                // true cost — is negative, so the flow is not optimal, and
                // the topological pass this procedure repairs prices with
                // cannot exist. Whether some other potentials could still
                // certify ε-optimality (a short cycle of mean ≥ −ε might) is
                // deliberately not decided: the paper's procedure fails the
                // attempt on admissible cycles, and failing is conservative —
                // after one linear-time pass.
                self.charge_many(node_count as u64)?;
                return Ok(false);
            }

            // Raise prices by −d(v)·ε, computed aside, adopted only whole.
            let mut candidate = std::mem::take(&mut self.refine_price);
            candidate.clear();
            let mut raised_any = false;
            for (&d, &price) in self.refine_dist.iter().zip(&self.price) {
                let Some(units) = d.checked_neg() else {
                    self.refine_price = candidate;
                    return Ok(false);
                };
                raised_any |= units > 0;
                let Ok(lift) = mul(units, eps, "refinement price lift") else {
                    self.refine_price = candidate;
                    return Ok(false);
                };
                let Ok(price) = add(price, lift, "refined price") else {
                    self.refine_price = candidate;
                    return Ok(false);
                };
                candidate.push(price);
            }
            // The gate runs against the candidate BEFORE adoption, for two
            // verdicts at once: ε-optimality of the unchanged flow, arc by
            // arc, and — the reason it must precede `copy_from_slice` —
            // representability of every live residual reduced cost under the
            // candidate prices. Adopting first would let a raise whose
            // reduced costs overflow become the solver's state, surfacing
            // later as a solve error on an instance that solves with the
            // heuristic off. Gate-then-adopt keeps every adopted state one
            // the mainline can compute over.
            let mut certified = true;
            'verify: for u in 0..node_count {
                for a in self.normalized.res.out_arcs(u) {
                    if self.normalized.res.cap[a] <= 0 {
                        continue;
                    }
                    let v = self.normalized.res.head[a] as usize;
                    let Ok(rc) =
                        reduced_cost(self.normalized.res.cost[a], candidate[u], candidate[v])
                    else {
                        // Unrepresentable under the raise: abandon without
                        // adopting it. Prices stay at the last adopted —
                        // hence representable — state.
                        self.refine_price = candidate;
                        return Ok(false);
                    };
                    if rc < -eps {
                        certified = false;
                        break 'verify;
                    }
                }
            }

            self.price.copy_from_slice(&candidate);
            self.refine_price = candidate;
            self.charge_many(node_count as u64)?;

            if certified {
                return Ok(true);
            }
            if !raised_any {
                // A fixpoint that still fails cannot improve on repetition.
                return Ok(false);
            }
        }
        Ok(false)
    }

    /// One scaling phase: turn an ε′-optimal flow into an ε-optimal flow.
    ///
    /// Returns `true` when the flow is already **exactly** optimal, so the
    /// caller can stop the scaling loop entirely.
    fn refine(&mut self, eps: Cost) -> Result<bool, SolveError> {
        let node_count = self.normalized.res.node_count;

        // Saturating every admissible arc leaves a pseudoflow whose residual
        // arcs all have non-negative reduced cost — 0-optimal, hence ε-optimal
        // for the new, smaller ε. Excess appears; the rest of the phase
        // eliminates it without ever dropping below −ε.
        let mut saturated_any = false;
        for u in 0..node_count {
            for a in self.normalized.res.out_arcs(u) {
                if self.normalized.res.cap[a] <= 0 {
                    continue;
                }
                let v = self.normalized.res.head[a] as usize;
                if reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])? < 0 {
                    let delta = self.normalized.res.cap[a];
                    self.normalized.excess[u] =
                        sub(self.normalized.excess[u], delta, "node excess")?;
                    self.normalized.excess[v] =
                        add(self.normalized.excess[v], delta, "node excess")?;
                    self.normalized.res.push(a, delta);
                    saturated_any = true;
                }
            }
        }

        // The saturation pass computes, for free, the one fact that can end the
        // solve early: if it saturated nothing then every residual arc has
        // c_p ≥ 0 under the current prices, and if nothing holds excess then
        // the pseudoflow is a flow. A flow whose residual arcs all have
        // non-negative reduced cost satisfies complementary slackness exactly
        // — ε = 0, not ε = 1 — so it is optimal and every remaining phase
        // would do nothing. Costs one bool; on long thin networks it skips
        // most of the schedule.
        if !saturated_any && !self.normalized.excess.iter().any(|&e| e > 0) {
            return Ok(true);
        }

        self.current
            .copy_from_slice(&self.normalized.res.first_out[..node_count]);
        self.queue.clear();
        self.queued.iter_mut().for_each(|q| *q = false);
        for u in 0..node_count {
            if self.normalized.excess[u] > 0 {
                self.activate(u);
            }
        }

        self.relabels_since_update = 0;
        self.global_update(eps)?;

        while let Some(u) = self.next_active() {
            if self.normalized.excess[u] <= 0 {
                continue;
            }
            self.discharge(u, eps)?;

            // Prices drift as relabels accumulate; recomputing them globally
            // once per n relabels keeps the admissible graph pointed at the
            // deficits instead of letting it decay — the paper's starting
            // point for the update frequency [cite: GOLDBERG-1997 §3.1].
            if self.relabels_since_update >= node_count as u64 {
                self.relabels_since_update = 0;
                self.global_update(eps)?;
                self.current
                    .copy_from_slice(&self.normalized.res.first_out[..node_count]);
            }
        }
        Ok(false)
    }

    /// Move all excess off `u`, relabelling whenever no admissible arc remains.
    ///
    /// Push, relabel, the current-arc pointer and this loop are the max-flow
    /// push-relabel method with reduced costs in place of distance labels
    /// [cite: GOLDBERG-TARJAN-1988]. Goldberg (1997) §1 describes the method as
    /// combining cost scaling with "the push-relabel maximum flow method of
    /// Goldberg and Tarjan", and its §2.2 specifies the current-arc pointer in
    /// the form used here: set to the node's first arc initially and after each
    /// relabel of that node.
    fn discharge(&mut self, u: usize, eps: Cost) -> Result<(), SolveError> {
        // Spans only shrink at phase boundaries, never inside a refine, so
        // the live end can be cached for the whole call.
        let span_end = self.normalized.res.live_end(u);

        while self.normalized.excess[u] > 0 {
            while self.current[u] < span_end {
                let a = self.current[u] as usize;
                if self.normalized.res.cap[a] <= 0 {
                    self.current[u] += 1;
                    continue;
                }
                let v = self.normalized.res.head[a] as usize;
                if reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])? >= 0 {
                    self.current[u] += 1;
                    continue;
                }

                // Pushing into a node that cannot pass the flow on just moves
                // the excess one hop and comes straight back. Relabel it first.
                if self.lookahead(v, eps)? {
                    continue;
                }

                let delta = self.normalized.excess[u].min(self.normalized.res.cap[a]);
                let was_active = self.normalized.excess[v] > 0;
                self.normalized.res.push(a, delta);
                self.normalized.excess[u] -= delta;
                self.normalized.excess[v] = add(self.normalized.excess[v], delta, "node excess")?;
                self.stats.pushes += 1;
                self.charge()?;
                if !was_active && self.normalized.excess[v] > 0 {
                    self.activate(v);
                }
                if self.normalized.excess[u] == 0 {
                    return Ok(());
                }
            }

            if !self.relabel(u, eps)? {
                // Feasibility was established up front, so an active node
                // always retains a residual arc towards a deficit — and under
                // arc fixing, a live one: the reduced problem left by sound
                // boundary fixing is itself feasible
                // (`docs/ALGORITHM.md` §7.4).
                return Err(SolveError::InvariantViolated {
                    what: "active node has excess but no residual outgoing arc",
                });
            }
            self.current[u] = self.normalized.res.first_out[u];
        }
        Ok(())
    }

    /// Raise `p(u)` by the least amount that makes one live residual arc
    /// admissible, keeping every live residual arc at `c_p ≥ −ε`.
    ///
    /// Returns `false` when `u` has no live residual outgoing arc at all.
    fn relabel(&mut self, u: usize, eps: Cost) -> Result<bool, SolveError> {
        let mut best: Option<Cost> = None;
        for a in self.normalized.res.out_arcs(u) {
            if self.normalized.res.cap[a] <= 0 {
                continue;
            }
            let v = self.normalized.res.head[a] as usize;
            let candidate = add(
                self.normalized.res.cost[a],
                self.price[v],
                "relabel candidate",
            )?;
            best = Some(best.map_or(candidate, |b: Cost| b.min(candidate)));
        }
        let Some(minimum) = best else {
            return Ok(false);
        };

        let raised = add(minimum, eps, "relabelled price")?;
        if raised <= self.price[u] {
            return Err(SolveError::InvariantViolated {
                what: "relabel did not raise the price of an unadmissible node",
            });
        }
        self.price[u] = raised;
        self.stats.relabels += 1;
        self.relabels_since_update += 1;
        self.charge()?;
        Ok(true)
    }

    /// Does `v` have an admissible residual arc under the current prices?
    ///
    /// Scans from `v`'s **current-arc pointer**, not from the start of its
    /// span, and advances it over what it rejects. Arcs before the pointer are
    /// already known inadmissible, and the discipline that establishes that
    /// (§ `discharge`) holds for `v` whoever is asking. Restarting the scan
    /// each time re-examined the same dead arcs on every push into `v`, which
    /// is why push-lookahead measured as a *loss* on dense bipartite families:
    /// the work was quadratic in `v`'s degree rather than amortised.
    #[cfg(feature = "heur-push-lookahead")]
    fn has_admissible(&mut self, v: usize) -> Result<bool, Overflow> {
        let span_end = self.normalized.res.live_end(v);
        while self.current[v] < span_end {
            let a = self.current[v] as usize;
            if self.normalized.res.cap[a] > 0 {
                let w = self.normalized.res.head[a] as usize;
                if reduced_cost(self.normalized.res.cost[a], self.price[v], self.price[w])? < 0 {
                    return Ok(true);
                }
            }
            self.current[v] += 1;
        }
        Ok(false)
    }

    /// Push-lookahead. Returns whether prices changed, in which case
    /// the caller must re-evaluate the arc it was about to push along.
    #[cfg(feature = "heur-push-lookahead")]
    fn lookahead(&mut self, v: usize, eps: Cost) -> Result<bool, SolveError> {
        // Only for a node with *exactly* zero excess, and this is not a
        // refinement — it is the difference between terminating and not.
        //
        // A node with negative excess is a deficit: it absorbs flow, which is
        // the whole objective, so pushing into it is productive and relabelling
        // it is actively wrong. Doing so raises the price the excess is trying
        // to descend towards, the excess chases it, and the two escalate
        // without bound. A node with positive excess is already active and
        // will discharge itself. Only the zero-excess case — where an arriving
        // unit must immediately be passed on — is worth looking ahead for.
        if self.normalized.excess[v] != 0 || self.has_admissible(v)? {
            return Ok(false);
        }
        if !self.relabel(v, eps)? {
            return Ok(false);
        }
        self.current[v] = self.normalized.res.first_out[v];
        self.stats.lookahead_relabels += 1;
        Ok(true)
    }

    #[cfg(not(feature = "heur-push-lookahead"))]
    #[allow(clippy::unnecessary_wraps)]
    fn lookahead(&mut self, _v: usize, _eps: Cost) -> Result<bool, SolveError> {
        Ok(false)
    }

    /// Global price update: recompute every price from the distance
    /// to the nearest deficit, measured in units of ε — the set-relabel /
    /// price-update heuristic [cite: GOLDBERG-1997 §3.1].
    ///
    /// Arc lengths are `ℓ(v,w) = max(0, ⌊c_p(v,w)/ε⌋ + 1)`, which are
    /// non-negative, so a Dijkstra-style sweep suffices. Raising `p(v)` by
    /// `d(v)·ε` preserves ε-optimality: on any residual arc the reduced cost
    /// changes by `(d(w) − d(v))·ε ≥ −ℓ(v,w)·ε`, and `c_p − ℓ·ε ≥ −ε` by
    /// construction.
    ///
    /// The sweep itself is [`Self::update_sweep`], which has two
    /// implementations — a binary heap, and the Dial-style buckets of
    /// `heur-bucket-update` — each seeding itself from the deficits, since
    /// the two queues are seeded differently. The unreachable fallback and
    /// adopt-or-abandon below are shared.
    #[cfg(feature = "heur-global-update")]
    fn global_update(&mut self, eps: Cost) -> Result<(), SolveError> {
        let node_count = self.normalized.res.node_count;

        // Scratch held on the engine and reserved to its worst case in
        // `Engine::new`, so an update allocates nothing however often it runs.
        self.update_dist.clear();
        self.update_dist.resize(node_count, UNREACHED);

        if !self.update_sweep(eps)? {
            // No deficit anywhere: nothing to measure distances to.
            return Ok(());
        }

        // Nodes that cannot reach any deficit are raised by the largest finite
        // distance. Anything less would leave an arc from a raised node into
        // an unraised one with a reduced cost below −ε.
        //
        // Distances are additionally truncated at the sweep's ceiling, which
        // is finite only under `heur-bucket-update`. Truncating a
        // shortest-distance labelling at a *uniform* cap preserves the
        // relaxation invariant `d(v) ≤ d(w) + ℓ(v,w)` that the ε-optimality
        // argument above needs — either both sides are below the cap and
        // nothing changed, or the left side is the cap and the right is at
        // least it.
        //
        // The two rules meet in one case worth spelling out, because the
        // ceiling changes the old reasoning. Without a ceiling, a residual
        // arc `v→w` whose head is reachable forces its tail to be reachable
        // too, so an unreachable node never sits above a reachable one. With
        // a ceiling, `v` *can* stay unreachable while `w` merely sits past
        // the ceiling, unscanned, so that implication no longer holds on its
        // own — but if anything was truncated then the fallback, taken over
        // the *truncated* distances, is the ceiling itself, and `v` and `w`
        // are lifted by the same amount. Computing the fallback after
        // `min(ceiling)` rather than before is what makes that true; the
        // `.map()` below is load-bearing, not cosmetic.
        let ceiling = self.sweep_ceiling();
        let fallback = self
            .update_dist
            .iter()
            .copied()
            .filter(|&d| d != UNREACHED)
            .map(|d| d.min(ceiling))
            .max()
            .unwrap_or(0);

        // Compute the new prices aside and adopt them only if every one fits.
        // A heuristic may change the route to the optimum; it may never change
        // whether an instance is solvable, so an overflow here abandons the
        // update instead of failing the solve.
        let mut lifted = std::mem::take(&mut self.update_lifted);
        lifted.clear();
        for (&distance, &price) in self.update_dist.iter().zip(&self.price) {
            let d = if distance == UNREACHED {
                fallback
            } else {
                distance.min(ceiling)
            };
            let Ok(lift) = mul(d, eps, "global update price lift") else {
                self.update_lifted = lifted;
                return Ok(());
            };
            let Ok(price) = add(price, lift, "globally updated price") else {
                self.update_lifted = lifted;
                return Ok(());
            };
            lifted.push(price);
        }
        self.price.copy_from_slice(&lifted);
        self.update_lifted = lifted;

        self.stats.global_updates += 1;
        // The sweep touched every node and every residual arc; charge for it.
        self.charge_many(node_count as u64)?;
        Ok(())
    }

    /// Largest distance the sweep can report, in units of ε. Unbounded for
    /// the heap sweep; the bucket count for the bucket sweep.
    #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
    #[inline]
    fn sweep_ceiling(&self) -> i64 {
        self.bucket_ceiling
    }

    /// The heap sweep represents any distance an `i64` can hold, so nothing
    /// is ever truncated and `min(ceiling)` in [`Self::global_update`] is a
    /// no-op.
    #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
    #[inline]
    #[allow(clippy::unused_self)]
    fn sweep_ceiling(&self) -> i64 {
        i64::MAX
    }

    /// Fill `update_dist` with each node's distance to the nearest deficit
    /// over *residual* arcs, in units of ε. Returns `false` when the instance
    /// has no deficit at all, in which case there is nothing to update.
    ///
    /// Binary-heap sweep: `O(m log n)`, ties broken by node id so the heap
    /// order is total and the result is reproducible across platforms.
    #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
    fn update_sweep(&mut self, eps: Cost) -> Result<bool, SolveError> {
        use std::cmp::Reverse;

        self.update_heap.clear();
        for (v, &excess) in self.normalized.excess.iter().enumerate() {
            if excess < 0 {
                self.update_dist[v] = 0;
                self.update_heap.push(Reverse((0, v as u32)));
            }
        }
        if self.update_heap.is_empty() {
            return Ok(false);
        }

        while let Some(Reverse((d, w))) = self.update_heap.pop() {
            let w = w as usize;
            if d > self.update_dist[w] {
                continue;
            }
            for a in self.normalized.res.out_arcs(w) {
                let Some((v, candidate)) = self.relax(a, w, d, eps)? else {
                    continue;
                };
                self.update_dist[v] = candidate;
                self.update_heap.push(Reverse((candidate, v as u32)));
            }
        }
        Ok(true)
    }

    /// Dial-style bucket sweep: `O(m + n)` with constant amortised queue cost,
    /// which is what the reference implementation uses for this heuristic
    /// [cite: GOLDBERG-1997 §3.1; GOLDBERG-1995-SP §6, §9].
    ///
    /// Lengths are non-negative integers and a scan of bucket `i` can only
    /// insert into bucket `i` or above, so one monotone pass over the bucket
    /// array visits every node in non-decreasing distance order — Dijkstra's
    /// order, without a heap. Buckets are singly-linked through an arena, and
    /// a decrease-key is a plain re-insertion: the older entry is left in
    /// place and skipped when popped, since `update_dist` is the authority on
    /// a node's current distance.
    ///
    /// The array holds `2n + 1` buckets, so the ceiling is `2n`. Prices move
    /// by `O(nε)` within a refine, so the sweep *chooses not to pursue* a
    /// distance beyond that — it does arise, and often: nodes past the
    /// ceiling are recorded but not inserted, which is the truncation
    /// [`Self::global_update`] accounts for and `update_truncations` counts.
    #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
    fn update_sweep(&mut self, eps: Cost) -> Result<bool, SolveError> {
        let ceiling = self.bucket_ceiling;
        self.bucket_head.fill(BUCKET_NIL);
        self.bucket_arena.clear();

        let mut seeded = false;
        for v in 0..self.normalized.res.node_count {
            if self.normalized.excess[v] < 0 {
                self.update_dist[v] = 0;
                // Seeds cannot exhaust the arena: there are at most `n` of
                // them and `n ≤ MAX_NODES = u32::MAX`, so the last seed's
                // index is below the `BUCKET_NIL` sentinel. Silently dropping
                // a *deficit* would be unsound — it would leave a distance-0
                // node unscanned while its neighbours took the fallback — so
                // this is asserted rather than assumed.
                let pushed = self.bucket_push(0, v);
                debug_assert!(pushed, "a deficit seed must always fit the arena");
                seeded = true;
            }
        }
        if !seeded {
            return Ok(false);
        }

        // Walk only as far as the buckets actually reach. The array is sized
        // for the worst case (`2n`), but a sweep whose furthest node settles
        // at distance 3 has no business stepping over the other `2n − 3`
        // empty chains. Insertions never target a bucket below the current
        // index, so tracking the high-water mark as we go is enough.
        let mut index: i64 = 0;
        let mut highest: i64 = 0;
        while index <= highest {
            loop {
                let entry = self.bucket_head[index as usize];
                if entry == BUCKET_NIL {
                    break;
                }
                let (node, next) = self.bucket_arena[entry as usize];
                self.bucket_head[index as usize] = next;
                let w = node as usize;
                // Stale entry from a decrease-key, or a node already scanned
                // at a smaller distance.
                if self.update_dist[w] != index {
                    continue;
                }
                for a in self.normalized.res.out_arcs(w) {
                    let Some((v, candidate)) = self.relax(a, w, index, eps)? else {
                        continue;
                    };
                    self.update_dist[v] = candidate;
                    // Past the ceiling — or, unreachably in practice, past
                    // what the arena can index — the distance is recorded but
                    // never scanned, and truncated back to the ceiling when
                    // the lift is applied. Both are the same sound
                    // truncation, and both are counted.
                    if candidate <= ceiling && self.bucket_push(candidate as usize, v) {
                        highest = highest.max(candidate);
                    } else {
                        self.stats.update_truncations += 1;
                    }
                }
            }
            index += 1;
        }
        Ok(true)
    }

    /// Relax the residual arc that enters `w` through out-entry `a`, given
    /// `w`'s settled distance `d`. Returns the tail and its improved distance,
    /// or `None` when the arc is not residual or offers no improvement.
    ///
    /// The sweep runs backwards — reaching `v` from `w` means `v` can send
    /// flow towards `w` — so the arc examined is the *reverse* entry of `a`.
    /// Under arc fixing only live spans are walked, and a live entry's partner
    /// is live too, so fixed arcs are never seen: the update serves the
    /// reduced problem, which is the one being solved
    /// (`docs/ALGORITHM.md` §7.4).
    #[cfg(feature = "heur-global-update")]
    #[inline]
    fn relax(
        &self,
        a: usize,
        w: usize,
        d: i64,
        eps: Cost,
    ) -> Result<Option<(usize, i64)>, SolveError> {
        let incoming = self.normalized.res.rev[a] as usize;
        if self.normalized.res.cap[incoming] <= 0 {
            return Ok(None);
        }
        let v = self.normalized.res.head[a] as usize;
        let rc = reduced_cost(
            self.normalized.res.cost[incoming],
            self.price[v],
            self.price[w],
        )?;
        let length = rc.div_euclid(eps).saturating_add(1).max(0);
        let candidate = d.saturating_add(length);
        if candidate < self.update_dist[v] {
            Ok(Some((v, candidate)))
        } else {
            Ok(None)
        }
    }

    /// Prepend `node` to bucket `index`. Returns `false` only if the arena
    /// has reached the one index it may not use — `BUCKET_NIL` — which needs
    /// more entries than a representable instance can produce; the caller
    /// then treats the node as truncated, which is sound for the same reason
    /// the ceiling is.
    #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
    #[inline]
    fn bucket_push(&mut self, index: usize, node: usize) -> bool {
        let Ok(entry) = u32::try_from(self.bucket_arena.len()) else {
            return false;
        };
        if entry == BUCKET_NIL {
            return false;
        }
        self.bucket_arena
            .push((node as u32, self.bucket_head[index]));
        self.bucket_head[index] = entry;
        true
    }

    #[cfg(not(feature = "heur-global-update"))]
    #[allow(clippy::unnecessary_wraps)]
    fn global_update(&mut self, _eps: Cost) -> Result<(), SolveError> {
        Ok(())
    }

    fn activate(&mut self, v: usize) {
        if self.queued[v] {
            return;
        }
        self.queued[v] = true;
        match self.selection {
            ActiveNodeOrder::Fifo => self.queue.push_back(v as u32),
            ActiveNodeOrder::Lifo => self.queue.push_front(v as u32),
        }
    }

    fn next_active(&mut self) -> Option<usize> {
        let v = self.queue.pop_front()? as usize;
        self.queued[v] = false;
        Some(v)
    }

    /// Charge one unit against the caller's operation budget.
    fn charge(&mut self) -> Result<(), SolveError> {
        self.charge_many(1)
    }

    /// Charge `units` against the caller's operation budget.
    ///
    /// Pushes and relabels are not the only work worth charging for: a global
    /// update sweeps the whole graph and, measured, dominates the running time
    /// on the shapes this crate exists to serve. A budget that ignored it
    /// would not be a time proxy at all — the same instance can differ by more
    /// than an order of magnitude in operations-per-second depending on how
    /// often the sweep runs.
    fn charge_many(&mut self, units: u64) -> Result<(), SolveError> {
        self.operations = self.operations.saturating_add(units);
        match self.budget {
            Some(budget) if self.operations > budget => Err(SolveError::OperationBudgetExhausted {
                budget,
                scaling_phases: self.stats.scaling_phases,
            }),
            _ => Ok(()),
        }
    }
}