I have to model the following problem as an optimization problem with constant objecive function and I am stuck at one of the restrictions.
Say that we have an $n\times n$ table for a fixed $n$. We have to allocate a list of nodes on this table. The nodes are labelled with natural numbers (greater or equal to 1) that can be repeated. The restriction to the position (cell) of this nodes are the following:
- There can only be one node on each cell
- Every time a node is allocated in a cell, it is connected with an edge to all nodes in adjacent cells (horizontal, vertical or diagonal).
- The degree of each node (number of other nodes it is connected to) coincides with its label.
- The graph must be connected.
I have been able to model all the conditions except for the last one. The way I have done this is by defining variables $x_{ij}^k$ where $0\leq i,j\leq n+1$ and $1\leq k\leq n$ such that $x_{ij}^k=1$ if there is a node with label $k$ on the $(i,j)$ cell and $0$ otherwise. I have also added $x_{i0}^k=x_{0j}^k=x^k_{i,n+1}=x^k_{n+1,j}=0$ for convenience in the restriction to the degree of the nodes.
How can I specify the restrictions for the graph to be connected?
If I new in advance the number of nodes, say $m$, I know that if it is not connected, then there should be a connected component of at most $\lfloor \frac{m}{2}\rfloor$ nodes and I could write equations to detect whether there is a connected component with $l$ verticies for each $1\leq l\leq \lfloor \frac{m}{2}\rfloor$. However, this is not the case, I should be able to write all the restrictions before I know the input. But even if I new the amount of vertices, the number of equations for this approach would be huge, so it would be highly inefficient.
If it helps, and example where the set of solutions provides only provide disconnected graphs is an input of 4 nodes with label 1, as they would be paired in two connected components of 2 vertices each one. So, for this input, the problem should be infeasible.
This type of constraint appears in political districting problems. See Imposing contiguity constraints in political districting models for several formulations.