Le graphe de Petersen

Bien. Ce n’était pas évident de modéliser le graphe.

Le fichier .mod

set VERTICES;
set COLOR;
set EDGES within {VERTICES, VERTICES};
param price{COLOR} >= 0;


var x{VERTICES,COLOR} binary;

minimize cost:
	sum{v in VERTICES, c in COLOR} price[c] * x[v,c];
	
	
subject to single_color{v in VERTICES}:
	sum{c in COLOR} x[v,c] == 1;
	
subject to different{(u,v) in EDGES, c in COLOR}:
	x[u,c] + x[v,c] <= 1;

Le fichier .dat

set VERTICES := 0 1 2 3 4 5 6 7 8 9;

param: COLOR : price := 
  RED    1
  BLUE  10
  GREEN  0;

set EDGES := 
 (0, 1) (0, 4) (0, 7) (1, 2)
 (1, 5) (2, 3) (2, 9) (3, 4)
 (3, 6) (4, 8) (5, 6) (5, 8)
 (6, 7) (7, 9) (8, 9);

suite