Map Coloring With ViolationsΒΆ

This version of the map coloring problem is an advanced version. Instead of having four colors, we only have three. In other words, some countries will have to share a color with a bordering country. The full DMCommunity challenge, with other submitted solutions, can be found here.

Map Coloring with Violations

This challenge is an advanced version of the May-2019 Challenge. Previously you had 4 colors (blue, red, green, or yellow) but now you have only 3 colors (blue, red, green). It is not enough to color six European countries: Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands in such a way that no neighboring countries use the same color. So, some neighboring counties may have the same colors but there is a relative cost for such violations:

France – Luxembourg: $257

Luxembourg – Germany: $904

Luxembourg – Belgium: $568

This problem is a bit harder than the previous one, because we can no longer create a constraint that bordering countries can not share a color. Instead, we express this constraint only for all countries that are not Luxembourg.

We start by creating our glossary. We create a type to represent countries and a type to represent the colors. We also add a type Number to represent the violation score.

Type
Name Type Values
Country String Belgium, France, Germany, Luxembourg, Netherlands
Color String Green, Red, Yellow
Number Int [0..10000]

To assign every country exactly one color, we can use a function. We also need a constant to represent the score of a solution, which we will call Violations To express that two countries border, we use a relation.

Function
Name Type
color of Country Color

Constant
Name Type
Violations Number

Relation
Name
Country borders Country

Now that our glossary is done, we move on to the next step. We change our constraint table from the previous model into the following: if two countries border of which neither is Luxembourg, they cannot share the same color. This way, Luxembourg is allowed to share a color with its bordering countries.

Bordering countries cannot share colors
E* Country called c1 Country called c2 c1 borders c2 color of c1
1 not(Luxembourg) not(Luxembourg) Yes Not(color of c2)

Now we add a table which will sum the weights of the vialotions, and store it in the Violations constant.

Coloring Violations
C+ color of Luxembourg Violations
1 = color of France 257
2 = color of Germany 904
3 = color of Belgium 568

And that is all the logic we need to solve this problem! We simply need to represent which countries border which using a data table, and then tell the system to minimize the Violations constant.

Data Table: Bordering Countries
Country called c1 Country called c2 c1 borders c2
1 Belgium France, Luxembourg, Netherlands, Germany Yes
2 Netherlands Germany Yes
3 Germany France, Luxembourg, Denmark Yes
4 France Luxembourg Yes

Goal
Minimize Violations

We can now run our model using the cDMN solver. This results in the following output:

Number of models: 1
Model 1
=======
structure  : V {
  Country_borders_Country = { Belgium,France; Belgium,Germany; Belgium,Luxembourg; Belgium,Netherlands; France,Luxembourg; Germany,Denmark; Germany,France; Germany,Luxembourg; Netherlands,Germany }
  Color = { Belgium->Red; Denmark->Red; France->Green; Germany->Yellow; Luxembourg->Green; Netherlands->Green }
  Violations = 257
}

Elapsed Time:
0.047935

And there we have it! If Luxembourg only shares a color with France, we have the lowest score for violation.

Of course, this is a trivial example: this answer was visible from the start. Instead of only having a violation for Luxembourg, we could create scores for every two bordering countries and then minimize it. This can be done by removing the constraint table, and changing the C+ table to a table which counts the violation weight for every two countries if they share the same color.

Coloring Violations
C+ Country called c1 Country called c2 color of c1 Violations
1 - - color of c2 Weight of c1 and c2

Where Weight of Country and Country is a function which maps every pair of countries on a violation weight, which is defined in a data table.