/*********************************************
File: hipp-opt-alternative-gus-cp.mod
Author: Ferhan Ture
Date: 12-20-07
Run with command: oplrun -v -conflict -relax -D n=4 -D m=4 hipp-opt-alternative-gus-cp.mod P0-opt.gus.dat
An alternative CP 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].
*********************************************/
using CP;
int n = ...;
int m = ...;
int g[1..n, 1..m]=...;
dvar int h[1..2*n, 1..m] in 0..1;
dvar int u[1..2*n] in 0..1;
dvar int d[1..2*n,1..2*n] in 0..1;
// Minimization statement
minimize sum(i in 1..2*n) u[i];
subject to {
// Each genotype i is explained by its parent haplotypes, haplotype 2i and haplotype 2i-1
forall(i in 1..n,j in 1..m)
(g[i][j] == h[2*i-1][j] && h[2*i-1][j] == h[2*i][j]) || (g[i][j] ==2 && h[2*i-1][j] != h[2*i][j]);
// If haplotypes i1 and i2 have a site j with different values, then these haplotypes are different
forall(i1 in 1..2*n,i2 in 1..2*n,j in 1..m)
h[i1][j] - h[i2][j] <= d[i1][i2];
// If haplotype i1 is different than haplotype i2, then haplotype i2 is different than haplotype i1
forall(i1 in 1..2*n,i2 in 1..2*n)
d[i1][i2] == d[i2][i1];
// If haplotype i is different than all previous haplotypes 1..i-1, then it is called unique
forall(i in 1..2*n)
(-i+2) + sum(j in 1..i-1) d[i][j] <= u[i];
}