Paper Info
Title
Lagrangean Decompositions For The Unconstrained Binary Quadratic Programming Problem
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.
Year
DOI
Venue
2011
10.1111/j.1475-3995.2009.00743.x
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
Keywords
Field
DocType
quadratic programming, Lagrangean decomposition, bounds
Mathematical optimization,Vertex (geometry),Quadratic unconstrained binary optimization,Subgradient method,Binary decision diagram,Quadratic equation,Duality (optimization),Quadratic programming,Mathematics,Binary number
Journal
Volume
Issue
ISSN
18
2
0969-6016
Citations 
PageRank 
References 
4
0.42
15
Authors
2
Name
Order
Citations
PageRank
Geraldo Regis Mauri1888.79
Luiz Antonio Nogueira Lorena249836.72