Lagrangean decompositions for the unconstrained binary quadratic programming problem

Lagrangean decompositions for the unconstrained binary quadratic programming problem

0.00 Avg rating0 Votes
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: ,
Keywords: duality, Lagrangian decomposition, gradient search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.