1
$\begingroup$

I have an MILP problem where I have to choose a set of vertices 'm' from complete set of vertices such that all the 'm' vertices are connected.

Assume there are a set of vertices numbered 1...n. Out of these vertices 'm' ($m <= n$) vertices have to be chosen. A matrix is available that describes the connectivity between the vertices. The constraint must ensure that all the chosen vertices are connected. For example consider there are 6 vertices with index i =1,2...6. And the connectivity matrix (undirected graph) is given by

$$ \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix} $$

Then a connected tree of only 4 vertices can be generated. And when m = 5 or 6, then no feasible solution exist.

Alternatively, if there are 5 vertices 1,2,3,4 and 5 with connectivity matrix $$ \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} $$ In this scenario, for m =4, vertices 1,2,4 and 5 is not a feasible solution. How to enforce this constraint in MILP ?

$\endgroup$

1 Answer 1

1
$\begingroup$

A common approach is to add (phantom) flows between selected vertices. One set of binary variables chooses your $m$ vertices. A second set of binary variables chooses one of the selected vertices to be the source of $m-1$ units of flow. A set of continuous variables represents flow between vertices. You want $m-1$ units to leave the selected source vertex, 1 unit to be consumed at every other selected vertex, and net flow to be zero at all other vertices. Nodes that were not selected cannot have any flow into or out of them.

$\endgroup$
1
  • $\begingroup$ Thanks. This solved the problem. $\endgroup$
    – DKumar
    May 10, 2023 at 5:00

You must log in to answer this question.

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