LP Transport Solver — Algorithm Reference

Overview

The LP Transport Solver is an alternative to the default Rust MRP engine for supply planning. It formulates the entire multi-echelon supply chain as a single linear program (LP) and solves it with the HIGHS solver via Pyomo. The objective is to minimize total transport cost while respecting all constraints from upstream processes (forecast demand, MEIO safety stock, EOQ min-qty, firm orders, calendars, capacity).

When to use it:

• You want globally optimal transport routing instead of greedy source-priority ordering
• You have a multi-echelon network (2–7 levels) where the MRP's sequential 2-pass approach produces suboptimal transfers
• You want to model reverse logistics (repair dispatch, bad-stock pool, scrap) as explicit decisions rather than pre-computed parameters

When NOT to use it:

• You need source priority enforcement (the LP ignores source_priority and picks the cheapest route globally)
• You rely on MinMax/PoQ order policies (the LP uses continuous review only)
• You need the consolidation window or nervousness limit features (not yet modeled in Phase 1)

---

Mathematical Formulation

Sets

Set	Description
I	Items (sku_id)
L	Locations (site_id)
T	Time periods (weeks 0…H-1, default H=52)
R	Routes (route_id with source_type, src→dest, lead_time)

Decision Variables

All variables are continuous, non-negative.

Variable	Domain	Description
x[i,l,r,t]	ℝ⁺	Flow on route r for item i at location l released in period t
inv[i,l,t]	ℝ⁺	Ending inventory of good stock at node (i,l) in period t
short[i,l,t]	ℝ⁺	Shortage (unmet demand) at node (i,l) in period t
ss_slack[i,l,t]	ℝ⁺	Safety stock violation slack at node (i,l) in period t
bad[i,l,t]	ℝ⁺	Bad-stock inventory at node (i,l) in period t
Y[i,l,t]	ℝ⁺	Repair dispatch (units sent to repair) at node (i,l) in period t
scrap[i,l,t]	ℝ⁺	Units scrapped from bad pool at node (i,l) in period t

Objective Function

Minimize:

Σ c(r) × x[i,l,r,t]                    // transport + procurement cost
+ Σ h(i) × inv[i,l,t]                  // inventory holding cost
+ Σ P_short × short[i,l,t]             // shortage penalty
+ Σ P_ss × ss_slack[i,l,t]             // safety stock violation penalty
+ Σ P_scrap × scrap[i,l,t]             // scrap cost

Where:

• c(r) = per-unit cost on route r = unit_cost + (order_cost + setup_cost) / estimated_batch_size
• h(i) = unit_cost × holding_cost_pct / 52 (weekly holding cost)
• P_short = shortage_penalty (default 50.0 per unit)
• P_ss = safety_stock_penalty (default 100.0 per unit)
• P_scrap = repair_scrap_cost (default 0.0 per unit)

Constraints

1. Inventory Balance (Good Stock)

inv[i,l,t] = inv[i,l,t-1]
           + SR[i,l,t]                    // scheduled receipts (firm orders)
           + repair_in[i,l,t]             // repair arrivals
           + Σ x[i,l,r,t-LT]              // route arrivals (release t-LT arrives at t)
           - Σ x[dest,ri,t]               // TRANSFER outflows to downstream nodes
           - demand[i,l,t]                // customer demand
           + short[i,l,t]                 // shortage (elastic slack)
           - ss_slack[i,l,t]              // SS violation (elastic slack)

This is the core constraint that unifies the entire multi-echelon network. Unlike the MRP's 2-pass approach (upstream MRP → allocation → downstream MRP), the LP models all flows in a single constraint system, so the solver jointly optimizes upstream procurement and downstream distribution.

The outflow term (Σ x[dest,ri,t]) is critical: when a WH sends a TRANSFER to a downstream store, those units are subtracted from the WH's inventory in the same period they are dispatched.

Figure: the inventory-balance constraint unifies the network — inflows (prior inventory, firm receipts, repair arrivals, route arrivals) minus outflows (transfers out, customer demand, safety-stock slack) yield the period's ending inventory, with shortage as elastic slack.

flowchart LR
  subgraph IN["Inflows"]
    I1["inv[i,l,t-1]"]
    I2["firm receipts (SR)"]
    I3["repair_in"]
    I4["route arrivals x[t-LT]"]
  end
  subgraph OUT["Outflows"]
    O1["transfer out"]
    O2["customer demand"]
    O3["safety-stock slack"]
  end
  IN --> BAL["inv[i,l,t] = balance"]
  OUT --> BAL
  BAL --> SH["short[i,l,t]<br/>(elastic)"]

2. Safety Stock (Soft Constraint)

inv[i,l,t] + ss_slack[i,l,t] ≥ SS[i,l,t]

Safety stock is soft — violations are allowed but penalized. This matches the MRP engine's behavior where SS is a planning target, not a hard requirement.

3. Bad-Stock Balance

bad[i,l,t] = bad[i,l,t-1]
           + bad_returns[i,l,t]           // deterministic inflow: demand × return_rate
           - Y[i,l,t]                     // repair dispatch
           - scrap[i,l,t]                 // scrap
           - repair_returns[i,l,t]        // pre-committed returns (from MRP preprocess)

The bad-stock pool is tracked explicitly. Unlike the MRP engine (where repair_returns is a pre-computed parameter), the LP treats repair dispatch as a decision variable — the solver chooses when and how much to repair.

4. Repair Feasibility

Y[i,l,t] ≤ bad[i,l,t-1] + bad_returns[i,l,t]    // can't repair more than available
Y[i,l,t] ≤ repair_capacity[i,l,t]                 // repair shop capacity

5. Repair Arrivals (Deterministic Delay)

repair_in[i,l,t] = Y[i,l,t-TA] × repair_yield   // when t ≥ TA

Where TA = repair_turnaround (combined return + repair lead time).

6. Route Calendar

Arcs where the shipping calendar bitmask = 0 are excluded from the model (variable not created for that period). This matches the MRP's sourcing_pass calendar check.

7. Capacity (Soft)

Σ flow_on_lane[r,t] ≤ capacity[r,t] × soft_capacity_multiplier

When capacity_enforcement = "soft", the solver may exceed hard capacity up to the soft limit. Overtime cost is implied by the per-unit route cost.

8. Firm Orders Block Horizon

When firm_orders_block_horizon = true:

x[i,l,r,t] = 0   for all t ≤ latest_firm_by_type[order_type]

This prevents the solver from creating new recommendations before the latest firm order of the same order type.

---

Cost Model

Per-Unit Cost Approximation

In Phase 1, the LP uses a linear per-unit cost on each route:

c(r) = unit_cost + (order_cost + setup_cost) / estimated_batch_size

The estimated_batch_size is computed as:

estimated_batch_size = max(average_demand_per_positive_week, min_qty, 1.0)

This approximation converts the fixed per-order cost (order_cost) into a per-unit equivalent. It is exact when the actual order quantity equals the estimated batch size. For quantities significantly above or below, there will be a cost estimation error. Phase 3 introduces MIP binary variables to model per-batch costs exactly.

Holding Cost

h(i) = unit_cost × holding_cost_pct / 52

Annual holding cost percentage (default 25%) divided by 52 gives the weekly cost per unit of inventory.

---

Multi-Echelon Network Flow

The LP models the entire multi-echelon supply chain as a unified network. The topology is discovered from the route data using the same BFS as _add_upstream_network_nodes().

Figure: the supply chain is a min-cost flow network — procurement (BUY) feeds the root warehouse, TRANSFER arcs move stock through transshipment nodes, and customer demand at stores is the sink. The LP solver decides flows on all arcs simultaneously.

flowchart LR
  SRC["Source: BUY route<br/>(procurement)"] --> R["RootWH<br/>(site 100)"]
  R ==TRANSFER==> C["CountryWH<br/>(site 10)"]
  C ==TRANSFER==> ST["Store<br/>(site 1)"]
  ST --> DM["Customer demand<br/>(sink)"]
  LP["LP solver<br/>(HIGHS / Pyomo)"] -.decides all flows.-> R
  LP -.decides all flows.-> C
  LP -.decides all flows.-> ST

3-Echelon Example

RootWH (site 100) --BUY--> [inventory] --TRANSFER--> CountryWH (site 10) --TRANSFER--> Store (site 1)

In the LP:

• RootWH has a BUY route → inflow x[root, buy_route, t], no direct demand
• CountryWH has a TRANSFER route from RootWH → inflow x[countrywh, transfer_route, t], outflow to Store
• Store has a TRANSFER route from CountryWH → inflow x[store, transfer_route, t], customer demand

The solver decides BUY quantities at RootWH, TRANSFER quantities from RootWH→CountryWH, and TRANSFER quantities from CountryWH→Store simultaneously — no sequential 2-pass decomposition.

Outflow Tracking

When node A sends a TRANSFER to node B:

inv[A,t] = ... - x[B, transfer_route, t]    // outflow from A
inv[B,t+LT] = ... + x[B, transfer_route, t]  // inflow to B at t+LT

This ensures flow conservation: every unit leaving A arrives at B after the lead time.

---

Reverse Logistics

The LP explicitly models the repair/scrap decision:

MRP Engine	LP Solver
repair_returns[t] is pre-computed: demand[t-TA] × return_rate × yield	Y[i,l,t] (repair dispatch) is a decision variable
All bad stock is repaired immediately	Solver chooses when and how much to repair
No scrap option	scrap[i,l,t] is a decision with configurable cost
Repair pool consumed sequentially	Repair dispatch bounded by bad-stock availability AND repair shop capacity

When repair shop capacity is binding, the solver prioritizes repairing items with the highest transport-cost savings. This is impossible in the MRP engine.

---

Lot-Sizing (Post-Processor)

The LP produces continuous (fractional) order quantities. Lot-sizing is applied as a post-processor after the LP solve:

Figure: after the HIGHS solver returns fractional flows, the lot-sizing post-processor snaps (or keeps) quantities to order multiples before writing identical-format rows to PIPE_supply_orders.

flowchart TD
  LP["HIGHS LP solve"] --> X["Continuous x[i,l,r,t]<br/>(fractional)"]
  X --> LS{"lot_sizing mode"}
  LS -- "snap" --> SN["ceil/floor to mult_qty<br/>max(result, min_qty)<br/>min(result, max_qty)"]
  LS -- "none" --> NN["keep fractional"]
  LS -- "relax_round" --> RR["round to nearest mult_qty"]
  SN --> OUT["PIPE_supply_orders"]
  NN --> OUT
  RR --> OUT

1. snap (default): Apply the same ceil/floor logic as the Rust allocate() step
2. ceil(qty / mult_qty) × mult_qty
3. max(result, min_qty)
4. min(result, max_qty)
5. floor to mult_qty

6. If result < min_qty → 0

7. none: Keep LP fractional quantities as-is

8. relax_round (Phase 2): Round to nearest mult_qty (up or down)

---

Item-Level Decomposition

For large instances (>5000 SKU-location pairs), the LP can be decomposed by item:

1. Solve each item independently (all locations + routes for that item)
2. Check shared capacity constraints for violations
3. If violations found, increase shadow prices and re-solve affected items
4. Repeat until convergence (max 3 iterations)

This reduces solve time from exponential in total SKU count to linear in the number of items, with typically 2-3 capacity reconciliation iterations.

---

Comparison: LP Solver vs MRP Engine

Feature	MRP Engine (Rust)	LP Transport Solver
Optimization	Greedy, source-priority order	Global cost minimization
Multi-echelon	Two Rust passes + Python allocation (upstream, allocation, stores). Supports N echelons via BFS discovery up to max_echelons=4 (default = 5 total levels). See MRP Engine Architecture	Unified LP network flow; same BFS input, all echelons optimized simultaneously
Source priority	Enforced (Repair→Return→Transfer→Build→Buy)	Ignored — picks cheapest route
Transfer allocation	Python _allocate_transfers() proportional	LP decides optimal quantities
Repair dispatch	Pre-computed parameter	Decision variable
Scrap	Not modeled	Decision with cost
Bad-stock pool	Informational only	Explicit balance constraint
Per-batch cost	Not optimized	Approximated per-unit (Phase 1), exact MIP (Phase 3)
Lot-sizing	Inline during sourcing	Post-processor snap
Pegging	Propagation-based	Propagation-based (matches)
Output tables	PIPE_supply_orders, etc.	Same tables, identical format