/*********************************************
File: hipp-dec-s2-gus-ilp.mod
Author: Ferhan Ture
Date: 12-20-07
Run with command: oplrun -v -D n=5 -D m=4 -D k=5 hipp-dec-s2-gus-ilp.mod P0.gus.dat
ILP HIPP-DEC formulation with S2, according to Gusfield's definition
HIPP-DEC Given a set G of n genotypes each with m sites, and a positive integer k, decide whether there is a set H of k 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].
S2 Haplotype i is not generated (used to explain genotypes), unless i-1 is already generated.
*********************************************/
int n = ...;
int m = ...;
int k = ...;
int g[1..n, 1..m]=...;
dvar int h[1..k, 1..m] in 0..1;
dvar int explains[1..k,1..k,1..n] in 0..1;
dvar int d[1..k,1..k] in 0..1;
subject to {
// C1 Map every genotype i to two haplotypes i1 and i2
forall(i in 1..n)
sum(i1 in 1..k,i2 in 1..k) explains[i1,i2,i]==1;
//C2 & C3
forall(i in 1..n,i1 in 1..k, i2 in 1..k)
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*(explains[i1,i2,i]);
// S2
forall(i1 in 1..k,i2 in 1..k,j in 1..m)
abs(h[i1,j] - h[i2,j]) <= d[i1,i2];
forall(i1 in 1..k,i2 in 1..k)
d[i1,i2] <= sum(j in 1..m) (abs(h[i1,j] - h[i2,j]));
forall(i in 1..k)
(-i+2) + sum(j in 1..i-1) d[i,j] == 1;
}