/*********************************************
File: hipp-opt-gus-ilp.mod
Author: Ferhan Ture
Date: 12-20-07
Run with command: oplrun -v -D n=5 -D m=4 hipp-opt-gus-ilp.mod P0.gus.dat
ILP HIPP formulation, according to Gusfield's definition
HIPP Given a set G of n genotypes each with m sites, find a minimal set H of haplotypes such that the following constraints are satisfied:
C1 Every genotype g in G is mapped to two haplotypes in H.
C2 For every genotype g in G, for every ambiguous site j of g, the values of the j'th sites of these haplotypes are different.
C3 For every genotype g in G, for every resolved site j of g, the values of the j'th site of these haplotypes are g[j].
*********************************************/
int n = ...;
int m = ...;
int g[1..n, 1..m]=...;
dvar int h[1..2*n, 1..m] in 0..1;
dvar int s[1..2*n,1..2*n,1..n] in 0..1;
// Minimization statement
minimize max(i1 in 1..2*n, i2 in 1..2*n, i in 1..n) i2*s[i1,i2,i];
subject to {
// C1 Map every genotype i to two haplotypes i1 and i2
forall(i in 1..n)
sum(i1 in 1..2*n,i2 in 1..2*n) (i1<=i2)*s[i1,i2,i] ==1;
// C2 & C3
forall(i in 1..n,i1 in 1..2*n, i2 in 1..2*n)
sum(j in 1..m) ((h[i1,j]==h[i2,j] && h[i2,j]==g[i,j]) || (h[i1,j]!=h[i2,j] && g[i,j]==2)) >= m*(s[i1,i2,i]);
}