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.