EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2613. Improving Lower Bounds for Large Scale QAPs
Invited abstract in session TA-30: Parallel Solvers, stream Software for Optimization.
Tuesday, 8:30-10:00Room: 064 (building: 208)
Authors (first author is the speaker)
| 1. | Koichi Fujii
|
| NTT DATA Mathematical Systems Inc. | |
| 2. | Sunyoung Kim
|
| Department of Mathematics, Ewha Women's University | |
| 3. | Masakazu Kojima
|
| Chuo University | |
| 4. | Hans Mittelmann
|
| School of Math&Stats, Arizona State University | |
| 5. | Yuji Shinano
|
| Optimization, Zuse Institue Berlin |
Abstract
We report the progress of our project of solving large-scale Quadratic Assignment Problems (QAPs). We present a method that efficiently computes global lower bounds for QAPs by employing the Newton-bracketing method along with Lagrangian doubly nonnegative (DNN) relaxation. The integration of auxiliary information derived from the Newton-bracketing method, combined with the checkpoint mechanism of the parallelization framework Ubiquity Generator (UG), enables the determination of strong global lower bounds for large QAPs. This method has led to the improvement of lower bounds for several unsolved problems listed in QAPLIB, the standard benchmark for QAPs.
Keywords
- Programming, Integer
- Large Scale Optimization
- Programming, Quadratic
Status: accepted
Back to the list of papers