9
$\begingroup$

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "distance" between the colors chosen for each node. What is an algorithm I can use to choose the colors for the nodes such that the total edge weight is maximized?

For example, say node 0 can be red, blue, or gray, and node 5 can be either blue or gold. If node 0 and node 5 were both blue, the edge between them would have low weight, which is not good. Example graph

I have considered a few possibilities:

  • Brute-force search. While feasible for this example, where there are only 3*2*2*1*1*2 = 24 total possible color combinations, my actual problem has well over 300 nodes, so this is not feasible.

  • Nonlinear optimization problem. I have written a formulation such that this small example can be solved in AMPL and Python's scipy, but this also suffers from large complexity.

  • Maximum-cost network flow. I have tried to formulate this as a network flow problem, where each node represents a "choice" to be made about each actual node. However, I am unsure how to introduce appropriate constraints and/or dummy nodes such that I guarantee that the cost of the flow actually equals my objective function, and that the only feasible solutions in the flow problem "make sense" for my original problem.

There is also a chance that this problem is not really tractable, but I would not know how to show that.

The actual use case of this problem is that I have a Voronoi diagram where each region corresponds to a different team. I can select one of up to 3 colors for each team to use for that team's region on the map, and I want to choose the colors such that the contrast between bordering regions is maximized.

I originally posted this on StackOverflow but I was redirected here. Any idea on how to formulate this problem?

EDIT: After solving the problem, here was the resulting image, note that I removed pure black and white (to avoid obtaining a checkerboard). Lots of gold and navy blue!

enter image description here

$\endgroup$
4
  • $\begingroup$ I would try to formulate it as a MIP first. The formulation is straight forward and the problem as well as the size look like it should be solvable by modern solvers. $\endgroup$
    – SimonT
    Dec 21 '20 at 8:49
  • 1
    $\begingroup$ Could you share your non linear formulation ? $\endgroup$
    – Kuifje
    Dec 21 '20 at 9:18
  • 3
    $\begingroup$ There's actually a paper with a problem similar to this one, for the purpose of choosing colors for metro (subway) lines: link.springer.com/content/pdf/10.1007%2Fs00283-015-9597-y.pdf $\endgroup$
    – LarrySnyder610
    Dec 21 '20 at 16:36
  • $\begingroup$ Thank you so much for this! I was searching terms like "color contrast" or "color difference" but never found this. A little bit different from what I'm trying to do but still very interesting. The bit about RGB is well taken too. $\endgroup$
    – ischmidt20
    Dec 22 '20 at 3:36
6
$\begingroup$

You can solve this as a quadratic assignment problem. With the same $x$ variables as in @Kuifje's answer, you want to maximize $$\sum_{(u,v)\in A}\sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| x_{u,j}x_{v,k} \tag1$$ subject to $$\sum_{j \in C(v)} x_{u,j} = 1 \quad \text{for $v \in V$} \tag2$$ One approach is to call a mixed integer quadratic programming solver. Alternatively, you can linearize the quadratic objective $(1)$ by introducing binary (or just nonnegative) variables $y_{u,v}^{j,k}$ and linear constraints \begin{align} y_{u,v}^{j,k} &\le x_{u,j} &&\text{for $(u,v) \in A, j \in C(u), k \in C(v)$} \tag3 \\ y_{u,v}^{j,k} &\le x_{v,k} &&\text{for $(u,v) \in A, j \in C(u), k \in C(v)$} \tag4 \\ \end{align} and then maximize $$\sum_{(u,v)\in A}\sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| y_{u,v}^{j,k} \tag5$$ Notice that $(2)$-$(5)$ is very similar to @Kuifje's formulation but eliminates $z$ and also omits one set of $\le$ constraints.


You can instead use compact linearization as follows. Maximize $(5)$ subject to $(2)$, $(3)$, and $$\sum_{j \in C(u)} y_{u,v}^{j,k} = x_{v,k} \quad \text{for $(u,v) \in A$ and $k \in C(v)$} \tag6$$ You can derive $(6)$ from $(2)$ by multiplying both sides by $x_{j,v}$ and replacing the resulting product with $y_{u,v}^{j,k}$, as in the Reformulation-Linearization Technique (RLT).


Update: After seeing the resulting map, which has several bordering regions with similar colors like gold and yellow, I think you want a slightly different objective. Instead of maximizing the sum of the edge weights, I recommend maximizing the minimum of the edge weights, which you can do as follows. Introduce a new variable $z$ and maximize $z$ subject to $(2)$, $(3)$, $(6)$, and $$z \le \sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| y_{u,v}^{j,k} \quad \text{for $(u,v)\in A$} \tag7$$

Furthermore, both objectives treat all borders the same, so a short border accrues the same reward as a long border. If you have access to the length $\ell_{u,v}$ of the border between $u$ and $v$, you might get better results by replacing $|\omega_j- \omega_k|$ with $\ell_{u,v} |\omega_j- \omega_k|$.

$\endgroup$
2
  • $\begingroup$ Accepting this, as it was the actual formulation I used in my implementation, which I coded up with Google's CP-SAT solver in Python. $\endgroup$
    – ischmidt20
    Jan 23 at 5:10
  • $\begingroup$ @ischmidt20 I just updated my answer with some further suggestions. $\endgroup$
    – RobPratt
    Jan 23 at 16:00
6
$\begingroup$

If you are dealing with Voronoi diagrams then perhaps your graph is planar, and in this case there is probably a good heuristic for the problem, but more details should be given I think before going down that road. In the mean time you can try working with a MIP as suggested by @SimonT. For example:

Let $x_{vc}$ be a binary variable that takes values $1$ if and only if node $v\in V$ is assigned color $c \in C(v)$, where $C(v)$ denotes the set of choices for node $v$. Also, let $\omega_c \in \mathbb{R}^+$ denote the weight of color $c$ (used to measure the distance between two nodes). Let $y_{uv}^{jk}$ be another binary variable that takes value $1$ if and only if colors $j$ and $k$ are assigned to nodes $u$ and $v$, respectively, with $(u,v) \in A, j \in C(u), k \in C(v).$ And let $z_{uv}$ be a non negative variable that equals the distance between nodes $u$ and $v$.

You want to maximize the total edge weight:

$$ \max \quad \sum_{(u,v)\in A} z_{uv} $$ subject to:

  • Each node must be assigned exactly one color: $$ \sum_{c \in C(v)} x_{vc} = 1 \quad \forall v \in V $$
  • $x$ and $y$ must be consistent:

\begin{align*} x_{uj}+x_{vk} &\le y_{uv}^{jk} +1 \quad &\forall (u,v) \in A, \forall j \in C(u), \forall k \in C(v) \\ y_{uv}^{jk} &\le x_{uj} \quad &\forall (u,v) \in A, \forall j \in C(u), \forall k \in C(v) \\ y_{uv}^{jk} &\le x_{vk} \quad &\forall (u,v) \in A, \forall j \in C(u), \forall k \in C(v) \end{align*}

  • The distance between two vertices is the difference between the weights of their colors:

$$ z_{uv} = \sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| y_{uv}^{jk} \quad \forall (u,v) \in A $$

  • Variables $x$ and $y$ are binary: $$ x,y \in \{0,1\} $$
  • Variables $z$ are non negative: $$ z\in \mathbb{R^+} $$
$\endgroup$
1
  • $\begingroup$ Brilliant, I think this might do it! My previous formulation tried to create your $y_{uv}^{jk}$ variables by multiplying $x_{uj}$ and $x_{vk}$ together, such that y would be 1 if and only if both x variables were 1. Introducing this non-linearity in the objective function was obviously not ideal, and it looks like this accomplishes the same but without that non-linearity. I'll toy with this over the next couple days but it looks promising, thanks! $\endgroup$
    – ischmidt20
    Dec 21 '20 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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