Topic
  • No replies
SystemAdmin
SystemAdmin
623 Posts

Pinned topic A tiny OPL model for solving Jan. 2013 IBM Research "Ponder This" challenge

‏2013-02-07T08:26:37Z |
For information, here is a small OPL model using CP Optimizer to solve the IBM Research Ponder This challenge of January 2013. As you see, the model is amazingly short (5 lines for the model itself). CP Optimizer (V12.5) finds a solution in about 10mn on my laptop.

Here is the complete model:


using CP;   
// Data   range Letters      = 1..18; range Permutations = 1..13; string letter[Letters] = [
"A", 
"B", 
"C", 
"E", 
"F", 
"H", 
"I", 
"J", 
"L", 
"M", 
"N", 
"P", 
"Q", 
"T", 
"V", 
"X", 
"Y", 
"Z"];   tuple Pair   
{ 

int l1; 

int l2; 
} tuple Triple 
{ 

int l1; 

int l2; 

int l3; 
} 
{Pair
}   Pairs   = 
{ <l1,l2> | l1,l2 in Letters : l1!=l2 
}; 
{Pair
}   OPairs  = 
{ <l1,l2> | l1,l2 in Letters : l1<l2  
}; 
{Triple
} Triples = 
{ <l1,l2,l3> | l1,l2,l3 in Letters : l1!=l2 && l1!=l3 && l2!=l3 
};   
// CP Optimizer model   dvar 

int b[p in Permutations][OPairs] in ((p==1)?1:0)..1; 
// Symmetry breaking for first permutation (p=1) dexpr 

int before[p in Permutations][<l1,l2> in Pairs] = (l1<l2)?b[p][<l1,l2>]:(1-b[p][<l2,l1>]); dexpr 

int contains[p in Permutations][<l1,l2,l3> in Triples] = minl(before[p][<l1,l2>], before[p][<l2,l3>]); subject to 
{ forall(p in Permutations, <l1,l2,l3> in Triples) 
{ contains[p][<l1,l2,l3>] <= before[p][<l1,l3>]; 
} 
// Transitive closure forall(<l1,l2,l3> in Triples) 
{ sum(p in Permutations) contains[p][<l1,l2,l3>] >= 1; 
} 
}   
// Post-processing: display solution   

int position[p in Permutations][l in Letters] = 1+sum(l1 in Letters: l1!=l) before[p][<l1,l>]; 

int solution[Permutations][Letters];   execute 
{ 

for(var p in Permutations) 

for(var l in Letters) solution[p][position[p][l]]=l; 

for(var p1 in Permutations) 
{ 

for(var l1 in Letters) write(letter[solution[p1][l1]]); writeln(); 
} 
}


And here is a solution:


ABCEFHIJLMNPQTVXYZ NYHXPZJVBTQIELMACF EYIVXABQTZFPNCMLJH VLPFZAEYXTQHMJINCB QZICMXVJHBAYEPNFLT YNLMEZXFVCTQIPBHAJ TPXMZYLNJHCAIBVFEQ TVQPNMHLBIYEJFCAZX AXNZPMIHFECQVTJYLB FBXVLJIHZPCYMQTNEA QJXTCFEBZNAYHVMLPI JIZYMTQPALVEBCHFXN HCZLYVNBATJXQFPMEI


Note that this model can be made more efficient by adding surrogate and symmetry breaking constraints but we wanted to share the simplicity of the basic model.

Alex (Fleischer) and Philippe