Rule Solver – Map Coloring with Violations

This is an advanced version of “Map Coloring” problem that could use 4 colors. Now we have only 3 colors (blue, red, green). It is certainly not enough to color six European countries: Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands with no neighboring countries using the same color. So, some neighboring countries 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 satisfies as many constraints as possible while minimizing the total violation cost.

As usual, we start with the Glossary:

All 6 unknown decision variables could take different colors from 1 to 4.

We will split all constraints into Hard (must be satisfied) and Soft (could be violated). First, we will post hard constraints

Then we will post soft constraints with their violation costs:

These three constraints were added to the array “Constraint Violations”. Now we can define the objective variable as a sum of all constraint violations:

Finally, we can invoke the above tables using the table “Define”. The table “Solve” solves the problem by using the predefined method “SolverMinimize”:

Here are the execution results:

Netherlands[1] Belgium[2] Luxembourg[1] Denmark[1] France[1] Germany[3]

Luxembourg != Belgium[0] France != Luxembourg[257] Luxembourg != Germany[0]

Objective[257]

Only the “cheapest” constraint “France != Luxembourg[257]” has been violated.

The proper standard project is available in openrules.solver/PREFERENCES/MapColoringPreferences.