Constrain Mixed-Integer problem such that a graph is fully connected

Question

I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are implied by other constraints.

Let $A^m_{i,j}$ be the entries of the $m$-th power of of the $p\times p$ adjacency matrix where $A^{n+l}_{i,j} = \bigvee_{m\in\{1,..,p\}}\ A^n_{i,m} \wedge A^l_{m,j}$ as the boolean algebra suggests. If $\sum_{m\in\{1,..,p\}} A^m_{i,j}$ is non zero in every $i,j$ then the graph is fully connected. We exploit the fact that the matrices are boolean to express the products that occur in the matrix in a MILP framework. However that means we have order at least $O(p^4)$ "$A^n_{i,m} \wedge A^l_{m,j}$" terms which i am afraid will scale poorly.

Could you suggest some alternative formulation with convex relaxations that might scale better and can be solved using standard solvers?

I am aware of another approach using the eigenvalues of the graph Laplacian matrix $L$. However i haven't been able to put this approach into a single level MILP problem. I vaguely recall that cone programming might help. The Laplacian might be able to be replaced by the Incidence Matrix for this to make representation easier.

Answer 1

If you are looking for a way to ensure (in a MILP model) that a graph with $p$ nodes is connected, a common approach is to treat each edge as a pair of directed edges (adding flow variables $x_{ij}$ and $x_{ji}$ for each edge $(i,j)$, choose one node arbitrarily to have supply $p-1$ of a phantom commodity, and assign a demand of $1$ to every other node. You then add the usual flow balance constraints (flow out of node = flow into node - 1). Feasibility of the flow constraints guarantees a path from the source node to every other node, meaning the graph is connected.