In [1] the following problem is proposed:

- Consider a complete (undirected) graph,
- where each arc has a weight.
- Given a collection of colors,
**color each node,** **such that the sum of the weights of arcs with same-colored nodes is minimized**.- We can assume some sparsity in the weights.

The user expects the number of nodes to be between 20 and 50, and there are just a small number of colors.

Minimize weights for the colored arcs |

The picture shows a complete graph (all nodes have a direct arc to each other) with 10 nodes. The optimal coloring of nodes minimizes the sum of weights along the colored edges. An edge is colored if the two incident nodes have the same color.

#### Data

The first thing I always do when confronted with a problem like this is to form a data set. This is a very useful exercise: it forces you to get a reasonable understanding of the problem. More than just casual reading of some text.

- Say we have \(n=50\) nodes.
- As we are dealing with an undirected graph, I'll create arcs \(i-j\) only for \(i \lt j\). So we have 1,225 arcs. The set of arcs is called \(\color{darkblue}a_{i,j}\).
- I form weights \(\color{darkblue}w_{i,j}\) as follows:
- With probability 0.75, the weight is zero
- The other weights are uniformly distributed from \(U(0,1)\)
- I use \(k=5\) colors.

#### Model

MIQP Model |
---|

\[\begin{align} \min & \sum_{\color{darkblue}a_{i,j},c} \color{darkblue}w_{i,j} \cdot \color{darkred}x_{i,c} \cdot \color{darkred}x_{j,c}\\ & \sum_c\color{darkred}x_{n,c}=1 && \forall n \\& \color{darkred}x_{n,c} \in \{0,1\} \end{align}\] |

MIP Model |
---|

\[\begin{align} \min & \sum_{\color{darkblue}a_{i,j}} \color{darkblue}w_{i,j} \cdot \color{darkred}y_{i,j}\\ & \color{darkred}y_{i,j} \ge \color{darkred}x_{i,c} + \color{darkred}x_{j,c} - 1 && \forall \color{darkblue}a_{i,j},c\\ & \sum_c\color{darkred}x_{n,c}=1 && \forall n \\& \color{darkred}x_{n,c} \in \{0,1\} \\ & \color{darkred}y_{i,j} \in [0,1] \end{align}\] |

The constraint \[ \color{darkred}y_{i,j} \ge \color{darkred}x_{i,c} + \color{darkred}x_{j,c} - 1 \>\>\> \forall \color{darkblue}a_{i,j},c\] implements the implication \[\color{darkred}x_{i,c} = \color{darkred}x_{j,c} = 1 \Rightarrow \color{darkred}y_{i,j}=1\] Note that the variable \(\color{darkred}y_{i,j}\) is continuous between 0 and 1. It will be integer automatically.

Side note.In this reformulation I assumed \(\color{darkblue}w_{i,j} \ge 0\). If that is not the case we can use a slightly more complex formulation: \[\begin{align} \min & \sum_{\color{darkblue}a_{i,j},c} \color{darkblue}w_{i,j} \cdot \color{darkred}y_{i,j,c} \\ & \color{darkred}y_{i,j,c} \le \color{darkred}x_{i,c} && \forall \color{darkblue}a_{i,j},c \> \text{if $\color{darkblue}w_{i,j}\lt 0$} \\ & \color{darkred}y_{i,j,c} \le \color{darkred}x_{j,c} && \forall \color{darkblue}a_{i,j},c \> \text{if $\color{darkblue}w_{i,j}\lt 0$} \\ & \color{darkred}y_{i,j,c} \ge \color{darkred}x_{i,c} + \color{darkred}x_{j,c} - 1 && \forall \color{darkblue}a_{i,j},c \> \text{if $\color{darkblue}w_{i,j}\gt 0$} \\ & \color{darkred}x_{n,c} \in \{0,1\} \\ & \color{darkred}y_{i,j,c} \in [0,1]\end{align}\]

#### Results

---- 91 VARIABLE color1 color2 color3 color4 color5 n1 1.000 ---- 91 VARIABLE ---- 96 PARAMETER n20 n26 n31 n41 n46 n48 n3 0.150 0.017 |

---- 91 VARIABLE color1 color2 color3 n1 1.000 ---- 91 VARIABLE ame colored nodes---- 96 PARAMETER n12 n13 n15 n16 n17 n20 n2 0.749 0.270 + n22 n24 n25 n26 n29 n31 n3
0.187 + n32 n33 n34 n35 n36 n37 n1 0.314 + n40 n41 n42 n44 n45 n46 n3
0.196 + n47 n49 n50 n15 0.178 |

#### Cplex tidbits

Tried aggregator 1 time.MIP Presolve eliminated 0 rows and 1 columns.MIP Presolve added 1926 rows and 963 columns.Reduced MIP has 1976 rows, 1113 columns, and 4002 nonzeros.Reduced MIP has 1113 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.09 sec. (0.34 ticks)Probing time = 0.00 sec. (0.37 ticks)Tried aggregator 1 time.Detecting symmetries...MIP Presolve eliminated 963 rows and 0 columns.Reduced MIP has 1013 rows, 1113 columns, and 3039 nonzeros.Reduced MIP has 1113 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (3.24 ticks)Classifier predicts products in MIQP should be linearized.

Tried aggregator 1 time.MIP Presolve eliminated 2712 rows and 905 columns.Reduced MIP has 1013 rows, 471 columns, and 3039 nonzeros.Reduced MIP has 150 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (2.85 ticks)Found incumbent of value 166.366290 after 0.00 sec. (3.79 ticks)Probing time = 0.00 sec. (0.27 ticks)Tried aggregator 1 time.Detecting symmetries...Reduced MIP has 1013 rows, 471 columns, and 3039 nonzeros.Reduced MIP has 471 binaries, 0 generals, 0 SOSs, and 0 indicators.Presolve time = 0.00 sec. (2.20 ticks)

--- MIQP status (101): integer optimal solution.--- Cplex Time: 29.88sec (det. 22780.65 ticks)--- MIP status (101): integer optimal solution.--- Cplex Time: 50.83sec (det. 44974.47 ticks)

#### Conclusion

#### References

- Find graph colouring that minimises sum of weights of edges that share vertex colours, https://stackoverflow.com/questions/70804766/find-graph-colouring-that-minimises-sum-of-weights-of-edges-that-share-vertex-co
- Coloring the US county map, https://yetanothermathprogrammingconsultant.blogspot.com/2022/01/coloring-us-county-map.html

#### Appendix: GAMS Model

$ontext Suppose
we have a weighted complete graph with n vertices. We want to coloureach
vertex one of k colours. The cost of any colouring is the sum of theweights
of all edges that connect vertices of the same colour.For my
use case, n will be around 20-50. For k = 2, 3 brute force workedfine,
but I would ideally like a solution for any k. It is also the casethat
the graphs I'm dealing with have reasonable sparsity, but again,I would
ideally like to solve the general case.References:https://yetanothermathprogrammingconsultant.blogspot.com/2022/01/a-different-coloring-problem.html$offtext *---------------------------------------------------------------* random graph** sparse undirected network:* arcs only from i->j when i<j*---------------------------------------------------------------setn 'nodes' /n1*n50/ a(n,n) 'arcs' c 'colors' /color1*color3/ ; alias(n,i,j);a(i,j)$( ord(i)<ord(j)) = yes;parameter w(n,n) 'weights';w(a)$(uniform(0,1)<0.25) = uniform(0,1); display w;*---------------------------------------------------------------* MIQP model*---------------------------------------------------------------binary variablesx(n,c) 'assign color to node' ; variablecost 'number of arcs with same colored nodes' ; equationsobjective 'minimize cost' assign(n) 'every node should have exactly one color' ; objective.. cost =e= sum((a(i,j),c),w(a)*x(i,c)*x(j,c));assign(n).. sum(c, x(n,c)) =e= 1;model color1 /all/;option optcr=0,
miqcp=cplex, threads=16;solve color1
minimizing cost using miqcp;*---------------------------------------------------------------* MIP model*---------------------------------------------------------------binary variable y(i,j) 'nodes have the same color';equationsobjective2 'linearized objective' ybound(i,j,c) 'x(i,c)=x(j,c)=1 => y(i,j)=1' ; objective2.. cost =e= sum(a,w(a)*y(a));ybound(a(i,j),c)$w(a).. y(a) =g= x(i,c)+x(j,c)-1; model color2 /objective2,assign,ybound/;* optionally relax y to continuous between 0 and 1y.prior(a) = INF;solve color2 minimizing
cost using mip;*---------------------------------------------------------------* symmetry* impose restrictions on first few nodes* node1 = color1* node2 = color1
or color2* node3 = color1
or color2 or color3*---------------------------------------------------------------set allowed(n,c) 'allowed colors for first
card(c)-1 nodes';allowed(n,c) = ord(c) <= ord(n) and ord(n) < card(c);display allowed;equation symmetry(n) 'break some symmetry';symmetry(n)$( ord(n)<card(c)).. sum(allowed(n,c),x(n,c)) =e= 1;model color3 /color1,symmetry/;solve color3
minimizing cost using miqcp;*---------------------------------------------------------------* reporting*---------------------------------------------------------------display x.l,cost.l;parameter wx 'obj contribution';wx(a(i,j)) = w(a)* sum(c,x.l(i,c)*x.l(j,c));display wx; |

Nice post as always. The y[i,j] <= x[i,c] and y[i,j] <= x[j,c] constraints would instead need y[i,j,c] variables to work properly.

ReplyDeleteYes indeed. Thanks!

Delete