A column generation approach for the unconstrained binary quadratic programming problem

A column generation approach for the unconstrained binary quadratic programming problem

0.00 Avg rating0 Votes
Article ID: iaor201110462
Volume: 217
Issue: 1
Start Page Number: 69
End Page Number: 74
Publication Date: Feb 2012
Journal: European Journal of Operational Research
Authors: ,
Keywords: graphs
Abstract:

This paper proposes a column generation approach based on the Lagrangean relaxation with clusters to solve the unconstrained binary quadratic programming problem that consists of maximizing a quadratic objective function by the choice of suitable values for binary decision variables. The proposed method treats a mixed binary linear model for the quadratic problem with constraints represented by a graph. This graph is partitioned in clusters of vertices forming sub‐problems whose solutions use the dual variables obtained by a coordinator problem. The column generation process presents alternative ways to find upper and lower bounds for the quadratic problem. Computational experiments were performed using hard instances and the proposed method was compared against other methods presenting improved results for most of these instances.

Reviews

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