A Lower Bound for the Quadratic Assignment Problem using Semidefinite Programming and SDP_S

Frédéric ROUPIN

This page was made from the QAPLIB home page problems data and html code, which is maintained at the University of Pennsylvania, School of Engineering and Applied Science, by Peter Hahn.

Introduction

The lower bounds presented here have been obtained by using SDP_S on a Pentium IV 2.2 GHz with 1Go RAM under Linux (Redhat 9).

We consider only problems with symmetric instances with size up to 30 (because of memory limitation). For instance, solving the semidefinite relaxation of the nug30 problem requires about 600Mo (using SDP_S).

The semidefinite program used is described in "From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems" .

The source code for generating the input files for SDP_S from a standard QAP ".dat" file can be found here.

For each problem, we report:

The value of the best dual feasible solution we obtained rounded up to the next integer.
The gap between our lower bound and the best known feasible solution. When it is 0% we precise if our primal solution is integral (feasible) and thus optimal.
The CPU time needed to obtain the bound.
An intermediate bound with the corresponding CPU time. Indeed, the SDP solver SB has a strong tailing off effect. To illustrate this point, the figure below gives the bound in dependence of CPU time for the nug15 problem (Pentium IV 2.2 GHz 1Go RAM):

We set a CPU time limit of 24 hours. Therefore the bounds indicated are not always the best one can obtain using our semidefinite relaxation. For instance for the Chr20a problem, we obtained 2192 (the optimal value) in about 47 hours but only 2186 in the allowed CPU time limit.

For some problems, the parameter "-u" was set to 0 or 1 (default value is 4) in order to obtain a better convergence of the SDP solver SB (written by C. Helmberg). See the documentation of SB for further details.

We quote the filename under which it is stored in the library (QAPLIB) and report the size of the problem. Then the objective function value of the best known feasible solution is given. In parentheses we indicate whether this solution is optimal (OPT) or derived by a heuristic. In addition, the best known lower bound is given (when the optimal solution is not known).

N. Christofides and E. Benavent [ChBe:89]

   name    n      solution      Our Bound     Our gap          CPU time   Intermediate Bound
   -----------------------------------------------------------------------------------------
   Chr12a  12     9552 (OPT)      9552	      0%(feasible)     10mn21s     9464 at  1mn48s
   Chr12b  12     9742 (OPT)      9742	      0%(feasible)      4mn49s     9723 at  1mn41s
   Chr12c  12    11156 (OPT)     11156        0%(feasible)     20mn12s    11114 at  7mn49s 
   Chr15a  15     9896 (OPT)      9896        0%(feasible)   5h19mn        9541 at 35mn29s
   Chr15b  15     7990 (OPT)      7987	      0.04%            34mn20s     7785 at  7mn40s
   Chr15c  15     9504 (OPT)      9504        0%(feasible)     59mn48s     9420 at 19mn40s
   Chr18a  18    11098 (OPT)     11098	      0%(feasible)  15h08mn       10046 at 43mn46s
   Chr18b  18     1534 (OPT)      1503        2%            20h36mn        1444 at 55mn25s
   Chr20a  20     2192 (OPT)      2186        0,27%         23h37mn        2101 at 2h34mn
   Chr20b  20     2298 (OPT)      2293        0.21%         23h47mn        2144 at 2h01mn   
   Chr20c  20    14142 (OPT)     14142        0%            13h49mn       13808 at 2h34mn
   Chr22a  22     6156 (OPT)      6156        0%            14h50mn        5928 at 3h02mn 
   Chr22b  22     6194 (OPT)      6194        0%            18h43mn        5950 at 3h01mn
   Chr25a  25     3796 (OPT)      3789        0.18%         22h19mn        3626 at 3h04mn

Recall that for the Chr20a problem, we obtained the optimal value (2192) in about 47 hours but only 2186 in the allowed CPU time limit. For the Chr20b problem, we obtained the optimal value (2298) in 32h10mn.

B. Eschermann and H.J. Wunderlich [EsWu:90]

   name    n    feas.sol.   Our Bound  Our gap  CPU time Intermediate Bound
   ---------------------------------------------------------------------------------------------------------
   Esc16a  16    68 (OPT)    64          5.88%    5h27mn     60 at 5mn18s
   Esc16b  16   292 (OPT)   290          0.68%      42mn01s 284 at 9mn27s
   Esc16c  16   160 (OPT)   154          3.75%    2h25mn    141 at 10mn05s
   Esc16d  16    16 (OPT)    13         18.75%      53mn50s  10 at 11mn13s
   Esc16e  16    28 (OPT)    27          3.57%    2h56mn     24 at 14mn26s   
   Esc16g  16    26 (OPT)    25          3,84%    1h30mn     21 at  4mn35s
   Esc16h  16   996 (OPT)   976          2.00%    9h24mn    954 at 10mn20s             
   Esc16i  16    14 (OPT)    12         14,28%    3h16mn      9 at 6mn26s                                   
   Esc16j  16     8 (OPT)     8          0%       20mn17s     6 at 5mn02s

S.W. Hadley, F. Rendl and H. Wolkowicz [HaReWo:92]

   name   n    solution      Our Bound  Our gap  CPU time Intermediate Bound
   --------------------------------------------------------------------------
   Had12  12   1652 (OPT)    1652        0%	   3mn08s
   Had14  14   2724 (OPT)    2724 	 0% 	   9mn37s
   Had16  16   3720 (OPT)    3720        0%       36mn58s  3709 at 8mn17s
   Had18  18   5358 (OPT)    5358        0%        8h55mn  5341 at 14mn40s
   Had20  20   6922 (OPT)    6922        0%        7h59mn  6900 at 25mn08s

J. Krarup and P.M. Pruzan [KrPr:78]

   name    n    solution     Our Bound  Our gap  CPU time  Intermediate Bound
   --------------------------------------------------------------------------
   Kra30a  30   88900 (OPT)   86241 	2.99%    20h57mn   78223 at 29mn34s
   Kra30b  30   91420 (OPT)   87211     4.60%    20h38mn   79183 at 30mn32s

C.E. Nugent, T.E. Vollmann and J. Ruml [NuVoRu:68]

   name    n    feas.sol.   Our Bound   Our gap    CPU time   Intermediate Bound
   ---------------------------------------------------------------------------------
   Nug12   12    578 (OPT)     568       1.73%     1h01mn        561 at  1mn30s            
   Nug14   14   1014 (OPT)    1010       0.39%     3h23mn       1003 at  5mn02s
   Nug15   15   1150 (OPT)    1140       0.86%     6h14mn       1131 at  7mn20s
   Nug16a  16   1610 (OPT)    1597       0.80%     2h41mn       1581 at  7mn21s   
   Nug16b  16   1240 (OPT)    1217       1.85%     7h43mn       1201 at  7mn12s
   Nug17   17   1732 (OPT)    1206	 1.50%    13h57mn	1685 at  9mn56s		       
   Nug18   18   1930 (OPT)    1892	 1.97%    13h06mn       1867 at 11mn33s
   Nug20   20   2570 (OPT)    2503       2.60%    14h45mn       2464 at 14mn48s
   Nug21   21   2438 (OPT)    2378	 2.46%    22h33mn       2329 at 14mn31s
   Nug22   22   3596 (OPT)    3519       2.14%    21h51mn       3424 at 13mn58s 
   Nug24   24   3488 (OPT)    3392       2.75%    19h25mn 	3284 at 18mn30s
   Nug25   25   3744 (OPT)    3617       3.39%    19h55mn	3463 at 20mn33s
   Nug27   27   5234 (OPT)    5107  	 2.43%    20h54mn 	4820 at 20mn35s
   Nug28   28   5166 (OPT)    5003       3.16%    22h28mn	4712 at 26mn56s
   Nug30   30   6124 (OPT)    5912       3,46%    24h00mn       5496 at 29mn37s

C. Roucairol [Roucairol:87]

   name   n     feas.sol.    Our Bound   Our gap  CPU time  Intermediate Bound
   ---------------------------------------------------------------------------
   Rou12  12   235528 (OPT)   235521     0.003%   7h41mn      235343 at 1h00mn
   Rou15  15   354210 (OPT)   349920     1.21%   23h39mn      349002 at 2h24mn
   Rou20  20   725522 (OPT)   693798     4.37%   23h42mn      691240 at 3h02mn

M. Scriabin and R.C. Vergin [ScVe:75]

   name   n      solution     Our Bound   Our gap    CPU time  Intermediate Bound
   ---------------------------------------------------------------------------------
   Scr12  12    31410 (OPT)   31409        0.003%  10h56mn      31298 at    7mn34s
   Scr15  15    51140 (OPT)   51140        0%       8h03mn      50889 at   10mn39s
   Scr20  20   110030 (OPT)  106251        3.43%   21h50mn     105055 at 1h57mn

E.D. Taillard [Taillard:91,Taillard:94]

   name    n    feas.sol.       Our bound  Our gap      CPU time  Intermediate Bound
   ------------------------------------------------------------------------------------
   Tai12a  12    224416 (OPT)    2244416   0%(feasible)  3mn54s
   Tai15a  15    388214 (OPT)    376833    2.93%         23h41mn   373526 at 20mn42s
   Tai17a  17    491812 (OPT)    475837    3.25%         23h49mn   468922 at 25mn13s
   Tai20a  20    703482 (OPT)    670013    4.75%         24h       658710 at 29mn59s    
   Tai30a  30   1818146 (Ro-TS) 1695391    6.75%         24h       1547342 at 17mn28s

		Tai30a: Previous best bound 1529135 (SDP) (gap=15.90 %)

		(RO-Ts): robust tabu search [Taillard:91,Taillard:94]

		(SDP):a semidefinite programming bound [ZhKaReWo:96]

U.W. Thonemann and A. Bölte [ThBo:94]

   name     n       feas.sol.       Our bound   Our gap  CPU time  Intermediate Bound
   -----------------------------------------------------------------------------------
   Tho30    30    149936 (OPT)       141735      5.47%   21h51mn    122940 at 32mn50s

GO BACK TO MAIN PAGE OF SDP_S

RETOUR A LA PAGE PRINCIPALE DE SDP_S