! 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;
SETS:
 Color: is_used;
 country: gets_color;
 kxc( color,country): y;
 neighbor(country,country);
ENDSETS
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