Article ID: | iaor20111807 |
Volume: | 18 |
Issue: | 2 |
Start Page Number: | 257 |
End Page Number: | 270 |
Publication Date: | Mar 2011 |
Journal: | International Transactions in Operational Research |
Authors: | Lorena Luiz Antonio Nogueira, Mauri Geraldo Regis |
Keywords: | duality, Lagrangian decomposition, gradient search |
The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.