کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478448 | 1446086 | 2012 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A column generation approach for the unconstrained binary quadratic programming problem A column generation approach for the unconstrained binary quadratic programming problem](/preview/png/478448.png)
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.
► We propose a column generation approach to 0–1 quadratic binary problems.
► A mixed binary linear model represented by a graph is partitioned in clusters.
► Computational experiments were performed using hard instances of literature.
Journal: European Journal of Operational Research - Volume 217, Issue 1, 16 February 2012, Pages 69–74