# Set Cover and additional constraints

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.

• Phew. That's a lot of text to read. I'm struggling to identify what your specific question is. You listed 4 types of constraints you want to enforce. Which ones do you already known how to enforce? Is there one that you don't know how to enforce? What is the intended meaning of your variables $x_k$? $y_j$? $z_i$? It would help to state that explicitly. I don't know what you mean by "connect $z_i$ with $y_i$ and resources". I also don't know what $i:s$ or $j:w$ or $k:e$ mean. – D.W. Mar 27 '17 at 23:33
• Added extra information that should answer your questions. If anything still unclear feel free to ask i will explain :) – user1812 Mar 28 '17 at 0:00

## 1 Answer

Once you've defined the variables $x_{ij},y_j,z_i$, all you need to do is add ILP constraints that enforce the domain requirements. The general approach is: write down the list of domain requirement, then go through them one-by-one, and for each, translate it to ILP.

What are the domain requirements? First, if you open store $j$, then you must enable a set of edges that are sufficient to provide all the resources that store $j$ needs. Second, if you enable an edge between some warehouse and some store, then that warehouse must be opened.

Now we express each of the domain requirements as ILP. Here is how we express the first domain requirement. For each store $j$ and each resource $r$ required by store $j$, we require

$$\sum_{j \in S_r} x_{ij} \ge y_j,$$

where $S_r$ is the set of warehouses that supply resource $r$. This ensures that, for each resource $r$ needed by store $j$, if you open store $j$, then you must enable at least one edge that can supply resource $r$ to store $j$.

Enforcing the second domain requirement is relatively straightforward, once you know that you can represent a logical implication as a less-than-or-equal constraint. For each warehouse $i$ and each store $j$, we require

$$z_i \ge x_{ij}.$$

This ensures that if you enable an edge, then the corresponding warehouse needs to be open.

Now you ask the ILP solver to find an assignment that satisfies all of these inequalities, and minimizes the value of the objective function.