2
$\begingroup$

I have a mixed-integer linear program (MILP) that needs to select some edges from a graph according to some metrics.

One constraint that I'd like to enforce is that two given nodes have to be connected (i.e. there must exist a path between them).

looking at the adjacency matrix I know that one can find the shortest path or even all the possible path using some algorithms like breadth first search and even Dijkstra.

My question is: given that I do not want to know the path, can I formulate this ''path existence/connectivity problem'' as a constraint for a MILP problem?

The best idea I had was to compute all the paths connecting the two vertices offline and force the selection of at least one of those. Which would work, but it's something really inelegant.

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $y_j$ be real variables indexed by the nodes of your graph, with $y_a = 0$ and constraints $y_j = y_k$ if $(j,k)$ is an edge. Then nodes $a$ and $b$ are connected iff this implies $y_b = 0$. Thus if you impose an upper bound of $1$ to keep things finite, and maximize $y_b$, an optimal solution has $y_b = 0$ if they are connected and $1$ if they are not.

$\endgroup$
4
  • $\begingroup$ this seems to be a very clever solution. I'm still figuring it out tho. what do you mean with ''and 0 if they are not''? did you want to say 1? $\endgroup$ Mar 24, 2017 at 22:21
  • $\begingroup$ Yes, thanks. Edited it. $\endgroup$ Mar 24, 2017 at 23:13
  • $\begingroup$ I studied it for a bit and I really like this solution. Thanks a lot! does this procedure have a name? getting your reply after like 5 minutes makes me think this is a known problem. $\endgroup$ Mar 24, 2017 at 23:19
  • $\begingroup$ sorry to bother you again, but would you have a look at this other question? I realised that this method is not easily extended to actually imposing the existence of the connection. math.stackexchange.com/questions/2205124/… thanks $\endgroup$ Mar 27, 2017 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .