This is a follow up question of this thread, in which it is asked how to model a circular layout of a given set of cliques of a graph, which represent simultaneous movements at an intersection.
@prubin proposed a model, which is satisfactory and elegant, but which relies on the fact that the right set of cliques are part of the given inputs:
Let $k$ be the number of cliques and let $H_m=\lbrace i : m\in K_i\rbrace$ for all movements $m\in M.$ Define binary variables $z_{ij}$ for all pairs of clique indices $i\neq j,$ where $z_{ij}=1$ will signal that clique $j$ follows clique $i$ in a clockwise traversal of your circle. Fix $z_{ii}=0$ for all $i$ (to simplify the indexing in what follows) and add the constraints $$\sum_{i=1}^k z_{ij} = 1\quad \forall j\in \lbrace 1,\dots, k\rbrace \tag{1}$$ and $$\sum_{j=1}^k z_{ij} = 1\quad \forall i\in \lbrace 1,\dots, k\rbrace \tag{2}$$ to ensure that every clique is preceded/followed by exactly one clique.
Now for each movement $m$ add the constraint $$\sum_{i,j\in H_m : i < j} ( z_{ij} + z_{ji}) \ge \vert H_m \vert - 1 \tag{3}$$
I would now like to know how to proceed if the cliques are not given as an input. That is, I would like to simultaneously define the cliques, and the circular layout. Note that considering all maximal cliques of the graph is not necessarily a good idea, as no circular layout may exist which such sets.
Adapting @prubin's model sounds possible with additional binary variables $x_{mi}$ that take value $1$ if and only if node/movement $m$ is part of clique $K_i$, and binary variables $y_i$ that take value $1$ if and only if clique $K_i$ is selected.
Every node/movement $m$ should be part of at least one clique: $$\sum_i x_{mi}\ge 1 \quad \forall v$$ Cliques should be well defined: $$ x_{mi}+x_{ni}\le y_i \quad \forall (m,n)\notin E, \;\forall K_i $$
Constraints (1) and (2) could be modified as follows:
$$\sum_{i=1}^k z_{ij} = y_j\quad \forall j\in \lbrace 1,\dots, k\rbrace \tag{1}$$ and $$\sum_{j=1}^k z_{ij} = y_i\quad \forall i\in \lbrace 1,\dots, k\rbrace \tag{2}$$
However I am unsure how to adapt constraint (3)?
Also, variables should be defined differently, as $k$ is undefined.
Is there a better approach than this?
