×

A column generation approach for the unconstrained binary quadratic programming problem. (English) Zbl 1244.90178

Summary: We propose 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.

MSC:

90C20 Quadratic programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, W. P.; Dearing, P. M., On the equivalence between roof duality and Lagrangean duality for unconstrained 0-1 quadratic programming problems, Discrete Applied mathematics, 48, 1, 1-20 (1994) · Zbl 0794.90038
[2] Beasley, J.E., 1998. Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical Report, Management School, Imperial College: London, UK.; Beasley, J.E., 1998. Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical Report, Management School, Imperial College: London, UK.
[3] Billionnet, A.; Elloumi, S., Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem, Mathematical Programming, 109, 55-68 (2007) · Zbl 1278.90263
[4] Billionnet, A.; Faye, A.; Soutif, E., A new upper bound for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 112, 664-672 (1999) · Zbl 0933.90049
[5] Boros, E.; Crama, Y.; Hammer, P. L., Chvatal cuts and odd cycle inequalities in quadratic 0-1 optimization, SIAM - Journal on Discrete Mathematics, 5, 2, 163-177 (1992) · Zbl 0761.90069
[6] Elloumi, S.; Faye, A.; Soutif, E., Decomposition and linearization for 0-1 quadratic programming, Annals of Operations Research, 99, 79-93 (2000) · Zbl 0990.90073
[7] Glover, F.; Kochenberger, G.; Alidaee, B., Adaptative memory tabu search for binary quadratic programs, Management Science, 44, 3, 336-345 (1998) · Zbl 0989.90072
[8] Glover, F.; Alidaee, B.; Rego, C.; Kochenberger, G., One-pass heuristics for large-scale unconstrained binary quadratic problems, European Journal of Operational Research, 137, 2, 272-287 (2002) · Zbl 1030.90074
[9] Hansen, P.; Meyer, C., Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem, Discrete Applied Mathematics, 57, 6, 1267-1290 (2009) · Zbl 1178.90251
[10] Karypis, G.; Kumar, V., Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, 48, 96-129 (1998)
[11] Narciso, M. G.; Lorena, L. A.N., Lagrangean/surrogate relaxation for generalized assignment problems, European Journal of Operational Research, 114, 165-177 (1999) · Zbl 0946.90035
[12] Palubeckis, G., Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Annals of Operations Research, 131, 259-282 (2004) · Zbl 1066.90069
[13] Pardalos, P. M.; Jha, S., Complexity of uniqueness and local search in quadratic 0-1 programming, Operations Research Letters, 11, 119-123 (1992) · Zbl 0761.90070
[14] Pardalos, P. M.; Rodgers, G. P., Computational aspect of a branch and bound algorithm for quadratic 0-1 programming, Computing, 45, 131-144 (1990) · Zbl 0721.65034
[15] Pardalos, P. M.; Prokopyev, O. A.; Shylo, O. V.; Shylo, V. P., Global equilibrium search applied to the unconstrained binary quadratic optimization problem, Optimization Methods and Software, 23, 129-140 (2008) · Zbl 1145.90430
[16] Ribeiro, G. M.; Lorena, L. A.N., Lagrangean relaxation with clusters and column generation for the manufacturer’s pallet loading problem, Computers and Operations Research, 34, 9, 2695-2708 (2007) · Zbl 1141.90514
[17] Ribeiro, G. M.; Lorena, L. A.N., Lagrangean relaxation with clusters for point-feature cartographic label placement problems, Computers and Operations Research, 35, 2129-2140 (2008) · Zbl 1163.91539
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.