🧩 Constraint Solving POTD:Problem of the Day: Supply Chain Network Design

[github-actions[bot]]

Problem Statement

Supply chain network design is the problem of deciding where to locate facilities (warehouses, distribution centers, factories) and how to route goods through them to meet customer demand while minimizing total cost.

Concrete Instance

Imagine you operate an e-commerce business with:

• 3 potential warehouse locations: New York (cost: $50K/month), Chicago ($40K/month), Los Angeles ($45K/month)
• 4 customer regions: Northeast (demand: 100 units), Midwest (80 units), Southwest (60 units), West Coast (70 units)
• Transportation costs (per unit): from each warehouse to each region varies
• Capacity constraints: each warehouse can serve at most 150 units/month
• Demand constraints: every region must receive exactly its required demand

Decision: Which warehouses should you open, and how should you ship goods from warehouses to customer regions?

Output: A feasible solution specifying which warehouses are active, the flow from each warehouse to each region, and the total monthly cost.

---

Why It Matters

Real-world applications of supply chain network design are everywhere:

• Retail & E-commerce: Amazon, Walmart, and others must decide where to place distribution centers across continents to minimize delivery times and shipping costs while handling seasonal demand spikes.
• Manufacturing: Auto suppliers and electronics manufacturers design multi-tier networks (raw materials → factories → regional warehouses → customers) to balance production efficiency, inventory holding, and logistics.
• Humanitarian Logistics: NGOs and disaster-relief organizations use network design to pre-position supplies efficiently during emergencies, minimizing response time to affected regions.

Every major enterprise faces this problem; solving it even 1% better can save millions annually.

---

Modeling Approaches

Approach 1: Mixed-Integer Linear Programming (MILP)

Paradigm: Optimization via linear algebra.

Key variables:

• y_i ∈ {0, 1} — binary indicator: is warehouse i open?
• x_{ij} ≥ 0 — continuous flow: units shipped from warehouse i to region j

Constraints:

• Demand satisfaction: Σ_i x_{ij} = demand_j for each region j
• Supply capacity: Σ_j x_{ij} ≤ capacity_i · y_i for each warehouse i
• Facility costs: cost = Σ_i (fixed_cost_i · y_i) + Σ_{ij} (unit_cost_{ij} · x_{ij})

Objective: Minimize total cost.

Trade-offs:

• ✅ Expressiveness: Exact optimal solutions via branch-and-bound
• ✅ Scalability: Solves problems with thousands of warehouses and regions
• ❌ Propagation: Linear relaxation alone is weak; requires cutting planes and branch-and-bound depth

Approach 2: Constraint Programming with Global Constraints

Paradigm: Declarative constraint satisfaction with specialized propagators.

Key variables:

• warehouse_open[i] ∈ {0, 1} — is facility i open?
• route[j] ∈ {1..m} — which warehouse serves region j?
• flow[i][j] ∈ [0, capacity_i] — flow on route (i, j)

Constraints:

• Global cardinality: ensure each region is assigned to exactly one warehouse
• Cumulative capacity: cumulative([flow[i][j] for all j], capacity_i · warehouse_open[i])
• Routing consistency: if region j is routed to warehouse i, then warehouse_open[i] = 1
• Channel constraints: link assignment decisions to flow variables

Trade-offs:

• ✅ Propagation: Global constraints (cumulative, element, table) prune search space aggressively
• ✅ Flexibility: Easy to add complex side constraints (e.g., supplier availability, regulatory zones)
• ❌ Scalability: Search can explode if routing decisions are naive; needs good variable ordering

Approach 3: Lagrangian Relaxation + Subgradient Optimization

Paradigm: Decomposition and bounds.

Key idea: Relax complicating constraints (e.g., demand satisfaction) into the objective via Lagrange multipliers λ_j. This decomposes the problem into independent warehouse sub-problems. Iteratively update multipliers using subgradient descent to tighten the bound and steer toward feasibility.

Trade-offs:

• ✅ Bounds: Generates strong dual bounds quickly
• ✅ Heuristics: Sub-problem solutions give feasible primal candidates
• ❌ Convergence: Subgradient methods can be slow; requires tuning step sizes and stopping criteria

Example Model (Pseudo-code)

# Simplified Supply Chain Network Design in pseudo-code
maximize/minimize total_cost

variables:
  y[i] in {0, 1}                    # Warehouse i open?
  x[i][j] >= 0                      # Flow from warehouse i to region j

# Facility opening and capacity
for each warehouse i:
  capacity_used[i] = sum(x[i][j] for all j)
  capacity_used[i] <= max_capacity[i] * y[i]

# Demand satisfaction
for each region j:
  demand[j] = sum(x[i][j] for all i)

# Objective
total_cost = sum(fixed_cost[i] * y[i] for all i)
           + sum(unit_cost[i][j] * x[i][j] for all i, j)

constraints:
  y[i] in {0, 1}
  x[i][j] >= 0
  sum(x[i][j] for all i) = regional_demand[j]  for each j

---

Key Techniques

1. Facility Location Relaxation & Dual Decomposition

Rather than solve the full network problem, many practitioners first solve a relaxed sub-problem: "If I decide which warehouses to open, what's the minimum cost to satisfy all demand?" This decomposition often yields tight bounds. Lagrangian relaxation iteratively refines multiplier estimates, guiding search toward good solutions.

2. Variable Ordering for Assignment & Routing

Smart variable selection dramatically accelerates search. Typical ordering:

1. First: decide warehouse opening (y_i) — high impact, low branching factor
2. Then: assign regions to warehouses — propagates capacity constraints
3. Finally: optimize detailed flows — often reduced to linear sub-problems

Good heuristics include minimum remaining values (MRV) and impact-based ordering.

3. Symmetry Breaking & Problem Reduction

Multiple optimal solutions often exist (e.g., opening warehouses {A, B} vs. {B, A}). Add symmetry-breaking constraints:

• y_1 ≥ y_2 ≥ y_3 ≥ ... ≥ y_m (impose order on warehouse decisions)
• Reduce by merging equivalent candidate sites (e.g., two warehouses with identical cost and capacity)

---

Challenge Corner

Can you extend this problem to handle:

1. Uncertainty: Customer demand is forecast with a ±20% margin of error. How would you model this as a stochastic network design problem? Consider scenario-based approaches or robust optimization.

2. Multi-commodity flows: You ship multiple product types (electronics, textiles, perishables) with different handling requirements and costs. How does introducing commodity-specific warehouse capabilities change the modeling complexity?

3. Time-phased decisions: Demand varies seasonally. How would you model opening/closing warehouses over a 12-month horizon while minimizing switching costs and respecting lead times?

4. Symmetry reduction: Given 10 candidate locations, how many symmetry-breaking constraints are sufficient to eliminate redundant solutions without losing optimality?

---

References

1. Daskin, M. S. (2011). Network and Discrete Location: Models, Algorithms, and Applications (2nd ed.). Wiley. — A comprehensive reference covering facility location, hub location, and network design.

2. Melo, M. T., Nickel, S., & Saldanha-da-Gama, F. (2009). "Facility location and supply chain management – A review." European Journal of Operational Research, 196(2), 401–412. — Survey of models, algorithms, and industrial applications.

3. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Springer. — Chapter on decomposition methods and Lagrangian relaxation applied to logistics.

4. OR-Tools Supply Chain Documentation: (developers.google.com/redacted) — Practical solvers and modeling tutorials for real-world network design problems.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 12.4 AIC · ⌖ 7.65 AIC · ⊞ 6.5K · ◷

• expires on Oct 27, 2026, 3:37 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 #70852.