[SCIP] SCIP and Quadratic Assignment Problem

[Vladimir V. Voloshinov]

Dear Benjamin,
thank you for your response.

Really, it was my mistake  to add "x[i,i] = 0 (i=1:N)"'  constraints into
general QAP formulation (there is a long history that led to that...).

Best regards,
Vladimir.

On Fri, Mar 3, 2017 at 7:31 PM, Benjamin Müller <benjamin.mueller at zib.de>
wrote:

> Dear Vladimir,
>
> could it be that your constraints
>
> > x[i,i] = 0 (i=1:N)
>
> are wrong? These essentially forbid that element i can be assigned to
> position i. In the solution file of chr15c
>
>         13  2  5  7  8  1 14  6  4  3 15  9 12 11 10,
>
> you see that the second element is assigned to the second position, which
> seems to be not valid for your model.
>
> Regards,
> Benjamin
>
>
>
> On 02/27/2017 12:46 AM, Vladimir VV wrote:
>
>> Dear All,
>> on experimenting with solving QAP by SCIP I found that for at least one
>> problem the solver returns wrong optimal value of objective function.
>>
>> I took data from this collection
>> http://anjos.mgi.polymtl.ca/qaplib//inst.html.
>>
>> For chr15c dataset, http://anjos.mgi.polymtl.ca/qaplib//data.d/chr15c.dat
>> ,
>> SCIP (version 3.2.1, see details in attached [chr15c.scip.4Gb.log.txt])
>> returns 10108 as optimal object value.
>> But QAPLIB site reports that optimal value is 9504, see
>> http://anjos.mgi.polymtl.ca/qaplib//soln.d/chr15c.sln.
>> 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!).
>>
>> QAP problem has been formulated as bilinear one with boolean variables
>> (F and D are nonnegative, symmetric NxN matrices):
>> z \to \min\limits_{x[i,j], z}
>> z >= \sum\limits_{i,j,k,l}F[i,j]*D[k,l]*x[i,k]*x[j,l],
>> \sum\limits_i x[i,j] = 1 (j=1:N),
>> \sum\limits_j x[i,j] = 1 (i=1:N),
>> x[i,i] = 0 (i=1:N)
>> z - an auxiliary scalar, continuous variable,
>> x[i,j] - boolean (i=1:N, j=1:N).
>>
>> Can anybody explain the reason of the issue?
>> For a number of other examples from QAPLIB,
>> http://anjos.mgi.polymtl.ca/qaplib//inst.html, SCIPAMPL returns correct
>> solutions... (the same as presented in
>> http://anjos.mgi.polymtl.ca/qaplib//soln.d/*.sln)
>>
>> Besides log file [chr15c.scip.4Gb.log.txt] I attached:
>> chr15c.nl <http://chr15c.nl>,col,row (AMPL-stub and auxiliaries
>> generated by Pyomo);
>> chr15c.sol (returned by
>> SCIPAMPL chr15c.nl <http://chr15c.nl> -AMPL scip4qapMem4Gb.set
>> );
>> scip4qapMem4Gb.set (SCIP options file).
>>
>>
>> Thanks in advance.
>> Vladimir V. Voloshinov.
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
> --
> ______________________________
> Benjamin Müller
> Zuse Institute Berlin
> Takustr. 7, 14195 Berlin
> benjamin.mueller at zib.de
> +49 30 841 85-195
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170304/90b61903/attachment.html>