Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Lagrangean decompositions for the unconstrained binary quadratic programming problem

Texto completo
Autor(es):
Mauri, Geraldo Regis [1] ; Nogueira Lorena, Luiz Antonio [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Fed Univ Espirito Santo UFES, Ctr Agrarian Sci, BR-29500000 Alegre, ES - Brazil
[2] Natl Inst Space Res INPE, Lab Comp & Appl Math, BR-12227010 Sao Jose Dos Campos, SP - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: International Transactions in Operational Research; v. 18, n. 2, p. 257-270, MAR 2011.
Citações Web of Science: 4
Resumo

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. (AU)

Processo FAPESP: 04/11053-9 - Metodologia híbrida para resolução do problema dial-a-ride
Beneficiário:Geraldo Regis Mauri
Linha de fomento: Bolsas no Brasil - Doutorado