Set Cover and additional constraints

Question

Consider the following bipartite graph:

Each node in red color represents a warehouse $w = \{ 1,2,3\} $. For this example we have three warehouses located at different locations. Each warehouse has a cost of opening ${c_w} = \{ 7,8,10\} $ for all $w$. In addition to that, each warehouse provides different resources ${r_1},{r_2}$ or ${r_3}$ required for stores that they have connection to be opened.

Each node in blue color is a store $s = \{ 1,2,3,4,5\} $. We have five stores for this example. Each store has its opening cost ${c_s} = \{ 9,11,12,10,8\} $ for all $s$. In addition to that each store requires some resources that can be provided by one or more warehouses it is connected to.

Each edge between store and warehouse has some cost. You can think about it as a distance from store location to a warehouse location. Thus, in order to open a store ${s_i}$ it should be connected to one or more warehouses which, together provide resources that ${s_i}$ needs.

The problem is to find a subset of possible warehouses, a subset of possible stores, and a plan to serve each open store by a list of connected open warehouses. Our goal is to compute the total profit from opened stores minus the total cost from opening warehouses and servicing open stores using those open warehouses is maximized.

For this example, the optimal plan:

• Open $w = 1$, provide ${r_1}$ to $s = 1$, then open it.
• Open $w = 2$, provide $\{ {r_1},{r_2}\} $ to $s = 2$, then open it.
• Open $s = 3$, by providing resources from $w = \{ 1,2\} $

Thus, we opened 2 warehouses $w = \{ 1,2\} $ that provided resources for $s = \{ 1,2,3\} $, which we decided to open and we used only 4 edges. The optimal profit for this example is ${p_{OPT}} = 9 + 11 + 12 - (7 + 8 + 3 + 3 + 3 + 4) = 4$

Now the task is to model this problem as mixed integer programming, more specifically i think using binary variables i have to define the objective function and all required constraints, also stating new variables.

I have noticed that each ${r_s}$ can be considered a universe set and each ${r_w}$ or union of ${r_w}$s must cover ${r_s}$. This problem, was definitely, designed with a flavor of set covering. However, it was made more complicated by adding extra constraints.

I need to model this problem as MIP. So far, i managed to determine the objective function and came up with some constraints that allow me to chose edges to warehouses that cover the store resources.

My objective function: $$\max :\sum\nolimits_{i:s} {{c_s}} {z_i} - \left( {\sum\nolimits_{j:w} {{c_w}{y_j} + \sum\nolimits_{k:e} {{c_e}{x_k}} } } \right)$$where ${z_i},{y_j},{x_k}$ - binary values and ${c_e}$ is the cost of edge.

Ok, since this example is short i will write my objective function in expanded form so it becomes clear about my notation:

My objective function (expanded form): $\max :9{z_0} + 11{z_1} + 12{z_2} + 10{z_3} + 8{z_4} - 7{y_0} - 8{y_1} - 10{y_2} - 3{x_{00}} - 5{x_{01}} - 3{x_{02}} - 3{x_{11}} - 4{x_{12}} - 5{x_{13}} - 7{x_{22}} - 6{x_{23}} - 4{x_{24}};$

• ${z_i} = 0$ if we don't open store $s = i$ and ${z_i} = 1$ otherwise
• ${y_i} = 0$ if we don't open warehouse $w = i$ and ${y_i} = 1$ otherwise
• ${x_{ij}}$ means edge from store $j$ to warehouse $i$.
• ${x_{ij}} = 0$ if we don't use it and ${x_{ij}} = 1$ otherwise

Now i'm trying to set the following constraints:

1. For each ${s_i}$, i consider ${r_{{s_i}}} = U$ that is a universe set for which i should cover each element.
2. Then i apply $\sum\nolimits_{S:v \in S} {{y_S} \ge 1,\,\,\forall v \in U} $, that is i pick 1 element from $U$ and determine which adjacent ${r_{{w_j}}}$ can cover it.
3. For each resource required by store, it is covered by one or more sets from 2.
4. Then i ensure that store is opened if all of its resources are covered by reachable warehouse(s)

Here is my constraint examples for $s = 2 $.

Case $s = 2$:

Denote ${y_{ij}}$ a warehouse $i$ resource set that covers first element from the resource set of store $j$, ${z_j}$ - opening store $j$, ${r_{kj}}$ - required resource ${r_k}$ from store $j$. All indexes starting from 0. Now i have

$$\begin{gathered} {y_{01}} + {y_{11}} \ge1; \hfill \\ {y_{11}} \ge 1; \hfill \\ {r_{11}} \le {y_{01}} + {y_{11}}; \hfill \\ {r_{11}} \ge {y_{01}}; \hfill \\ {r_{11}} \ge {y_{11}}; \hfill \\ {r_{21}} \le {y_{11}}; \hfill \\ {r_{21}} \ge {y_{11}}; \hfill \\ {z_1} \ge {r_{11}} + {r_{21}} - 1; \hfill \\ {z_1} \le {r_{11}}; \hfill \\ {z_1} \le {r_{21}}; \hfill \\ \end{gathered} $$

In a first line i determine that ${r_1}$ is contained in ${w_1}$ and ${w_2}$ sets. The second required resource ${r_2}$ is only in ${w_2}$ set. Then i ensure that either one or both sets cover ${r_1}$ same with ${r_2}$. Finally i want to make sure that store can be opened if all resources can be supplied by warehouse. Now from this point i do something wrong because ${z_i}$ is always 1 if some reachable warehouse(s) can cover all resources. So basically with this encoding the solver always sets ${z_i}$ and i need to somehow link ${z_i}$ with warehouse opening. I guess instead of using ${z_i}$ to check if all resources can be obtained i need to introduce another dummy variable say $a$ and define a constraint something like: $a \to {\text{ some }}{w_i}$

As you can see from my constraints i'm missing a link between ${z_i},{y_j},{x_{ij}}$. I managed to create a set of constraints that answer the question: Can any warehouse or their union cover all resources needed by some store. If they do ${z_i}$ is always set to 1 and i don't want it to be necessary set to 1 if the resource set is covered. What i need is to add some logic that will force the objective function to choose weather to open ${z_i}$ and what ${y_j}$ and ${x_{ij}}$ should be set to 0/1 in order to maximize the objective function.