This problem is an advanced version of the Map Coloring where we had 4 colors but now we 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
We need to find a solution that minimizes the total violation cost.
To define and solve this problem we created Java class MapColoringWithViolations that extends JavaSolver and its method define() will replace the old constraints with two types of constraints “hard” and “soft”:
As before, the method define() creates constrained integer variables for each country with possible values from 0 to (number of colors – 1). Then it posts only “hard” constraints csp.post(country1, “!=”, country2) for all neighboring countries: these constraints cannot be violated. Then it defines so called “soft” constraints by converting a constraint csp.linear(country1,”=”,country2) to a Boolean constrained variable using the Constraint’s method asBool(). When we multiply these variables by their violation costs, we receive weight variables, which we placed in the Var[] array weightVars. We want to minimize the sum of all weight variables, so we set it as our objective.
To solve the problem we called the standard JavaSolver’s method minimize():
Here are the results:
JavaSolver.com 