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!