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.