<div dir="ltr"><div><div><div><div><div>Dear All,<br></div>on experimenting with solving QAP by SCIP I found that for at least one problem the solver returns wrong optimal value of objective function. <br></div><br>I took data from this collection <a href="http://anjos.mgi.polymtl.ca/qaplib//inst.html">http://anjos.mgi.polymtl.ca/qaplib//inst.html</a>.<br></div><br>For chr15c dataset, <a href="http://anjos.mgi.polymtl.ca/qaplib//data.d/chr15c.dat">http://anjos.mgi.polymtl.ca/qaplib//data.d/chr15c.dat</a>,<br></div>SCIP (version 3.2.1, see details in attached [chr15c.scip.4Gb.log.txt]) <br>returns 10108 as optimal object value.<br></div><div>But QAPLIB site reports that optimal value is 9504, see <a href="http://anjos.mgi.polymtl.ca/qaplib//soln.d/chr15c.sln">http://anjos.mgi.polymtl.ca/qaplib//soln.d/chr15c.sln</a>.<br></div><div>I checked optimal permutation,  presented in the above URL, with "my model" (in Pyomo, that I used for modelling, generating AMPL-stub and to analyze results) and got the same value (9504) which is "much better" than 10108 returned by SCIP (with zero gap!).<br><br></div><div>QAP problem has been formulated as bilinear one with boolean variables (F and D are nonnegative, symmetric NxN matrices):<br></div><div>z \to \min\limits_{x[i,j], z}<br>z >= \sum\limits_{i,j,k,l}F[i,j]*D[k,l]*x[i,k]*x[j,l],<br>\sum\limits_i x[i,j] = 1 (j=1:N),<br></div><div><div><div><div><div><div><div><div class="gmail_extra">\sum\limits_j x[i,j] = 1 (i=1:N),<br></div><div class="gmail_extra">x[i,i] = 0 (i=1:N)<br></div><div class="gmail_extra">z - an auxiliary scalar, continuous variable,<br></div><div class="gmail_extra">x[i,j] - boolean (i=1:N, j=1:N).<br><br></div><div class="gmail_extra">Can anybody explain the reason of the issue? <br>For a number of other examples from QAPLIB, <a href="http://anjos.mgi.polymtl.ca/qaplib//inst.html">http://anjos.mgi.polymtl.ca/qaplib//inst.html</a>, SCIPAMPL returns correct solutions... (the same as presented in <a href="http://anjos.mgi.polymtl.ca/qaplib//soln.d/*.sln">http://anjos.mgi.polymtl.ca/qaplib//soln.d/*.sln</a>)<br><br></div><div class="gmail_extra">Besides log file [chr15c.scip.4Gb.log.txt] I attached:<br></div><div class="gmail_extra"><a href="http://chr15c.nl">chr15c.nl</a>,col,row (AMPL-stub and auxiliaries generated by Pyomo);<br></div><div class="gmail_extra">chr15c.sol (returned by <br>SCIPAMPL <a href="http://chr15c.nl">chr15c.nl</a> -AMPL scip4qapMem4Gb.set<br>);<br>scip4qapMem4Gb.set (SCIP options file).<br><br></div><div class="gmail_extra"><br>Thanks in advance.<br>Vladimir V. Voloshinov.<br>
<br></div></div></div></div></div></div></div></div></div>