! A graph coloring model in LINGO  (ColorGraph.lg4);
! Given 
    a set of countries, and
    pairs of countries that share a border, and
    a set of colors,
  Choose a color for each country, so that if
  two countries are adjacent, they get different colors.
 Minimize the number of colors used;

! Keywords:  Coloring, Graph color, Map design;
 Color: is_used;
 country: gets_color;
 kxc( color,country): y;
DATA: ! The colors available; color = blue, green, red, yellow, purple; ! The countries, each to be assigned a color; country = belgium, denmark, france, germany, luxembourg, netherlands; ! The country pairs that share a nonzero length border; neighbor = belgium france belgium germany belgium luxembourg belgium netherlands denmark germany france germany france luxembourg germany luxembourg germany netherlands; ENDDATA SUBMODEL COLOR_GRAPH: ! Variables: y(i,j) = 1 if color i assigned to country j gets_color(j) = color assigned to country j, is_used(i) = 1 if color i is used; ! Minimize number of colors used; MIN = @SUM( color(i) : is_used(i)); @FOR( country(j): ! Country j must be assigned exactly one color; @SUM(color(i): y(i,j)) = 1; ! The specific color assigned to country j is; gets_color(j) = @SUM(color(i): i*y(i,j)); ! If country j gets color i, then is_used(i) = 1; @FOR( color(i): is_used(i) >= y(i,j); ); ); ! The y's are binary, (0 or 1); @FOR(kxc(i,j): @BIN(y(i,j))); @FOR( neighbor(r,s): @FOR( color(i): ! If r and s are neighbors, they cannot get the same color i; y(i,r) + y(i,s) <= 1; ); ); ! Kill some symmetry, use early colors first; @FOR( color(i) | i #GT# 1: is_used(i) <= is_used(i-1); ); ENDSUBMODEL
CALC: @SET('TERSEO', 2); ! Turn off default output; @SOLVE( COLOR_GRAPH); @WRITE(@NEWLINE(1),' Number colors used= ', @SUM( color(i): is_used(i)),@NEWLINE(1)); @FOR( country(j): @WRITE( @FORMAT(country(j), '12s'),' gets color ', @FORMAT( color(gets_color(j)), '10s'),@NEWLINE(1)); ); ENDCALC