Skip to main content
SpringerLink
Log in

On solving a hard quadratic 3-dimensional assignment problem

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

We address the solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques we were able to solve the target instance with moderate computational effort (2.5 million nodes and 1 week of computations on a standard PC).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. The dynamism of the objective function is defined as the ratio between the maximum and minimum absolute values of the non-zero coefficients.

References

  1. Burkard, R., Dell’Amico, M., Martello, S.: Assignment problems. SIAM (2009)

  2. Fischetti, M., Liberti, L.: Orbital shrinking. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO. Lecture Notes in Computer Science, vol. 7422, pp. 48–58. Springer, New York (2012)

    Google Scholar 

  3. Fischetti, M., Monaci, M., Salvagnin, D.: Three ideas for the quadratic assignment problem. Oper Res 60(4), 954–964 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  4. Gecode Team: Gecode: Generic constraint development environment (2012). Available at http://www.gecode.org

  5. Gent, I.P., Petrie, K.E., Puget, J.F.: Symmetry in constraint programming. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 329–376. Elsevier, New York (2006)

    Chapter  Google Scholar 

  6. Hahn, P.M.: http://www.seas.upenn.edu/~hahn/

  7. Hahn, P.M., Kim, B.J., Stützle, T., Kanthak, S., Hightower, W.L., Samra, H., Ding, Z., Guignard, M.: The quadratic three-dimensional assignment problem: exact and approximate solution methods. Eur J Oper Res 184(2), 416–428 (2008)

    Article  MATH  Google Scholar 

  8. IBM: IBM ILOG Cplex Optimization Studio. http://www.cplex.com

  9. Kaufman, L., Broeckx, F.: An algorithm for the quadratic assignment problem using Benders’ decomposition. Eur J Oper Res 2, 204–211 (1978)

    Article  Google Scholar 

  10. Liberti, L.: Reformulations in mathematical programming: automatic symmetry detection and exploitation. Math Progr 131(1–2), 273–304 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  11. Linderoth, J., Margot, F., Thain, G.: Improving bounds on the football pool problem by integer programming and high-throughput computing. Inf J Comput 21(3), 445–457 (2009)

    Article  MATH  Google Scholar 

  12. Margot, F.: Exploiting orbits in symmetric ILP. Math Progr 98(1), 3–21 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  13. Margot, F.: Symmetry in integer linear programming. In: Jünger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L. (eds.) 50 Years of Integer Programming 1958–2008, pp. 647–686. Springer, New York (2010)

    Google Scholar 

  14. McKay, B.D.: Practical graph isomorphism (1981)

  15. Mittelmann, H.D., Peng, J.: Estimating bounds for quadratic assignment problems associated with hamming and manhattan distance matrices based on semidefinite programming. SIAM J Optim 20(6), 3408–3426 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  16. Østergård, P.R.J., Blass, U.: On the size of optimal binary codes of length 9 and covering radius 1. IEEE Trans Inform Theory 47(6), 2556–2557 (2001)

    Article  MathSciNet  Google Scholar 

  17. Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math Progr 126(1), 147–178 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  18. Peng, J., Mittelmann, H.D., Li, X.: A new relaxation framework for quadratic assignment problems based on matrix splitting. Math Progr Comput 2(1), 59–77 (2010)

    Article  MATH  Google Scholar 

  19. Pierskalla, W.P.: The multi-dimensional assignment problem. Oper Res 16(2), 422–431 (1968)

    Article  MATH  Google Scholar 

  20. Rehn, T.: Fundamental permutation group algorithms for symmetry computation. Master’s thesis, Otto-von-Guericke University Magdeburg (2010)

  21. Salvagnin, D.: Orbital shrinking: a new tool for hybrid MIP/CP methods. In: CPAIOR, pp. 204–215 (2013)

  22. Salvagnin, D., Walsh, T.: A hybrid MIP/CP approach for multi-activity shift scheduling. In: CP, pp. 633–646 (2012)

  23. Samra, H., Ding, Z.: Symbol mapping diversity in iterative decoding/demodulation of ARQ systems. In: ICC, pp. 3585–3589. IEEE (2003)

  24. Samra, H., Ding, Z., Hahn, P.M.: Symbol mapping diversity design for multiple packet transmissions. IEEE Trans Commun 53(5), 810–817 (2005)

    Article  Google Scholar 

  25. Stützle, T.: Iterated local search for the quadratic assignment problem. Eur J Oper Res 174(3), 1519–1539 (2006)

  26. Wu, X., Mittelmann, H.D., Wang, X., Wang, J.: On computation of performance bounds of optimal index assignment. IEEE Trans Commun 59(12), 3229–3233 (2011)

    Article  Google Scholar 

  27. Xia, Y., Yuan, Y.: A new linearization method for quadratic assignment problem. Optim Methods Software 21, 803–816 (2006)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

We thank Peter M. Hahn for providing the numerical data for the 16-PSK Q3AP instance. The work of the first author was supported in part by AFOSR under grant FA9550-12-1-0153.

Author information

Authors and Affiliations

  1. School of Mathematical and Statistical Sciences, Arizona State University, Tempe, USA

    Hans D. Mittelmann

  2. DEI, University of Padova, Padua, Italy

    Domenico Salvagnin

Authors
  1. Hans D. Mittelmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Domenico Salvagnin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Domenico Salvagnin.

Appendix: Detailed computational results

Appendix: Detailed computational results

See Table 3.

Table 3 Subproblem results
Full size table
Table 4 Aggregated results. Easy subproblems are those requiring less than 100 nodes to solve, while the hard ones are those requiring more than 100,000
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mittelmann, H.D., Salvagnin, D. On solving a hard quadratic 3-dimensional assignment problem. Math. Prog. Comp. 7, 219–234 (2015). https://doi.org/10.1007/s12532-015-0077-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-015-0077-3

Keywords

Mathematics Subject Classification

Search

Navigation