DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
qudratic combinatorial optimization models: why they are needed, and a few approaches to solve them
We will review a few problems that can be formulated as quadratic optimization models, as well as some techniques to olve them optimally (various degrees of RLT), make them easier to solve by BB (convexification using SDP), or solve them  pproximately (convex hull relaxation). We will present computational results and discuss areas of possible future improvement.

Selected publications:

W.P. Adams, M. Guignard, P.M. Hahn, and W.L. Hightower, "A Level-2 Reformulation-Linearization technique bound for the quadratic assignment problem," European Journal of Operational Research, 180(3), 983996 (2007).

P.M. Hahn, B-J. Kim, W. L. Hightower, T. Stützle, S. Kanthak, H. Samra, Z. Ding, and M. Guignard, "The quadratic three-dimensional assignment problem: exact and heuristic solution methods," European Journal of Operational Research, 184(2), 416428 (2008).

P. M. Hahn, B.-J. Kim, M. Guignard, J.M. Smith and Y.-R. Zhu, "An Algorithm for the Generalized Quadratic Assignment Problem," Computational Optimization and Applications, 2008, Vol. 40, Iss. 3, 351-372. Received the 2008 COAP Best Paper Award.

 

A. Pessoa, P.M. Hahn, M. Guignard, and Y.-R. Zhu, " Algorithms for the Generalized Quadratic Assignment Problem combining Lagrangean Decomposition and the Reformulation-Linearization Technique," European Journal of Operational Research, 2010, 206(1), 54-63. Received the first prize at the SOBRAPO meeting, Brazil, 2008. 
 
P.M. Hahn, Y.-R. Zhu, M. Guignard, and J.M. Smith, "Exact Solution of Emerging Quadratic Assignment Problems," invited paper, The International Transactions on Operational Research, 2010, 17(5), 525-552.

 

 

M. Guignard, "Combining Approaches to Improve Bounds." Stud. Inform. Univ. (2010), 8(2), 1-16. 
 
P. M. Hahn, Y.-R. Zhu, M. Guignard and W.L. Hightower, "A Level-3 Reformulation-linearization Technique Bound for the Quadratic Assignment Problem," forthcoming in INFORMS Journal on Computing.

 

A. Ahlatçioglu, M. Bussieck, M. Esen, M. Guignard, J.H. Jagla and A. Meeraus, "Combining QCR and CHR for Convex Quadratic Pure 0-1 Programming Problems with Linear Constraints," forthcoming in Annals of Operations Research.