Premium
Lagrangean decompositions for the unconstrained binary quadratic programming problem
Author(s) -
Mauri Geraldo Regis,
Lorena Luiz Antonio Nogueira
Publication year - 2011
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00743.x
Subject(s) - subgradient method , quadratic programming , mathematical optimization , binary number , mathematics , linear programming , quadratic equation , quadratic unconstrained binary optimization , graph , set (abstract data type) , computer science , combinatorics , geometry , arithmetic , quantum mechanics , quantum computer , quantum , programming language , physics
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.