1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

Given your definition of $x_{mi},$ we should have $m\in K_i \iff x_{mi}=1,$ and thus $H_m = \lbrace i: x_{mi}=1 \rbrace.$ So $\vert H_m \vert = \sum_i x_{mi}.$

As for $k$ being undefined, one possibility is to solve the model for a fairly large value of $k.$ If not all $k$ cliques are used, you can either accept the solution or, if it has too many cliques (meaning the combination of traffic light states would cause the drivers to freak out) try with a smaller $k$ and see if the problem remains feasible and the objective value is acceptable. If all cliques are used, trying increasing $k$ and see if the objective improves and the complexity remains acceptable. If the problem is infeasible, definitely increase $k.$

$\endgroup$
2
  • $\begingroup$ Thank you ! Makes sense. So constraint (3) becomes $\sum_{i,j}(z_{ij}+z_{ji})x_{mi}x_{mj}\ge \sum_i x_{mi}-1$, which needs some linearization. Correct? $\endgroup$
    – Kuifje
    Apr 23, 2023 at 19:54
  • $\begingroup$ Yes. Since (3) is a $\ge$ constraint, I think you can do this by introducing new variables $w_{ijm}$ for $i<j$, changing the LHS of (3) to $\sum_{i<j}w_{ijm}$ and adding the constraints $w_{ijm} \le z_{ij} + z_{ji},$ $w_{ijm} \le x_{mi}$ and $w_{ijm} \le x_{mj}.$ $\endgroup$
    – prubin
    Apr 23, 2023 at 22:19

Your Answer

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

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