<div dir="ltr"><div><div><div>Dear Benjamin,<br></div>thank you for your response.<br><br>Really, it was my mistake to add "<span class="gmail-im">x[i,i] = 0 (i=1:N)</span>"' constraints into general QAP formulation (there is a long history that led to that...). <br><br></div>Best regards,<br></div>Vladimir.<br><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Mar 3, 2017 at 7:31 PM, Benjamin Müller <span dir="ltr"><<a href="mailto:benjamin.mueller@zib.de" target="_blank">benjamin.mueller@zib.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear Vladimir,<br>
<br>
could it be that your constraints<span class="gmail-"><br>
<br>
> x[i,i] = 0 (i=1:N)<br>
<br></span>
are wrong? These essentially forbid that element i can be assigned to position i. In the solution file of chr15c<br>
<br>
13 2 5 7 8 1 14 6 4 3 15 9 12 11 10,<br>
<br>
you see that the second element is assigned to the second position, which seems to be not valid for your model.<br>
<br>
Regards,<br>
Benjamin<div><div class="gmail-h5"><br>
<br>
<br>
On 02/27/2017 12:46 AM, Vladimir VV wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div class="gmail-h5">
Dear All,<br>
on experimenting with solving QAP by SCIP I found that for at least one<br>
problem the solver returns wrong optimal value of objective function.<br>
<br>
I took data from this collection<br>
<a href="http://anjos.mgi.polymtl.ca/qaplib//inst.html" rel="noreferrer" target="_blank">http://anjos.mgi.polymtl.ca/qa<wbr>plib//inst.html</a>.<br>
<br>
For chr15c dataset, <a href="http://anjos.mgi.polymtl.ca/qaplib//data.d/chr15c.dat" rel="noreferrer" target="_blank">http://anjos.mgi.polymtl.ca/qa<wbr>plib//data.d/chr15c.dat</a>,<br>
SCIP (version 3.2.1, see details in attached [chr15c.scip.4Gb.log.txt])<br>
returns 10108 as optimal object value.<br>
But QAPLIB site reports that optimal value is 9504, see<br>
<a href="http://anjos.mgi.polymtl.ca/qaplib//soln.d/chr15c.sln" rel="noreferrer" target="_blank">http://anjos.mgi.polymtl.ca/qa<wbr>plib//soln.d/chr15c.sln</a>.<br>
I checked optimal permutation, presented in the above URL, with "my<br>
model" (in Pyomo, that I used for modelling, generating AMPL-stub and to<br>
analyze results) and got the same value (9504) which is "much better"<br>
than 10108 returned by SCIP (with zero gap!).<br>
<br>
QAP problem has been formulated as bilinear one with boolean variables<br>
(F and D are nonnegative, symmetric NxN matrices):<br>
z \to \min\limits_{x[i,j], z}<br>
z >= \sum\limits_{i,j,k,l}F[i,j]*D[<wbr>k,l]*x[i,k]*x[j,l],<br>
\sum\limits_i x[i,j] = 1 (j=1:N),<br>
\sum\limits_j x[i,j] = 1 (i=1:N),<br>
x[i,i] = 0 (i=1:N)<br>
z - an auxiliary scalar, continuous variable,<br>
x[i,j] - boolean (i=1:N, j=1:N).<br>
<br>
Can anybody explain the reason of the issue?<br>
For a number of other examples from QAPLIB,<br>
<a href="http://anjos.mgi.polymtl.ca/qaplib//inst.html" rel="noreferrer" target="_blank">http://anjos.mgi.polymtl.ca/qa<wbr>plib//inst.html</a>, SCIPAMPL returns correct<br>
solutions... (the same as presented in<br>
<a href="http://anjos.mgi.polymtl.ca/qaplib//soln.d/*.sln" rel="noreferrer" target="_blank">http://anjos.mgi.polymtl.ca/qa<wbr>plib//soln.d/*.sln</a>)<br>
<br>
Besides log file [chr15c.scip.4Gb.log.txt] I attached:<br>
</div></div><a href="http://chr15c.nl" rel="noreferrer" target="_blank">chr15c.nl</a> <<a href="http://chr15c.nl" rel="noreferrer" target="_blank">http://chr15c.nl</a>>,col,row (AMPL-stub and auxiliaries<span class="gmail-"><br>
generated by Pyomo);<br>
chr15c.sol (returned by<br></span>
SCIPAMPL <a href="http://chr15c.nl" rel="noreferrer" target="_blank">chr15c.nl</a> <<a href="http://chr15c.nl" rel="noreferrer" target="_blank">http://chr15c.nl</a>> -AMPL scip4qapMem4Gb.set<span class="gmail-"><br>
);<br>
scip4qapMem4Gb.set (SCIP options file).<br>
<br>
<br>
Thanks in advance.<br>
Vladimir V. Voloshinov.<br>
<br>
<br>
<br></span>
______________________________<wbr>_________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="http://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">http://listserv.zib.de/mailman<wbr>/listinfo/scip</a><br>
<br><span class="gmail-HOEnZb"><font color="#888888">
</font></span></blockquote><span class="gmail-HOEnZb"><font color="#888888">
<br>
-- <br>
______________________________<br>
Benjamin Müller<br>
Zuse Institute Berlin<br>
Takustr. 7, 14195 Berlin<br>
<a href="mailto:benjamin.mueller@zib.de" target="_blank">benjamin.mueller@zib.de</a><br>
+49 30 841 85-195<br>
</font></span></blockquote></div><br><br></div></div></div></div>