/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: mpex29                                             */
/*   TITLE: Protein Comparison (mpex29)                        */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: OPTMODEL                                           */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF:                                                    */
/*    MISC: Example 29 from the Mathematical Programming       */
/*          Examples book.                                     */
/*                                                             */
/***************************************************************/



data edge_data1;
   input i j;
   datalines;
1 2
2 9
3 4
3 5
5 6
6 7
7 9
8 9
;

data edge_data2;
   input i j;
   datalines;
1 4
2 3
4 6
4 7
5 6
6 8
7 8
7 10
9 10
10 11
;


proc optmodel;
   set  EDGES {1..2};
   read data edge_data1 into EDGES[1]=[i j];
   read data edge_data2 into EDGES[2]=[i j];


   set NODES {g in 1..2} init union { in EDGES[g]} {i,j};
   for {g in 1..2} NODES[g] = 1..card(NODES[g]) inter NODES[g];


   set IJ = NODES[1] cross NODES[2];
   set EDGE_PAIRS = { in IJ,  in IJ: i  in EDGES[1]) and ( in EDGES[2])};


   /* Assign[i,j] = 1 if node i in NODES[1] assigned to node j in NODES[2] */
   var Assign {IJ} binary;

   /* IsCorrespondingEdge[i,j,k,l] = 1 if edge  in EDGES[1]
      corresponds to edge  in EDGES[2] */
   var IsCorrespondingEdge {EDGE_PAIRS} binary;

   /* maximize number of corresponding edges */
   max NumCorrespondingEdges =
      sum { in EDGE_PAIRS} IsCorrespondingEdge[i,j,k,l];

   /* assign each i to at most one j */
   con Assign_i {i in NODES[1]}:
      sum { in IJ} Assign[i,j]  in IJ} Assign[i,j]  in IJ,  in IJ: i  l}:
      Assign[i,j] + Assign[k,l]  in EDGE_PAIRS}:
      IsCorrespondingEdge[i,j,k,l]  in EDGE_PAIRS}:
      IsCorrespondingEdge[i,j,k,l]  in IJ: Assign[i,j].sol > 0.5}
      put ('Node '||i||' in graph 1 corresponds to node '||j||' in graph 2.');
   for { in EDGE_PAIRS: IsCorrespondingEdge[i,j,k,l].sol > 0.5} do;
      put ('Edge ('||i||','||k||') in graph 1 corresponds to') @@;
      put ('edge ('||j||','||l||') in graph 2.');
   end;
quit;