🧩 Constraint Solving POTD:Problem of the Day: Minimum Cost Flow Problem

[github-actions[bot]]

Warning

threat detection engine error
The threat detection engine encountered an error and could not complete analysis. This is a tooling failure, not a security finding.

Details

The threat detection engine failed to produce results.

Review the workflow run logs for details.

Problem Statement

The Minimum Cost Flow (MCF) problem asks: given a directed network where edges have both capacity and unit cost, find a flow that satisfies supply/demand constraints at nodes while minimizing total cost.

Formal definition:

• A directed graph G = (V, E) with n nodes and m edges
• Each edge (i,j) ∈ E has:
  • Capacity: u_ij (max flow allowed)
  • Cost: c_ij (per unit of flow)
• Each node i ∈ V has supply/demand: b_i (positive = supply, negative = demand)
• Goal: Find flow x_ij on each edge such that:
  • Flow conservation at each node (net inflow = demand)
  • Edge capacities respected
  • Total cost Σ c_ij × x_ij is minimized

Concrete instance: A warehouse at node 1 supplies 100 units. Two distribution centers at nodes 2 and 3 each need 50 units. Edges: (1→2) cost 2, capacity 80; (1→3) cost 3, capacity 70; (2→3) cost 1, capacity 60. Optimal solution routes 50 directly to node 2, 50 from node 1 to node 3, using transshipment edge (2→3) if beneficial.

Why It Matters

• Supply chain optimization: Minimizing logistics costs for distributing products through a network of warehouses, distribution centers, and retailers.
• Telecommunications: Routing data packets through networks to minimize congestion costs while respecting link capacities.
• Manufacturing: Coordinating flow of materials through production stages with bottleneck constraints.
• Airline crew scheduling: Assigning crews to flight segments with minimum operational cost.

Modeling Approaches

Approach 1: Linear Programming (Standard)

Formulate as a linear program:

Minimize:  Σ_(i,j)∈E  c_ij × x_ij

Subject to:
  For each node i:  Σ_j x_ij - Σ_j x_ji = b_i   (flow conservation)
  For each edge (i,j):  0 ≤ x_ij ≤ u_ij       (capacity constraint)

Trade-offs:

• ✅ Solves optimally in polynomial time (Successive Shortest Path, Cost Scaling algorithms)
• ✅ Highly efficient implementations available (CPLEX, Gurobi, open-source solvers)
• ✅ Naturally handles fractional flows
• ❌ Less expressive than CP for discrete demands or complex side constraints

Approach 2: Constraint Programming with Discrete Flow

Model as an integer CSP:

Variables:
  x_ij ∈ {0..u_ij} for each edge (i,j)

Constraints:
  For each node i:  Σ_j x_ij - Σ_j x_ji = b_i
  Minimize:  Σ_(i,j)  c_ij × x_ij

Trade-offs:

• ✅ Naturally handles integrality constraints (unit shipments)
• ✅ Easy to add side constraints (e.g., "use at most k edges")
• ✅ Symmetry breaking available
• ❌ Requires integer optimization (NP-hard in general)
• ❌ Slower than LP solvers for large networks

Example Model (MiniZinc Pseudo-Code)

% Minimum Cost Flow in MiniZinc
int: n = 4;  % nodes
int: m = 5;  % edges
array[1..m] of int: from = [1, 1, 2, 2, 3];
array[1..m] of int: to = [2, 3, 3, 4, 4];
array[1..m] of int: capacity = [100, 80, 60, 90, 100];
array[1..m] of int: cost = [2, 3, 1, 4, 2];
array[1..n] of int: supply = [100, -40, -30, -30];

var array[1..m] of 0..max(capacity): flow;

% Flow conservation
constraint forall(i in 1..n)(
  sum(j in 1..m where from[j] = i)(flow[j]) -
  sum(j in 1..m where to[j] = i)(flow[j]) = supply[i]
);

% Capacity constraints handled by variable domain

minimize sum(j in 1..m)(cost[j] * flow[j]);

Approach 3: Network Simplex (Specialized Algorithm)

The Network Simplex algorithm is the gold standard for MCF:

• Exploits graph structure for efficient basis maintenance
• Pivot operations only move flow along edges in a spanning tree
• Typically 10–100× faster than general LP simplex

Key Techniques

1. Successive Shortest Path Algorithm

• Iteratively find shortest path from supply to demand nodes
• Push flow along cheapest augmenting path until capacity or demand reached
• Repeat until all supply/demand satisfied
• Time complexity: O(n2m log n) with Dijkstra

2. Cost Scaling (Refined)

• Maintains "price" dual variables at nodes
• Only uses edges with reduced cost close to 0
• Exponentially fewer iterations than Successive Shortest Path
• Time complexity: O(n log n × (m log n + nC)) for cost range C

3. Cycle Canceling

• Find negative-cost cycles and reduce flow on them
• Simple to implement, sometimes effective for small instances
• Useful as a local search improvement heuristic

4. Decomposition & Symmetry Breaking

• Decompose large networks into subproblems (e.g., by geographic regions)
• Fix flows on critical edges to reduce search space
• Exploit commodity structure if multi-commodity flows

Challenge Corner

Question: In many real logistics networks, you have multiple types of goods (commodities) flowing through the same network, each with different supply/demand and possibly different costs on the same edge.

• How would you model the Multi-Commodity Flow problem as a constraint satisfaction problem?
• Can you enforce that "certain commodities never share the same edge"? What propagation strategies would help?
• How does the problem complexity change from single-commodity to multi-commodity?

References

1. Ahuja, Magnanti, Orlin — Network Flows: Theory, Algorithms, and Applications (1993). Chapters 3–5 cover MCF algorithms in detail.
2. Goldberg & Tarjan — "Finding Minimum-Cost Circulations by Successive Approximation" (1989). Seminal work on cost-scaling algorithms.
3. Google OR-Tools Documentation — [Min Cost Flow Guide]((developers.google.com/redacted) Practical solver and examples.
4. DIMACS MCF Benchmark — Standard test instances for evaluating MCF solver performance.

---

Next Problem: Tomorrow we explore a fresh challenge in constraint satisfaction!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 9.78 AIC · ⊞ 5.7K · ◷

• expires on Aug 7, 2026, 4:10 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #49571.