[SCIP] SCIP and Quadratic Assignment Problem

[Benjamin Müller]

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