Abstract
A new algorithm based on global equilibrium search (GES) is developed to solve an unconstrained binary quadratic programming (UBQP) problem. It is compared with the best methods of solving this problem. The GES algorithm is shown to be better both in speed and solution quality.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
B. Alidaee, G. Kochenberger, and A. Ahmadian, “0–1 quadratic programming approach for the optimal solution of two scheduling problems,” Intern. J. Syst. Sci., 25, 401–408 (1994).
G. Gallo, P. L. Hammer, and B. Simeone, “Quadratic knapsack problems,” Math. Program., 12, 132–149 (1980).
P. M. Pardalos and J. Xue, “The maximum clique problem,” J. Global Optimiz., 4, 301–328 (1994).
Z. Lü, F. Glover, and Hao Jin-Kao, “A hybrid metaheuristic approach to solving the UBQP problem,” Eur. J. Oper. Res., 207, No. 3, 1254–1262 (2010).
G. A. Kochenberger, F. Glover, B. Alidaee, and C. Rego, “A unified modeling and solution framework for combinatorial optimization problems,” Oper. Res. Spectrum., 26, 237–250 (2004).
K. Allemand, K. Fukuda, T. M. Liebling, and E. Steiner, “A polynomial case of unconstrained zero–one quadratic optimization,” Math. Program., Ser. A, 91, 49–52 (2001).
P. M. Pardalos and S. Jha, “Complexity of uniqueness and local search in quadratic 0–1 programming,” Oper. Res. Letters, 11, 119–123 (1992).
C. Helmberg and F. Rendl, “Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes,” Math. Program., 82, 291–315 (1998).
G. A. Palubeckis, “Heuristic-based branch and bound algorithm for unconstrained quadratic zero–one programming,” Computing, 54, 283–301 (1995).
J. E. Beasley, “Heuristic algorithms for the unconstrained binary quadratic programming problem,” Working Paper, The Management School, Imperial College, London (1998).
F. Glover, G. A. Kochenberger, and B. Alidaee, “Adaptive memory tabu search for binary quadratic programs,” Manag. Sci., 44, 336–345 (1998).
G. Palubeckis, “Iterated tabu search for the unconstrained binary quadratic optimization problem,” Informatica, 17, No. 2, 279–296 (2006).
T. M. Alkhamis, M. Hasan, and M. A. Ahmed, “Simulated annealing for the unconstrained binary quadratic pseudo-boolean function,” Eur. J. Oper. Res., 108, 641–652 (1998).
K. Katayama and H. Narihisa, “Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem,” Eur. J. Oper. Res., 134, 103–119 (2001).
A. Lodi, K. Allemand, and T. M. Liebling, “An evolutionary heuristic for quadratic 0–1 programming,” Eur. J. Oper. Res., 119, 662–670 (1999).
I. Borgulya, “An evolutionary algorithm for the binary quadratic problems,” Advances in Soft Computing, 2, 3–16 (2005).
K. Katayama, M. Tani, and H. Narihisa, “Solving large binary quadratic programming problems by an effective genetic local search algorithm,” in: Proc. Genetic and Evolutionary Computation Conference (GECCO99), Morgan Kaufmann (2000), pp. 643–650.
P. Merz and B. Freisleben, “Genetic algorithms for binary quadratic programming,” in: Proc. Genetic and Evolutionary Computation Conference (GECCO99), Morgan Kaufmann (1999), pp. 417–424.
P. Merz and K. Katayama, “Memetic algorithms for the unconstrained binary quadratic programming problem,” BioSystems, 78, 99–118 (2004).
M. Amini, B. Alidaee, and G. A. Kochenberger, “A scatter search approach to unconstrained quadratic binary programs,” in: New Methods in Optimization, McGraw-Hill, New York (1999), pp. 317–330.
P. M. Pardalos, O. A. Prokopyev, O. V. Shylo, and V. P. Shylo, “Global equilibrium search applied to the unconstrained binary quadratic optimization problem,” Optimization Methods and Software, 23, 129–140 (2008).
V. P. Shilo, “The method of global equilibrium search,” Cybern. Syst. Analysis, 35, No. 1, 68–74 (1999).
I. V. Sergienko and V. P. Shilo, Discrete Optimization Problems: Challenges, Solution Methods, Analysis [in Russian], Naukova Dumka, Kyiv (2003).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 68–78, November–December 2011.
Rights and permissions
About this article
Cite this article
Shylo, V.P., Shylo, O.V. Systems Analysis; Solving unconstrained binary quadratic programming problem by global equilibrium search. Cybern Syst Anal 47, 889–897 (2011). https://doi.org/10.1007/s10559-011-9368-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-011-9368-5