p20 | World Food Program Food Distribution

See also

This problem is sourced from Ferchtandiker2025.

Note

• We add implicit assumptions that all sets are non-empty and \(\mathrm{dem}_j, \mathrm{pc}_k, \mathrm{tc}_{ijk}, \mathrm{nutreq}_\ell, \mathrm{nutval}_{k\ell} \geq 0\).

Description

Optimizing Emergency Food Distribution for the World Food Program (WFP)

In crisis-affected regions—such as conflict zones, post-disaster areas, or drought-stricken communities—the World Food Program (WFP) faces the monumental task of delivering life-saving food aid to vulnerable populations. This requires balancing cost efficiency, logistical feasibility, and nutritional adequacy while navigating complex supply chains, unreliable infrastructure, and urgent time constraints.

Context and Challenges Logistical Complexity:

Fragile Infrastructure: Many regions lack reliable roads, with routes often disrupted by conflict, flooding, or landslides. Transshipment points (e.g., warehouses, temporary hubs) are critical but may have limited capacity.

Geographic Dispersion: Beneficiary camps are frequently located in remote or inaccessible areas, requiring multi-stage transportation (supplier → transshipment point → camp).

Cost Variability: Procurement costs for commodities vary by supplier, while transportation costs depend on distance, road conditions, and fuel availability.

Nutritional Needs:

Each beneficiary requires a daily ration that meets minimum nutritional standards.

Commodities differ in nutritional value; for example, rice provides carbohydrates but lacks certain micronutrients, necessitating a mix of foods.

Resource Constraints:

Limited funding demands strict cost control across procurement and transportation.

Political or security pressures may restrict access to certain suppliers or routes.

Key Objectives The WFP aims to design a food distribution plan that:

Minimizes Total Costs:

Reduce expenses from procuring commodities and transporting them through complex networks.

Guarantees Food Availability:

Ensure all beneficiary camps receive sufficient quantities of each commodity.

Meets Nutritional Standards:

Provide rations that collectively satisfy all nutrient requirements.

Operational Components Suppliers: Costs vary by location and commodity.

Transshipment Points: Intermediate hubs where food is consolidated, repackaged, or redirected. Bottlenecks must be avoided.

Beneficiary Camps: Final destinations where displaced populations receive food. Demand is determined by the number of people and required ration sizes.

Critical Constraints No Storage: No storage is assumed—food is immediately redirected.

Demand Fulfillment: Each camp must receive enough of every commodity to meet its calculated ration size.

Nutritional Adequacy: The combination of commodities in the ration must meet all nutrient thresholds.

Formulations

Formulation a (valid)

See also

This formulation is sourced from Ferchtandiker2025 (formulation id: efficient).

Note

• The efficient formulation is node-based with continuous flow variables \(F_{ijk}\) on graph edges.

• The original formulation was identified by FLARE to be invalid. Its procurement cost was \(\sum_{k \in K} \mathrm{pc}_k \sum_{j \in N_B} \mathrm{dem}_j R_k\), which depends only on the ration size \(R_k\), while the inefficient formulation charges procurement on the total amount shipped \(\sum_{p \in P} x_{pk}\). Since the demand constraint \(\sum_{i \in N} E_{ij} F_{ijk} \geq \mathrm{dem}_j R_k\) permits shipping in excess of \(\mathrm{dem}_j R_k\) without additional procurement penalty, the objectives are misaligned. To make this a valid reformulation, we charge procurement on the supplier outflow \(\sum_{s \in N_S} \sum_{j \in N} E_{S_s, j} F_{S_s, j, k}\).

Parameters

Name	Description	Type	Shape
nN	Total number of nodes in the supply network (suppliers, transshipment points, and beneficiary camps)	integer	scalar
nS	Number of supplier nodes	integer	scalar
nT	Number of transshipment nodes	integer	scalar
nB	Number of beneficiary camps	integer	scalar
nK	Number of food commodities	integer	scalar
nL	Number of nutritional requirements	integer	scalar
S	Supplier node indices: S[s] is the index in N of supplier s	integer	[nS]
T	Transshipment node indices: T[t] is the index in N of transshipment node t	integer	[nT]
B	Beneficiary camp node indices: B[j] is the index in N of beneficiary camp j	integer	[nB]
E	Adjacency matrix: 1 if a directed edge exists from node i to node j, 0 otherwise	binary	[nN, nN]
dem	Number of beneficiaries at each beneficiary camp	integer	[nB]
pc	Procurement cost per kg of each commodity	continuous	[nK]
tc	Transportation cost per kg of commodity k along the edge from node i to node j	continuous	[nN, nN, nK]
nutreq	Per-person nutritional requirement for each nutrient	continuous	[nL]
nutval	Nutritional value per kg of each commodity for each nutrient	continuous	[nK, nL]

Variables

Name	Description	Type	Shape / Indices
F	Amount of commodity k shipped from node i to node j (kg)	continuous	[nN, nN, nK]
R	Ration size per person of each commodity (kg)	continuous	[nK]

Assumptions

Description	Formulation	Implicit
There is at least one node.	\(n_N \geq 1\)	yes
There is at least one supplier node.	\(n_S \geq 1\)	yes
There is at least one transshipment node.	\(n_T \geq 1\)	yes
There is at least one beneficiary camp.	\(n_B \geq 1\)	yes
There is at least one commodity.	\(n_K \geq 1\)	yes
There is at least one nutrient.	\(n_L \geq 1\)	yes
Each supplier node index is a valid node index (in range [0, nN)).	\(S_s \in N \quad \forall s \in N_S\)	no
Each transshipment node index is a valid node index (in range [0, nN)).	\(T_t \in N \quad \forall t \in N_T\)	no
Each beneficiary camp node index is a valid node index (in range [0, nN)).	\(B_j \in N \quad \forall j \in N_B\)	no
The supplier, transshipment, and beneficiary node-class maps partition N (every node belongs to exactly one class).	\(N = N_S \sqcup N_T \sqcup N_B\)	no
The supplier, transshipment, and beneficiary node-class maps are each injective.	\(S, T, B \text{ are injective}\)	no
Number of beneficiaries at each camp is non-negative.	\(\mathrm{dem}_j \geq 0 \quad \forall j \in N_B\)	yes
Procurement cost per kg of each commodity is non-negative.	\(\mathrm{pc}_k \geq 0 \quad \forall k \in K\)	yes
Transportation cost along each arc for each commodity is non-negative.	\(\mathrm{tc}_{ijk} \geq 0 \quad \forall i,j \in N, k \in K\)	yes
Per-person nutritional requirement for each nutrient is non-negative.	\(\mathrm{nutreq}_l \geq 0 \quad \forall l \in L\)	yes
Nutritional value per kg of each commodity for each nutrient is non-negative.	\(\mathrm{nutval}_{kl} \geq 0 \quad \forall k \in K, l \in L\)	yes

Constraints

• Suppliers are pure sources: no inflow on incoming edges.

  \[ \sum_{i \in N} E_{i, S_s} F_{i, S_s, k} = 0 \quad \forall s \in N_S, k \in K \]

• Flow conservation at transshipment nodes for each commodity: total inflow equals total outflow (no storage).

  \[ \sum_{i \in N} E_{ij} F_{ijk} = \sum_{i \in N} E_{ji} F_{jik} \quad \forall j \in N_T, k \in K \]

• Beneficiaries are pure sinks: no outflow on outgoing edges.

  \[ \sum_{j \in N} E_{B_b, j} F_{B_b, j, k} = 0 \quad \forall b \in N_B, k \in K \]

• Each beneficiary camp receives at least its ration demand on incoming edges for each commodity.

  \[ \sum_{i \in N} E_{i,B_j} F_{i,B_j,k} \geq \mathrm{dem}_j R_k \quad \forall j \in N_B, k \in K \]

• The ration collectively satisfies all per-person nutritional requirements.

  \[ \sum_{k \in K} \mathrm{nutval}_{kl} R_k \geq \mathrm{nutreq}_l \quad \forall l \in L \]

• Flow support is acyclic per commodity: there exists a rank labeling that strictly increases along positive-flow edges. (implicit)

  \[ \forall k \in K, \exists r : N \to \mathbb{N}, \forall i, j \in N : E_{ij} = 1 \land F_{ijk} > 0 \implies r_i < r_j \]

• Flow is supported on graph edges: no flow on non-edges. (implicit)

  \[ E_{ij} = 0 \implies F_{ijk} = 0 \quad \forall i,j \in N, k \in K \]

• Flow on each arc for each commodity is non-negative. (implicit)

  \[ F_{ijk} \geq 0 \quad \forall i,j \in N, k \in K \]

• Ration size per person of each commodity is non-negative. (implicit)

  \[ R_k \geq 0 \quad \forall k \in K \]

Objective

Minimize total procurement cost plus total transportation cost. Procurement cost is charged on the outflow of each commodity leaving supplier nodes.

\[ \min \sum_{k \in K} \mathrm{pc}_k \left( \sum_{s \in N_S} \sum_{j \in N} E_{S_s, j} F_{S_s, j, k} \right) + \sum_{i \in N} \sum_{j \in N} \sum_{k \in K} \mathrm{tc}_{ijk} F_{ijk} \]

Formulation b (valid)

See also

This formulation is sourced from Ferchtandiker2025 (variation id: inefficient).

Note

• The inefficient formulation is path-based.

• Proving this is a valid reformulation requires introducing many assumptions that relate the path-based parameters to the underlying supply network structure of the efficient formulation. These assumptions ensure the set of paths is well-formed and allows for a flow-decomposition argument.

Parameters

Name	Description	Type	Shape
nN	Total number of nodes in the supply network (suppliers, transshipment points, and beneficiary camps)	integer	scalar
nS	Number of supplier nodes	integer	scalar
nT	Number of transshipment nodes	integer	scalar
nB	Number of beneficiary camps	integer	scalar
nP	Number of simple paths from a supplier to a beneficiary camp	integer	scalar
nK	Number of food commodities	integer	scalar
nL	Number of nutritional requirements	integer	scalar
S	Supplier node indices: S[s] is the index in N of supplier s	integer	[nS]
T	Transshipment node indices: T[t] is the index in N of transshipment node t	integer	[nT]
B	Beneficiary camp node indices: B[j] is the index in N of beneficiary camp j	integer	[nB]
E	Adjacency matrix: 1 if a directed edge exists from node i to node j, 0 otherwise	binary	[nN, nN]
pE	Path-edge indicator: 1 if edge (i, j) is part of path p, 0 otherwise	binary	[nP, nN, nN]
pRank	Rank/position of node v within path p; strictly increases along path edges	integer	[nP, nN]
c	Shipping cost per kg of commodity k along path p	continuous	[nP, nK]
q	Procurement cost per kg of commodity k	continuous	[nK]
nutval	Nutritional value per kg of commodity k for nutrient l	continuous	[nK, nL]
nutreq	Per-person nutritional requirement for nutrient l	continuous	[nL]
dem	Number of beneficiaries at beneficiary camp j	integer	[nB]
e	Indicator: 1 if path p ends at beneficiary camp j, 0 otherwise	binary	[nB, nP]

Variables

Name	Description	Type	Shape / Indices
x	Amount of commodity k shipped along path p (kg)	continuous	[nP, nK]
R	Ration size per person of each commodity (kg)	continuous	[nK]

Assumptions

Description	Formulation	Implicit
There is at least one node.	\(n_N \geq 1\)	yes
There is at least one supplier node.	\(n_S \geq 1\)	yes
There is at least one transshipment node.	\(n_T \geq 1\)	yes
There is at least one beneficiary camp.	\(n_B \geq 1\)	yes
There is at least one commodity.	\(n_K \geq 1\)	yes
There is at least one nutrient.	\(n_L \geq 1\)	yes
Each supplier node index is a valid node index (in range [0, nN)).	\(S_s \in N \quad \forall s \in N_S\)	no
Each transshipment node index is a valid node index (in range [0, nN)).	\(T_t \in N \quad \forall t \in N_T\)	no
Each beneficiary camp node index is a valid node index (in range [0, nN)).	\(B_j \in N \quad \forall j \in N_B\)	no
The supplier, transshipment, and beneficiary node-class maps partition N (every node belongs to exactly one class).	\(N = N_S \sqcup N_T \sqcup N_B\)	no
The supplier, transshipment, and beneficiary node-class maps are each injective.	\(S, T, B \text{ are injective}\)	no
Each path edge must be a graph edge.	\(pE_{p,i,j} \leq E_{ij} \quad \forall p \in P, i, j \in N\)	yes
Within each path, every node has in-degree at most 1.	\(\sum_{i \in N} pE_{p,i,v} \leq 1 \quad \forall p \in P, v \in N\)	yes
Within each path, every node has out-degree at most 1.	\(\sum_{j \in N} pE_{p,v,j} \leq 1 \quad \forall p \in P, v \in N\)	yes
Each path has a unique source node (in-degree 0, out-degree 1) and that node is a supplier.	\(\forall p \in P, \exists! v \in N : \sum_{j \in N} pE_{p,v,j} = 1 \land \sum_{i \in N} pE_{p,i,v} = 0; \text{ moreover } v \in \{S_s : s \in N_S\}\)	yes
Each path has a unique sink node (in-degree 1, out-degree 0) and that node is a beneficiary camp.	\(\forall p \in P, \exists! v \in N : \sum_{i \in N} pE_{p,i,v} = 1 \land \sum_{j \in N} pE_{p,v,j} = 0; \text{ moreover } v \in \{B_b : b \in N_B\}\)	yes
End indicator e is consistent with pE: e_{j,p} = 1 iff path p ends at beneficiary camp j.	\(e_{j,p} = \sum_{i \in N} pE_{p,i,B_j} - \sum_{k \in N} pE_{p,B_j,k} \quad \forall j \in N_B, p \in P\)	yes
Each path is acyclic: rank strictly increases along path edges.	\(pE_{p,i,j} = 1 \implies pRank_{p,j} = pRank_{p,i} + 1 \quad \forall p \in P, i, j \in N\)	yes
Path indexing is complete: every valid simple supplier-to-beneficiary path is indexed by some p in P.	\(\forall \text{ valid simple } S\text{-to-}B \text{ path } \pi, \exists p \in P : pE_p = \pi\)	yes
Path indexing is injective: distinct path indices give distinct edge sets.	\(p_1 \neq p_2 \implies \exists i, j \in N : pE_{p_1,i,j} \neq pE_{p_2,i,j}\)	yes
Shipping cost along each path for each commodity is non-negative.	\(c_{pk} \geq 0 \quad \forall p \in P, k \in K\)	yes
Procurement cost per kg of each commodity is non-negative.	\(q_k \geq 0 \quad \forall k \in K\)	yes
Nutritional value per kg of each commodity for each nutrient is non-negative.	\(\mathrm{nutval}_{kl} \geq 0 \quad \forall k \in K, l \in L\)	yes
Per-person nutritional requirement for each nutrient is non-negative.	\(\mathrm{nutreq}_l \geq 0 \quad \forall l \in L\)	yes
Number of beneficiaries at each camp is non-negative.	\(\mathrm{dem}_j \geq 0 \quad \forall j \in N_B\)	yes

Constraints

• Each beneficiary camp receives at least its ration demand from paths ending there for each commodity.

  \[ \sum_{p \in P} e_{jp} x_{pk} \geq \mathrm{dem}_j R_k \quad \forall j \in N_B, k \in K \]

• The ration collectively satisfies all per-person nutritional requirements.

  \[ \sum_{k \in K} \mathrm{nutval}_{kl} R_k \geq \mathrm{nutreq}_l \quad \forall l \in L \]

• Amount shipped along each path for each commodity is non-negative. (implicit)

  \[ x_{pk} \geq 0 \quad \forall p \in P, k \in K \]

• Ration size per person of each commodity is non-negative. (implicit)

  \[ R_k \geq 0 \quad \forall k \in K \]

Objective

Minimize total shipping cost plus total procurement cost.

\[ \min \sum_{p \in P} \sum_{k \in K} c_{pk} x_{pk} + \sum_{k \in K} q_k \left( \sum_{p \in P} x_{pk} \right) \]