Right now, we calculate implicit coverage per manifest. This is not very precise, as implicit coverage is dependent on the existence of (selection of) manifests in the final solution. For example, if m1 is implicitly protecting m2 and m3 yielding a coverage K, K holds true only when m1, m2, and m3 are selected in the ILP solution.
The idea is to model edges between manifests as variables. We further use constraints to model the relation between edges and nodes. That is, e0 (denoting the edge between m1, and m2) is set to 1 if and only if both m1 and m2 are selected. To achieve this we use the follwoing constraint:
0 <= m1 + m2 -2 e0 <= 1
The aforementioned constraint ensure that e0 can be set to 1 when both m1 and m2 are set to 1.
After adding all the edges between manifests in the graph that way, we set the implicit coverage, i.e. K for every edge in the graph (like before). However, we set implicit coverage to 0 for other variables (m0,..., m_n).
After this modification, we can optimize for implicit coverage as well.
mr-ma
commented
5 years ago
Right now, we calculate implicit coverage per manifest. This is not very precise, as implicit coverage is dependent on the existence of (selection of) manifests in the final solution. For example, if
m1is implicitly protectingm2 and m3yielding a coverageK,Kholds true only whenm1, m2, and m3are selected in the ILP solution. The idea is to model edges between manifests as variables. We further use constraints to model the relation between edges and nodes. That is,e0(denoting the edge betweenm1, andm2) is set to1if and only if bothm1andm2are selected. To achieve this we use the follwoing constraint:0 <= m1 + m2 -2 e0 <= 1The aforementioned constraint ensure that e0 can be set to1when bothm1 and m2are set to1.After adding all the edges between manifests in the graph that way, we set the implicit coverage, i.e.
Kfor every edge in the graph (like before). However, we set implicit coverage to0for other variables (m0,..., m_n).After this modification, we can optimize for implicit coverage as well.