p6 | Capacitated Warehouse Location Problem (CWLP)

See also

This problem is sourced from EvoCut.

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)

See also

This formulation is sourced from EvoCut.

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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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} \]