---
tocdepth: 3
---

# p20 | World Food Program Food Distribution

```{seealso}
This problem is sourced from [Ferchtandiker2025](https://github.com/nathan-ferchtandiker/LLMs-For-Optimization-Reformulations).
```

```{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)

```{seealso}
This formulation is sourced from [Ferchtandiker2025](https://github.com/nathan-ferchtandiker/LLMs-For-Optimization-Reformulations) (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)

```{seealso}
This formulation is sourced from [Ferchtandiker2025](https://github.com/nathan-ferchtandiker/LLMs-For-Optimization-Reformulations) (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) $$