4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I just realized that for symmetric graphs calculating $A^p(1\ 0\ .....\ 0 ) = (1\ 1\ ... \ 1) = x^p$ and $x^i = Ax^{i-1}$ under boolean algebra without calculating the intermediate matrices might be sufficient to lower the amount of variables but i don't think it will affect the asymptotic complexity, if it does that would be an acceptable solution. $\endgroup$ Oct 26, 2021 at 14:36
  • $\begingroup$ In game design, procedural layout problems are sometimes solved via optimization models. Typical constraints are that all rooms must be reachable (connected), and adjacency requirements are met. Side constraints, such as required sequences, can also be incorporated. For example, "Spatial Layout of Procedural Dungeons Using Linear Constraints and SMT Solvers" semanticscholar.org/paper/… $\endgroup$
    – Solver Max
    Oct 26, 2021 at 19:14
  • $\begingroup$ cs.stackexchange.com/q/159983/755 $\endgroup$
    – D.W.
    Sep 14 at 6:23

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Just to make sure, i don't want to verify properties of a (fixed) graph. I want to restrict the adjacency matrix of any graph (which i use in other constraints) such that it can only represent connected graphs and can represent all connected graphs. If you are proposing a formulation please write it out more explicitly, make it simple to count the number of terms and connect it to a adjacency matrix to that. I suppose the connection goes something like $-(p-1)A_{i,j}\leq x_{i,j}+x_{j,i} \leq (p-1)A_{i,j}$ but i don't want misinterpret your idea so a bit more detail would be appreciated. $\endgroup$ Oct 26, 2021 at 16:22
  • $\begingroup$ Do you mean this formulation: $$x \in [-(p-1),p-1]^p $$ $$ f_i = \begin{cases} p-1 & i=1 \\ -1 & i \neq 1 \\ \end{cases}$$ $$\forall j \in \{1,\ ...\ ,p-1\}: f_j + \sum_{i \in \{1,\dots,p-1\} } \text{sign}(i-j)*x_{i,j} = 0$$ $$\forall j \in \{1,\ ...\ ,p-1\}, i\in \{1,\ ...\ ,j-1\}: -(p-1)A_{i,j}\leq x_{i,j} \leq (p-1)A_{i,j} $$ $\endgroup$ Oct 26, 2021 at 17:36
  • $\begingroup$ @worldsmithhelper Are you assuming that all graphs have the same $p$ vertices, and differ only in which edges they have? $\endgroup$
    – prubin
    Oct 26, 2021 at 17:43
  • $\begingroup$ your assumption is correct. $\endgroup$ Oct 27, 2021 at 14:56
  • $\begingroup$ So if the incidence matrix $A$ is a variable, you can use the flow approach together with the constraints that $x_{ij}\le pA_{ij}$, which says you cannot have any flow over edges that do not exist. $\endgroup$
    – prubin
    Oct 27, 2021 at 16:08

Your Answer

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

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