QAPLIB-A comparison of Lower Bounds

Instance

Optimum

GLB62

RRD95

HG98

KCCEB99

AB01

RRRP02

RS03

R04

BV04

HH01

HZ07

Had16

3720

3358

3558

3553

3595

3699

3720**

3672

3720*

3719.1**

Had18

5358

4776

5083

5078

5143

5317

5356

5299

5358*

5357.0**

Had20

6922

6166

6571

6567

6677

6885

6920

6811

6922*

6920.0

Kra30a

88900

68360

76003

75853

75566

68572

77647

86678

86247

Kra30b

91420

69065

76752

76562

76235

69021

81156

87699

87107

Nug12

578

493

523

523

521

498

        578*

557

567

568

578*

577.2**

Nug15

1150

963

1041

1039

1033

1001

1122

1138

1141

1150*

1149.1**

Nug18

1930

1930*

Nug20

2570

2057

2182

2179

2173

2290

2451

2494

2506

2508

2568.1**

Nug22

3596

3511

3594.04**

Nug30

6124

4539

4805

4793

4785

5365

5803

5934

5770

Rou15

354210

298548

324869

323943

323589

303777

333287

348838

350207

354210*

354210*

Rou20

725520

559948

643346

642058

641425

607822

663833

691124

695123

699390

725314.4

Tai20a

703482

580674

617206

616644

585139

637300

671685

675870

703482*

Tai25a

1167256

962417

1006749

1005978

983456

1041337

1112862

1091653

Tai30a

1818146

1504688

1566309

1565313

1518059

1652186

1706875

1686290

Tho30

149936

90578

100784

99995

99855

124684

136059

142814

136708

* Problem solved exactly by lower bound calculation

**Optimumverified by bound calculation

Table 1 – Genesis of Lower Bounds.

Table 1 presents a comparison of lower bounds for a select group of QAPLIB instances. In the Table, GLB62 is the Gilmore-Lawler bound from Gilmore (1962); RRD95 is the interior-point bound from Resende et al. (1995); HG98 is the RLT-1 dual ascent bound from Hahn and Grant (1998); KCCEB99 is the dual-based bound from Karisch et al. (1999); AB01 is the quadratic programming bound from Anstreicher and Brixius (2001); RRRP02 is the RLT-2 interior point bound from Ramakrishnan et al. (2002); RS03 is the SDP bound from Rendl and Sotirov (2003); R04 is the SDP bound from Roupin (2004); BV04 is the lift-and-project SDP bound from Burer and Vandenbussche (2006); HH01 is the Hahn-Hightower RLT-2 dual ascent bound from Adams et al. (2007); and HZ07 is the Hahn-Zhu RLT-3 bound from Zhu (2007). The best lower bounds are in the shaded cells of the table.  Lower bounds are listed in the Table in order of date they were published, with the exception of HH01.  The HH01 bound was first published in 2001, but the HH01 bound calculations in Table 1 were recently calculated and
thus were placed just before the rightmost column.  It should be noted that HH01 is a dual ascent procedure that underestimates the RLT-2 lower bound described in Adams,
et al. (2007) and in Ramakrishnan et al. (2002).
Also, HG98 is a dual ascent procedure that underestimates the interior-point bound from Resende
et al. (2002).

The Rendl and Sotirov bound is also found in Fischer, I. et al. (2006).  In an as yet unfinished technical report, Povh and Rendl (2006) point out that the strongest relaxation (R3) from Rendl and Sotirov (2003) and the relaxation from Burer and Vandenbussche (2004) are actually the same.  The differing lower bound values in the two papers are due to the fact that Rendl and Sotirov use the bundle method, which gives only underestimates of the true
bound, while Burer and Vandenbussche are able to compute this bound more accurately 
Adams, W.P., M. Guignard, P.M. Hahn, and W.L. Hightower, 2007, A level-2 reformulation-linearization technique bound for the quadratic assignment problem, European Journal of Operational Research 180983-996.  First available as Working Paper 01-04, Systems Engineering Department, University of Pennsylvania, 2001 (Authors: P.M. Hahn, W.L. Hightower, T.A. Johnson, M. Guignard, and C. Roucairol).

 

Anstreicher, K.M., and N.W. Brixius, 2001, A new bound for the quadratic assignment problem based on convex quadratic programming, Mathematical Programming 89, 341-357.

 

Burer, S. and Vandenbussche, D. (2006) “Solving Lift-and-project Relaxations of Binary Integer Programs,” SIAM Journal on Optimization, 16, 726-750.  First available in 2004 on http://www.optimization-online.org/DB_HTML/2004/06/890.html.

 

Fischer, I., Gruber, G., Rendl, F. and Sotirov, R. (2006) ÒComputational experience with a bundle approach for semidefinite cutting plane relaxations of max-Cut and equipartition,Ó Mathematical Programming 105, 451-469.

 

Gilmore, P.C., 1962, Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10, 305-313.

 

Hahn, P.M., and T.L. Grant, 1998, Lower bounds for the quadratic assignment problem based upon a dual formulation, Operations Research 46, 912-922.

 

Karisch, S.E., E. ‚ela, J. Clausen, and T. Espersen, 1999, A dual framework for lower bounds of the quadratic assignment problem based on linearization, Computing 63, 351-403.

 

Povh, J and Rendl, F., (2006) ÒCopositive and Semidefinite Relaxations of the Quadratic Assignment Problem,Ó unfinished Technical Report, Department of Mathematics, University of Klagenfurt.

 

Ramakrishnan, K.G., M.G.C. Resende, B. Ramachandran, and J.F. Pekny, 2002, Tight QAP bounds via linear programming, in: Pardalos, P.M., A. Migdalas, and R.E. Burkard (Eds.), Combinatorial and Global Optimization, World Scientific Publishing, Singapore, 297-303.

 

Rendl, F., and R. Sotirov, (2007) Bounds for the quadratic assignment problem using the bundle method, Mathematical Programming 109, 505-524. First available in 2003 as a Technical Report, Department of Mathematics, University of Klagenfurt.

 

Resende, M.G.C., K.G. Ramakrishnan, and Z. Drezner, 1995, Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming, Operations Research 43,
781-791.

 

Zhu, Y-R., ÒRecent Advances and Challenges in Quadratic Assignment and Related Problems,Ó Ph.D. Dissertation, University of Pennsylvania, 2007.