---
tocdepth: 3
---

# p6 | Capacitated Warehouse Location Problem (CWLP)

```{seealso}
This problem is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- We add implicit assumptions that $|I|, |J| > 0$, $u, f, c \geq 0$, and $d > 0$.
- $d > 0$ is necessary for arguing $x_{ij} = 0$ when $y_j = 0$.
- EvoCut arXiv submission `v1` proposes a hybrid inequality combining three lower bounds. We split this hybrid inequality into three separate inequalities to generate formulations `p6.b-d`.
- EvoCut arXiv submission `v2` proposes a family of inequalities used to generate formulations `p6.e-j`.
```


## Description

The Capacitated Warehouse Location Problem (CWLP) involves selecting a subset of candidate warehouse locations to open and assigning each customer to one open warehouse. The problem is subjected to capacity constraints at each facility, with the goal of minimizing total fixed opening and transportation costs.

## Formulations
### Formulation `a` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- This is the MILP formulation given in Appendix F.3 of EvoCut arXiv submission `v1`.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `b` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC1).
```

```{note}
- Any two customers with demand exceeding half the maximum warehouse capacity cannot share a warehouse, so each such customer requires a distinct opened warehouse. This gives a simple lower bound on the number of warehouses that must be opened.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `u_max` | Maximum warehouse capacity. | $u_{\max} = \max_{j \in J} u_j$ |
| `k_crit` | Number of customers whose demand exceeds half the maximum warehouse capacity. Any two such customers cannot share a warehouse, so each requires a distinct opened warehouse. | $k_{\mathrm{crit}} = \big\| \{ i \in I : d_i > u_{\max} / 2 \} \big\|$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Critical-Customer Bound (EC1): at least k_crit warehouses must be opened.

  $$ \sum_{j \in J} y_j \geq k_{\mathrm{crit}} $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `c` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC2).
```

```{note}
- The total demand must be satisfied by the total capacity of opened warehouses. This gives a simple lower bound on the number of warehouses that must be opened.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `D` | Total demand across all customers. | $D = \sum_{i \in I} d_i$ |
| `k_dem` | Minimum number of largest-capacity warehouses whose capacities (taken in non-increasing order) sum to at least D. | $k_{\mathrm{dem}} = \min \Big\{ k \geq 0 : \sum_{\ell=1}^{k} u_{(\ell)} \geq D \Big\},\quad u_{(1)} \geq u_{(2)} \geq \cdots \geq u_{(m)}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Demand-Cover Bound (EC2): at least k_dem warehouses must be opened.

  $$ \sum_{j \in J} y_j \geq k_{\mathrm{dem}} $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `d` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC3).
```

```{note}
- Small warehouses are those with capacity less than the maximum customer demand. Hard customers are those whose demand exceeds the largest small-warehouse capacity, so they can only be served by large warehouses. To cover the hard customers, we need to open at least $k_T$ large warehouses, where $k_T$ is the minimum number of large warehouses whose capacities sum to at least the total demand of hard customers.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `T` | Set of large warehouses: those with capacity at least the maximum customer demand. | $T = \{ j \in J : u_j \geq \max_{i \in I} d_i \}$ |
| `u_max_small` | Maximum capacity among non-large (small) warehouses; 0 if all warehouses are large. | $u^{\text{small}}_{\max} = \max_{j \in J \setminus T} u_j \;\text{(} 0 \text{ if } J \setminus T = \emptyset \text{)}$ |
| `H` | Set of hard customers: those whose demand exceeds the largest small-warehouse capacity, so they can only be served by a large warehouse. | $H = \{ i \in I : d_i > u^{\text{small}}_{\max} \}$ |
| `D_H` | Total demand of hard customers. | $D_H = \sum_{i \in H} d_i$ |
| `k_T` | Minimum number of large warehouses whose capacities (taken in non-increasing order) sum to at least D_H. Equals 0 if H is empty. | $k_T = \min \Big\{ k \geq 0 : \sum_{\ell=1}^{k} u_{(\ell)} \geq D_H \Big\},\quad u_{(1)} \geq u_{(2)} \geq \cdots \text{ enumerating } \{u_j : j \in T\}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- T-Cover Bound (EC3): at least k_T warehouses must be opened.

  $$ \sum_{j \in J} y_j \geq k_T $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `e` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC1).
```

```{note}
- The total demand must be satisfied by the total capacity of opened warehouses. This gives a simple lower bound on the number of warehouses that must be opened.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Demand Coverage (EC1): total capacity of opened warehouses must cover total demand.

  $$ \sum_{j \in J} u_j \, y_j \geq \sum_{i \in I} d_i $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `f` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC2).
```

```{note}
- For every demand threshold $v$ corresponding to some customer demand, the total number of 'slots' of size $v$ across all open warehouses must be at least the number of customers with demand at least $v$. This gives a family of lower bounds on the number of warehouses that must be opened.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `V` | Set of distinct customer demand values, used as thresholds in the slot-count bounds. | $\mathcal{V} = \{ d_i : i \in I \}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Global Slot Count Bounds (EC2): for each demand threshold v in V, the total floor(u_j/v) slots across open warehouses must cover customers with demand >= v.

  $$ \sum_{j \in J} \left\lfloor \frac{u_j}{v} \right\rfloor y_j \geq |\{i \in I : d_i \geq v\}| \quad \forall v \in \mathcal{V} $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `g` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC3).
```

```{note}
- Customer $i$ can only be assigned to warehouse $j$ if $j$ is open.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Opening (EC3): customer i can only be assigned to warehouse j if j is open.

  $$ x_{ij} \leq y_j \quad \forall i \in I,\; \forall j \in J $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `h` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC4).
```

```{note}
- If customer $i$'s demand exceeds warehouse $j$'s capacity, customer $i$ cannot be assigned to warehouse $j$.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Assignment (EC4): if customer i's demand exceeds warehouse j's capacity, customer i cannot be assigned to warehouse j.

  $$ x_{ij} = 0 \quad \forall i \in I,\; j \in J \text{ with } d_i > u_j $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `i` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC5).
```

```{note}
- Every clique of customers who can not be assigned to the same warehouse introduce a lower bound on the number of warehouses that must be opened.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `C` | For each warehouse j, the lifted conflict set C[j]: start with customers whose demand exceeds u_j/2 (any two of them already conflict at j), then greedily add remaining customers — in non-increasing demand order — that conflict (sum exceeds u_j) with every already-included member. | $C_j = \{ i \in I : d_i > u_j / 2 \} \cup \{ i \text{ added greedily, non-increasing } d_i, \text{ s.t. } d_i + d_{i'} > u_j \;\forall i' \in C_j \} \quad \forall j \in J$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Warehouse Clique (EC5): for each warehouse j, the lifted conflict set C[j] satisfies sum_{i in C[j]} x_{ij} <= y_j.

  $$ \sum_{i \in C_j} x_{ij} \leq y_j \quad \forall j \in J $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$

### Formulation `j` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC6).
```

```{note}
- At most 2 customers with demand exceeding one-third of warehouse j's capacity can be assigned to warehouse j.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of customers | integer | *scalar* |
| `m` | Number of candidate warehouses | integer | *scalar* |
| `d` | Demand of customer i | continuous | `[n]` |
| `u` | Capacity of warehouse j | continuous | `[m]` |
| `f` | Fixed cost to open warehouse j | continuous | `[m]` |
| `c` | Transportation cost if all of customer i's demand is served by warehouse j (already accounts for d_i) | continuous | `[n, m]` |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if customer i is assigned to warehouse j, 0 otherwise | binary | `[n, m]` |
| `y` | 1 if warehouse j is opened, 0 otherwise | binary | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Demand of each customer is positive. | $d_i > 0 \quad \forall i \in I$ | yes |
| Capacity of each warehouse is non-negative. | $u_j \geq 0 \quad \forall j \in J$ | yes |
| Transportation cost for each customer-warehouse pair is non-negative. | $c_{ij} \geq 0 \quad \forall i \in I, j \in J$ | yes |
| Fixed cost to open each warehouse is non-negative. | $f_j \geq 0 \quad \forall j \in J$ | yes |


#### Constraints

- Each customer is assigned to exactly one warehouse.

  $$ \sum_{j \in J} x_{ij} = 1 \quad \forall i \in I $$

- Capacity: total demand assigned to each warehouse cannot exceed its capacity times whether it is open.

  $$ \sum_{i \in I} d_i \, x_{ij} \leq u_j \, y_j \quad \forall j \in J $$

- Warehouse Cover Inequality (EC6): at most 2 customers with demand exceeding one-third of warehouse j's capacity can be assigned to warehouse j.

  $$ \sum_{i \in I :\, d_i > u_j/3} x_{ij} \leq 2 \, y_j \quad \forall j \in J $$

#### Objective

Minimize the total fixed opening cost plus transportation cost.

$$ \min \sum_{j \in J} f_j \, y_j + \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij} $$