p6 | Capacitated Warehouse Location Problem (CWLP)

See also

This problem is sourced from EvoCut [2].

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\).

NP-hard: yes

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)

See also

This formulation is sourced from EvoCut [2].

Note

• This is the CWLP formulation from v1 of Yazdani et al. [2].

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC1).

Note

• This is the CWLP formulation from v1 of Yazdani et al. [2] augmented with the first lower bound of the proposed hybrid inequality (EC1).

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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_{\mathrm{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)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC2).

Note

• This is the CWLP formulation from v1 of Yazdani et al. [2] augmented with the second lower bound of the proposed hybrid inequality (EC2).

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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_{\mathrm{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)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC3).

Note

• This is the CWLP formulation from v1 of Yazdani et al. [2] augmented with the third lower bound of the proposed hybrid inequality (EC3).

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC1).

Note

• This is the CWLP formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC1.

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC2).

Note

• This is the CWLP formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC2.

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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 \mathcal{V}\), the total \(\lfloor u_j / v \rfloor\) slots across open warehouses must cover customers with demand \(\geq 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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC3).

Note

• This is the CWLP formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC3.

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC4).

Note

• This is the CWLP formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC4.

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC5).

Note

• This is the CWLP formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC5.

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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} \leq 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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC6).

Note

• This is the CWLP formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC6.

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
There is at least one customer.	\(n \geq 1\)	yes
There is at least one warehouse.	\(m \geq 1\)	yes
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} \]

Reformulations

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)

Note

• Formulation b has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → c (valid)

Note

• Formulation c has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → d (valid)

Note

• Formulation d has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → e (valid)

Note

• Formulation e has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → f (valid)

Note

• Formulation f has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → g (valid)

Note

• Formulation g has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → h (valid)

Note

• Formulation h has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → i (valid)

Note

• Formulation i has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)

a → j (valid)

Note

• Formulation j has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
d	\(d_{i} = d_{i}\)
u	\(u_{i} = u_{i}\)
f	\(f_{i} = f_{i}\)
c	\(c_{ij} = c_{ij}\)