How to maximize "contrast" between nodes on a graph?

Question

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.

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!

Answer 1

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|$.

Answer 2

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^+} $$