chronos-mesh

ADR-0003: Pure-Python Exact Two-Phase Tableau Simplex & Best-First Branch-and-Bound MILP Engine

Context

Fixed-charge multi-sourcing rerouting requires solving Mixed-Integer Linear Programs (MILPs) of the form:

\[\min_{x \ge 0,\; y \in \{0,1\}^m} \; c^\top x + f^\top y \quad \text{s.t.} \quad A_{\text{ub}}[x; y] \le b_{\text{ub}}, \;\; A_{\text{eq}}[x; y] = b_{\text{eq}}\]

where binary activation variables $y_e \in {0, 1}$ model contractual carrier setup charges $f_e$ and Big-$M$ lane capacity coupling $x_e - M_e y_e \le 0$.

Relying on proprietary commercial solver licenses (Gurobi, CPLEX) prevents deterministic zero-dependency execution in CI and air-gapped edge environments, while naive greedy heuristics or LP rounding violate hard anti-concentration caps ($x_e \le \alpha D$) or produce suboptimal fixed-charge carrier activations.

Decision

We implement a self-contained, dependency-free Exact Two-Phase Tableau Simplex + Best-First Branch-and-Bound MILP Solver (src/chronos_mesh/optimizer/milp_solver.py):

  1. Canonical Slack & Artificial Basis Construction:
    • Inequality rows $a_i^\top z \le b_i$ (after sign normalization for $b_i < 0$) receive slack variables; equality rows and flipped $\ge$ rows receive Phase-I artificial variables.
  2. Bland’s Anti-Cycling Pivot Rule:
    • Under degenerate supply-chain network polytopes (common when multiple lanes hit capacity bounds simultaneously), Dantzig’s steepest-edge rule can cycle indefinitely. Both Phase-I (feasibility) and Phase-II (optimality) enforce Bland’s Rule—selecting the smallest-index entering column with negative reduced cost and breaking minimum-ratio ties by smallest basic variable index—guaranteeing finite termination.
  3. Best-First Branch-and-Bound (heapq) with Most-Fractional Branching:
    • Each node solves the LP relaxation. Nodes with relaxation lower bound $\underline{z} \ge z^\star - \epsilon$ are fathomed immediately.
    • Fractional binary/integer variables are branched on $\lfloor z_j \rfloor$ and $\lceil z_j \rceil$ selecting the variable closest to $0.5$, prioritizing min-bound open nodes on a min-heap to certify zero optimality gap rapidly.
  4. Property-Based Brute-Force Equivalence Proof:
    • Verified via Hypothesis (tests/test_milp_properties.py) across randomized fixed-charge instances against an exhaustive $2^m$ exact enumeration oracle, proving global optimality to $10^{-5}$ tolerance.

Consequences