Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from SciELO through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Column generation with clusters for the unconstrained binary quadratic programming problem

Full text
Author(s):
Geraldo Regis Mauri [1] ; Luiz Antonio Nogueira Lorena [2]
Total Authors: 2
Affiliation:
[1] Universidade Federal do Espírito Santo. Departamento de Engenharia Rural. Centro de Ciências Agrárias - Brasil
[2] Instituto Nacional de Pesquisas Espaciais. Laboratório Associado de Computação e Matemática Aplicada - Brasil
Total Affiliations: 2
Document type: Journal article
Source: Gestão & Produção; v. 16, n. 4, p. 515-525, 2009-12-00.
Abstract

This paper proposes a new alternative of column generation (GC) based on the lagrangean relaxation with clusters (LagClus) to solve the Unconstrained Binary Quadratic Programming Problem (PQ). The PQ is a classical non-linear problem of optimizing a quadratic function by suitable choices of binary decisions variables. The proposed GC treats a mixed binary linear model (PQL) of PQ with constraints represented by a graph and divided through a partitioning heuristic. Besides finding feasible solutions the proposed method still presents two alternative ways to find bounds for PQ. Several computational experiments were performed using hard instances with different features. GC is compared to traditional lagrangean relaxation and other methods recently proposed presenting improved results for most of these instances. (AU)