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:

### Like this:

Like Loading...