Transportation & Allocation Network (LP)

Problem Class	Solver	Key APIs	Links
Linear Programming (LP)	HiGHS (default)	m.continuous(), m.constraint(), expr (sum, dot), minimize	Open in Playground Source Code

The transportation problem is one of the most fundamental network optimization models: determine how many units to ship from each supply origin (factory) to each destination (store) to minimize total shipping cost while respecting factory supply limits and meeting store demands.

This example demonstrates how to construct a 2D matrix of decision variables using m.continuous(factories, stores) and write aggregated constraints declaratively via dot() and m.constraint(expr...).

Problem Inputs

We have 3 factories (Tokyo, Nagoya, Osaka) shipping to 4 regional stores (North, East, West, South):

Factory \ Store	North ($/unit)	East ($/unit)	West ($/unit)	South ($/unit)	Supply Capacity
Tokyo	$4	$2	$7	$8	120 units
Nagoya	$6	$4	$3	$5	100 units
Osaka	$9	$7	$2	$3	80 units
Store Demand	70 units	90 units	60 units	60 units	Total: 280 / 300

Mathematical Formulation

Let $x_{f, s} \ge 0$ be the quantity shipped from factory $f \in F$ to store $s \in S$, and $c_{f, s}$ be the unit shipping cost.

$$\begin{aligned} \text{Minimize} \quad & \sum_{f \in F} \sum_{s \in S} c_{f,s} \, x_{f,s} \\ \text{Subject to} \quad & \sum_{s \in S} x_{f,s} \le \text{Supply}_f \quad \forall f \in F \quad (\text{Factory capacity}) \\ & \sum_{f \in F} x_{f,s} \ge \text{Demand}_s \quad \forall s \in S \quad (\text{Store demand}) \\ & x_{f,s} \ge 0 \quad \forall f \in F, s \in S \end{aligned}$$

Implementation in WaSHI

import { Model, minimize, expr } from "@ohtaman/washi";

const factories = ["Tokyo", "Nagoya", "Osaka"] as const;
const stores = ["North", "East", "West", "South"] as const;

const shippingCost = {
  Tokyo:  { North: 4, East: 2, West: 7, South: 8 },
  Nagoya: { North: 6, East: 4, West: 3, South: 5 },
  Osaka:  { North: 9, East: 7, West: 2, South: 3 },
};

const supplies = { Tokyo: 120, Nagoya: 100, Osaka: 80 };
const demands = { North: 70, East: 90, West: 60, South: 60 };

async function solveScenario(label: string, cap: typeof supplies) {
  const m = new Model("TransportationNetwork");

  // 1. Create 2D continuous variables: ship[factory][store] >= 0
  const ship = m.continuous([...factories], [...stores], { lb: 0 });

  // 2. Objective: Minimize total shipping cost across all routes via 2D dot product
  m.objective(minimize(expr`dot(${shippingCost}, ${ship})`));

  // 3. Supply constraints (row sums): outgoing from f <= cap[f]
  const supplyConstrs = Object.fromEntries(
    factories.map((f) => [
      f,
      m.constraint(expr`sum(${ship[f]}) <= ${cap[f]}`, `supply_${f}`),
    ])
  );

  // 4. Demand constraints (column sums): incoming to s >= demands[s]
  const demandConstrs = Object.fromEntries(
    stores.map((s) => [
      s,
      m.constraint(
        expr`sum(${factories}, ${(f) => ship[f][s]}) >= ${demands[s]}`,
        `demand_${s}`
      ),
    ])
  );

  const status = await m.solve();
  console.log(`[${label}] Status: ${status}, Total Shipping Cost: $${m.objectiveValue}`);
  for (const f of factories) {
    const dual = supplyConstrs[f].dual ?? 0;
    const routes = stores
      .map((s) => `${s}:${Math.round(ship[f][s].value ?? 0)}`)
      .join(", ");
    console.log(`  ${f.padEnd(7)} -> ${routes} (supply dual: $${dual}/u)`);
  }
  const demandDuals = stores
    .map((s) => `${s}:$${demandConstrs[s].dual ?? 0}`)
    .join(", ");
  console.log(`  Marginal Delivered Cost (demand duals) -> ${demandDuals}`);
}

async function runTransportation() {
  // Scenario A: Baseline capacities ($920)
  await solveScenario("Scenario A: Baseline", supplies);

  // Scenario B: Tokyo capacity reduced (120 -> 80) due to maintenance ($1,000)
  await solveScenario("Scenario B: Tokyo Maintenance", {
    Tokyo: 80,
    Nagoya: 120,
    Osaka: 100,
  });
}

runTransportation();

Open in Playground →

Practical Notes

• Interpreting Supply & Demand Shadow Prices (.dual):
  • demand_s.dual ($\ge 0$): The marginal delivered cost of supplying 1 additional unit to store $s$.
  • supply_f.dual ($\le 0$): How much total network shipping cost would decrease if factory $f$'s capacity were expanded by 1 unit. In Scenario B, when Tokyo is constrained at 80 units, supply_Tokyo.dual becomes negative (-$2/u), indicating that each extra unit of capacity in Tokyo saves $2 by avoiding rerouting through Nagoya.
• Total Supply vs. Total Demand ($\sum \text{Supply}_f \ge \sum \text{Demand}_s$): If store demands exceed aggregate factory capacity, the hard demand constraints become "Infeasible". In production logistics systems, add an elastic "spot-carrier / backorder" variable $u_s \ge 0$ to each store's demand constraint ($\sum_f x_{f,s} + u_s \ge \text{Demand}_s$) with a high penalty cost so the solver allocates scarce inventory optimally rather than failing.