# Deriving a valid inequality

Given a set of facilities $$I$$ and days $$J$$, each facility $$i \in I$$ has a capacity of $$C_i$$, and a set of days $$J$$ where in each day $$j \in J$$ there's a total demand of $$q_j$$ that can be satisfied by one or more facilities.

To satisfy the daily demand facilities are opened. The number of opened facilities of type $$i$$ should be equivalent on all days, hence the global cost of opening one facility of type $$i$$ is $$h_{i}^{g} = |J|h_{i}$$. In addition, among the opened facilities, in each day $$j$$ a number of them can be canceled recovering the cost of opening one facility ($$h_i$$) and subject to a penalty ($$h^{'}_i$$) if the total number of canceled ones exceeds a certain threshold $$0 \leq \alpha \leq 1.0$$ (e.g percentage) of the total number of opened facilities of type $$i$$. Thus we have $$h^{'}_i < h_i < h_{i}^{g}$$.

The problem is to find the number of facilities of type $$i$$ to be opened in all days and the one to be canceled in each day $$j$$ while minimizing the total cost of opened, cancelled and penalized facilities.

Let the following integer variables be:
$$y_i$$ = Total number of opened facilities
$$x_{ij}$$ = number of canceled facilities of type $$i$$ in day $$j$$
$$w_i$$ = number of penalized facilities among the canceled ones
$$z_{ij}$$ = actual number of facilities of type $$i$$ used in day $$j$$ ($$z_{ij} = y_i - x_{ij}, \forall i,j)$$
$$d_{ij}$$ = amount sent from facility $$i$$ to satisfy the demand in day $$j$$.

The objective function minimizes: $$\sum_{i\in I} h_{i}^{g} y_i + \sum_{i\in I} h^{'}_i w_i - \sum_{i\in I,j\in J} h_i x_{ij}$$.

In addition we have the following constraints:
(1) $$\sum_{i} d_{ij} = q_{j}, \forall j$$ : demand satisfaction
(2) $$d_{ij} \leq C_i z_{ij}, \forall i,j$$: capacity constraints
(3) $$z_{ij} = y_i - x_{ij}, \forall i,j$$: actual number of used facilities $$i$$ in day $$j$$
(4) $$x_{ij} \leq y_i,\forall i,j$$: no cancellation if facility is not opened
(5) $$\sum_{j~\in{J}} x_{ij} - \beta y_{i} \leq w_{i} , \forall i$$: penalize only if total cancellation exceeds $$\alpha$$ percentage of total number of y_{i}. Concretely $$\beta = \alpha \times |{J}|$$, $$0 \leq \alpha \leq 1.0$$. For example $$\beta = 0.2$$ where $$\alpha = 10\%$$ and $$|{J}| =2$$. This constraint states that if:

1. $$\sum_{j~\in~{J}} x_{ij} - \beta y_{i} \leq 0 \rightarrow w_{i} =0, \forall i~\in~{I}$$
2. $$\sum_{j~\in~{J}} x_{ij} - \beta y_{i} > 0 \rightarrow w_{i} \geq \sum_{j~\in~{J}} x_{ij} - \beta y_{i}, \forall i~\in~{I}$$

Now imagine $$|I| = 2$$ such that $$C_0 = 50$$ and $$C_1 = 60$$, $$h_0 = 500$$, $$h_1 = 550$$, $$h^{'}_{0} =400$$, $$h^{'}_{1} =440$$. $$|J| = 2$$, $$q_0 = 75$$, $$q_1 = 110$$ and $$\beta = 0.2$$.

Given these parameters, the optimal solution of the LP relaxation is $$y_1 = 1.833333$$, $$x_{10} = 0.5833333$$, $$w_1 = 0.216667$$, $$d_{10} = 75$$, $$d_{11} = 110$$.

It's not difficult to find this given that if $$y_1 = 1.833333$$ then:
in day 0: $$C_1 \times y_1 = 60 \times 1.83333 = 110 - 75 = 35 => 35/60 =0.583333$$ which equals the cancellation
in day 1: $$C_1 \times y_1 = 60 \times 1.83333 = 110 - 110 = 0$$

then for constraint (5) : $$0.58333 - 0.366666 \leq 0.2166667$$

I am looking for a way to derive valid inequalities to cutoff this fractional solution (variables are integer) or to strengthen the formulation given the LP relaxation? or what is the right literature to look at to derive such cuts ? I am looking for network design problems with capacity expansion or elimination. Thank you.

• I suppose that you have a cost on your $w_i$ variables? Otherwise, your constraint does not satisfy your implication in 1.
– Sune
Commented Oct 9, 2023 at 11:29
• @MatheusDiógenesAndrade I edited my question in this regard.
– CHE
Commented Oct 13, 2023 at 8:41
• @CHE, is there any case in which an empty solution (zero-valued solution) wouldn't be the optimal? Since that, assigning a day to a facility (x_ij >= 1), updates the y_i, and thus, the term, at the objective function, h_i y_i - h''_i sum_j x_ij, always will be positive. Commented Oct 13, 2023 at 11:08
• @MatheusDiógenesAndrade an optimal solution never has an empty solution. Let $q_{ij}$=demand on day $j$ that can be satisfied by facility $i$ (can be more than one). $y_{i}$= number of opened facilities (same on all days), $x_{ij}$= number of canceled facilities on day $j$ of type $i$. Yes it's always positive because demand should be satisfied ($y_i$ >0 for at least one $i$). But if we choose the wrong facilities $x_{ij}$ increases and thus the penalization (we only penalize if $\forall i,\sum_{j}x_{ij} > \alpha |J| y_i$ (e.g. $\alpha$=20%) ). if needed I can provide a small example.
– CHE
Commented Oct 14, 2023 at 10:51