8
$\begingroup$

I have this problem described in natural language, and I was wondering whether it is relatable to any known problem.

I have a directed acyclic graph. Each node can host a "probe". If node $i$ hosts a probe, then node $i$ and all the nodes connected to $i$ are considered "probed". I have to place a number $p$ of probes to maximize the number of probed nodes.

It reminds me of a covering problem, but on a network: so I was wondering if there is something more specific about this or it is just a matter of abstracting the natural language description. I am mainly interested in MILP formulations, but other pointers are welcome as well.

Thanks

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ is the "dominating set" problem what you look for? en.wikipedia.org/wiki/Dominating_set $\endgroup$
    – Marco Lübbecke
    Commented May 20, 2020 at 9:30
  • 1
    $\begingroup$ @MarcoLübbecke: the only difference is, in the dominating set, all vertices have to be "probed". Here, the cardinality of the dominating set is known in advance, and we have to do our best with that number. So the final result can be different than a dominated set. $\endgroup$
    – Kuifje
    Commented May 20, 2020 at 10:29
  • $\begingroup$ I see, thanks for clarifying; then I would start from an ILP for dominating set and modify accordingly -- do you see how that could work? $\endgroup$
    – Marco Lübbecke
    Commented May 20, 2020 at 10:34
  • $\begingroup$ Yes indeed that makes a lot of sense ! $\endgroup$
    – Kuifje
    Commented May 20, 2020 at 12:07
  • $\begingroup$ Are only the direct neighbours of a probed node is probed or is it like a flow so that second, third... n-th hop neighbours are also probed? If the latter is true you can check influence maximization with reverse reachable sets concept and there are simpler maximal covering formulations. $\endgroup$
    – Evren Guney
    Commented May 21, 2020 at 21:20

1 Answer 1

Reset to default
2
$\begingroup$

Define a binary variable $p_{iv}$ for each node $v$, that takes value $1$ if and only if it is probed by probe $i$, a binary variable $\delta_{iv}$ that takes value $1$ if and only if probe $i$ is located on node $v$, and a binary variable $\omega_v$ that takes value $1$ if node $v$ is probed.

You want to maximize the number of probed nodes :

$$ \max \; \sum_{v} \omega_{v} $$ subject to: \begin{align*} \delta_{iv}+ p_{iu} &\le 1 &\forall v, \;\forall u \notin N_v , \; \forall i\\ \sum_v \delta_{iv} &=1 \quad &\forall i\\ \omega_v &\le \sum_i p_{iv} \quad &\forall v\\ p_{iv}, \delta_{iv}, \omega_v &\in \{0,1\} \quad &\forall v, \; \forall i\\ \end{align*}

The first constraint models the fact that if probe $i$ is located on node $v$, then it cannot probe all vertices that are not adjacent to $v$ ($N_v$ denotes $v$ and its neighbors). The second constraint states that a probe can only take one location. The last constraint links variables $p$ and $\omega$: a node is probed if it is probed by at least one probe.

There are probably better formulations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.