nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.07.2014

The unconstrained binary quadratic programming problem: a survey

verfasst von: Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, Yang Wang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In recent years the unconstrained binary quadratic program (UBQP) has grown in importance in the field of combinatorial optimization due to its application potential and its computational challenge. Research on UBQP has generated a wide range of solution techniques for this basic model that encompasses a rich collection of problem types. In this paper we survey the literature on this important model, providing an overview of the applications and solution methods.

Vorheriger Artikel Multi-depot vessel routing problem in a direction dependent wavefield

Nächster Artikel Mathematical programming: Turing completeness and applications to software analysis

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Alidaee B, Glover F, Kochenberger GA, Rego C (2005) A new modeling and solution approach for the number partitioning problem. J Appl Math Decis Sci 2005(2):113–121. doi:10.1155/JAMDS.2005.113 CrossRefMATHMathSciNet

Alidaee B, Kochenberger G, Lewis K, Lewis M, Wang H (2008) A new approach for modeling and solving set packing problems. Eur J Oper Res 186(2):504–512. doi:10.1016/j.ejor.2006.12.068 CrossRefMATHMathSciNet

Alidaee B, Kochenberger GA, Ahmadian A (1994) 0–1 Quadratic programming approach for optimum solutions of two scheduling problems. Int J Syst Sci 25(2):401–408. doi:10.1080/00207729408928968 CrossRefMATHMathSciNet

Alkhamis TM, Hasan M, Ahmed MA (1998) Simulated annealing for the unconstrained quadratic pseudo-Boolean function. Eur J Oper Res 108(3):641–652. doi:10.1016/S0377-2217(97)00130-6 CrossRefMATH

Amini MM, Alidaee B, Kochenberger GA (eds) (1999) A scatter search approach to unconstrained quadratic binary programs. New ideas in optimization. McGraw-Hill Ltd., London

Barahona F (1986) A solvable case of quadratic 0–1 programming. Discret Appl Math 13(1):23–26. doi:10.1016/0166-218X(86)90065-X CrossRefMATHMathSciNet

Barahona F, Grotschel M, Junger M, Reinelt G (1988) An application of combinatorial optimization to statistical. Oper Res 36(3):493CrossRefMATH

Barahona F, Junger M, Reinelt G (1989) Experiments in quadratic 0–1 programming. Math Program 44:127–137CrossRefMATHMathSciNet

Beck A, Teboulle M (2000) Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J Optim 11(1):179–188CrossRefMATHMathSciNet

Beasley JE (1998) Heuristic algorithms for the unconstrained binary quadratic programming problem. PhD thesis, Imperial College, England

Billionnet A, Elloumi S (2007) Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math Program 109(1):55–68CrossRefMATHMathSciNet

Billionnet A, Sutter A (1994) Minimization of a quadratic pseudo-Boolean function. Eur J Oper Res 78(1):106–115. doi:10.1016/0377-2217(94)90125-2 CrossRefMATH

Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. In: Handbook of combinatorial optimization. Springer, Berlin, pp 1–74

Boros E, Hammer P, Sun X (1989) The DDT method for quadratic 0–1 minimization. RUTCOR Research Center, RRR:39–89

Boros E, Hammer PL (1991) The max-cut problem and quadratic 0–1 optimization polyhedral aspects, relaxations and bounds. Ann Oper Res 33(1–4):151–180CrossRefMATHMathSciNet

Boros E, Hammer PL (2002) Pseudo-Boolean optimization. Discret Appl Math 123(1–3):155–225. doi:10.1016/S0166-218X(01)00341-9 CrossRefMATHMathSciNet

Boros E, Hammer PL, Tavares G (2006) Preprocessing of Unconstrained Quadratic Binary Optimization. Rutcor Research Report, vol 13

Boros E, Hammer PL, Tavares G (2007) Local search heuristics for quadratic unconstrained binary optimization (QUBO). J Heuristics 13(2):99–132CrossRef

Cai Y, Wang J, Yin J, Zhou Y (2011) Memetic clonal selection algorithm with EDA vaccination for unconstrained binary quadratic programming problems. Expert Syst Appl 38(6):7817–7827. doi:10.1016/j.eswa.2010.12.124 CrossRef

Carraesi P, Malucelli F, Farinaccio F (1995) Testing optimality for quadratic 0-1 unconstrained problems. ZOR-Math Methods Oper Res 42:295–311CrossRefMathSciNet

Carraesi P, Farinaccio F, Malucelli F (1999) Testing optimality for quadratic 0-1 problems. Math Program 85:407–421CrossRefMathSciNet

Carter MW (1984) The indefinite zero-one quadratic problem. Discret Appl Math 7(1):23–44CrossRefMATH

De Simone C, Diehl M, Jünger M, Mutzel P, Reinelt G, Rinaldi G (1995) Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm. J Stat Phys 80(1–2):487–496CrossRefMATH

Douiri SM, Elbernouss S (2012) The unconstrained binary quadratic programming for the sum coloring problem. Mod Appl Sci 6(9):26–33. doi:10.5539/mas.v6n9p26 CrossRef

Gao D, Ruan N (2010) Solutions to quadratic minimization problems with box and integer constraints. J Global Optim 47:463–484. doi:10.1007/s10898-009-9469-0 CrossRefMATHMathSciNet

Glover F, Alidaee B, Rego C, Kochenberger G (2002) One-pass heuristics for large-scale unconstrained binary quadratic problems. Eur J Oper Res 137(2):272–287. doi:10.1016/S0377-2217(01)00209-0 CrossRefMATHMathSciNet

Glover F, Kochenberger G, Alidaee B, Amini M (1999) Tabu search with critical event memory: an enhanced application for binary quadratic programs. In: Meta-Heuristics. Springer, Berlin, pp 93–109

Glover F, Kochenberger GA, Alidaee B (1998) Adaptive memory tabu search for binary quadratic programs. Manag Sci 44(3):336–345CrossRefMATH

Glover F, Lü Z, Hao J-K (2010) Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR 8(3):239–253CrossRefMATHMathSciNet

Gueye S, Michelon P (2009) A linearization framework for unconstrained quadratic (0-1) problems. Discret Appl Math 157(6):1255–1266. doi:10.1016/j.dam.2008.01.028 CrossRefMATHMathSciNet

Gulati VP, Gupta SK, Mittal AK (1984) Unconstrained quadratic bivalent programming problem. Eur J Oper Res 15(1):121–125. doi:10.1016/0377-2217(84)90055-9 CrossRefMATHMathSciNet

Hammer P, Shlifer E (1971) Applications of pseudo-Boolean methods to economic problems. Theor Decis 1(3):296–308. doi:10.1007/BF00139572 CrossRefMATH

Hammer PL, Rudeanu S (1968) Boolean methods in operations research and related areas, vol 5. Springer, BerlinCrossRefMATH

Hanafi S, Rebai AR, Vasquez M (2013) Several versions of the devour digest tidy-up heuristic for unconstrained binary quadratic problems. J Heuristics 19(4):645–677CrossRef

Hansen P (1979) Methods of nonlinear 0-1 programming. Ann Discret Math 5:53–70. doi:10.1016/S0167-5060(08)70343-1 CrossRefMATH

Hansen P, Jaumard B (1990) Algorithms for the maximum satisfiability problem. Computing 44(4):279–303CrossRefMATHMathSciNet

Hansen P, Jaumard B, Mathon V (1993) State-of-the-art survey-constrained nonlinear 0-1 programming. ORSA J Comput 5(2):97–119CrossRefMATHMathSciNet

Hansen P, Jaumard B, Meyer C (2000) Exact sequential algorithms for additive clustering. Groupe d’études et de recherche en analyse des décisions, Montréal

Helmberg C, Rendl F (1998) Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes. Math Program Ser B 82(3):291–315CrossRefMATHMathSciNet

Huang H-X, Pardalos PM, Prokopyev OA (2006) Lower bound improvement and forcing rule for quadratic binary programming. Comput Optim Appl 33(2–3):187–208CrossRefMATHMathSciNet

Iasemidis L, Pardalos P, Sackellares J, Shiau D-S (2001) Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures. J Comb Optim 5(1):9–26CrossRefMATHMathSciNet

Jeyakumar V, Rubinov AM, Wu ZY (2007) Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions. Math Program Ser A 110:521–541. doi:10.1007/s10107-006-0012-5 CrossRefMATHMathSciNet

Kalantari B, Bagchi A (1990) An algorithm for quadratic zero-one programs. Naval Res Logist (NRL) 37(4):527–538CrossRefMathSciNet

Katayama K, Narihisa H (2001) Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem. Eur J Oper Res 134(1):103–119. doi:10.1016/S0377-2217(00)00242-3 CrossRefMATHMathSciNet

Katayama K, Tani M, Narihisa H (2000) Solving large binary quadratic programming problems by effective genetic local search algorithm. In: Proceedings of 2000 Genetic and Evolutionary Computation Conference, pp 643–650

Kernighan B, Lin S (1970) An eflicient heuristic procedure for partitioning graphs. Bell Syst Tech J 49:291–307CrossRefMATH

Kochenberger G, Alidaee B, Glover F, Wang H (2007) An effective modeling and solution approach for the generalized independent set problem. Optim Lett 1(1):111–117CrossRefMATHMathSciNet

Kochenberger G, Glover F, Alidaee B, Lewis K (2005a) Using the unconstrained quadratic program to model and solve Max 2-SAT problems. Int J Oper Res 1(1):89–100CrossRefMATHMathSciNet

Kochenberger G, Glover F, Alidaee B, Rego C (2005b) An unconstrained quadratic binary programming approach to the vertex coloring problem. Ann Oper Res 139(1–4):229–241. doi:10.1007/s10479-005-3449-7 CrossRefMATHMathSciNet

Kochenberger G, Glover F, Alidaee B, Wang H (2005c) Clustering of microarray data via clique partitioning. J Comb Optim 10(1):77–92CrossRefMATHMathSciNet

Kochenberger GA, Hao J-K, Lü Z, Wang H, Glover F (2013) Solving large scale max cut problems via tabu search. J Heuristics 19(4):565–571CrossRef

Krarup J, Pruzan P (1978) Computer-aided layout design. In: Balinski ML, Lemarechal C (eds) Mathematical Programming in Use, vol 9. Mathematical Programming Studies. Springer, Berlin, pp 75–94. doi:10.1007/BFb0120827

Laughhunn D (1970) Quadratic binary programming with application to capital-budgeting problems. Oper Res 18(3):454–461CrossRefMATH

Lewis M, Alidaee B, Glover F, Kochenberger G (2009) A note on xQx as a modelling and solution framework for the Linear Ordering Problem. Int J Oper Res 5(2):152–162CrossRefMATH

Lewis M, Alidaee B, Kochenberger G (2005) Using xQx to model and solve the uncapacitated task allocation problem. Oper Res Lett 33(2):176–182. doi:10.1016/j.orl.2004.04.014 CrossRefMATHMathSciNet

Lewis M, Kochenberger G, Alidaee B (2008) A new modeling and solution approach for the set-partitioning problem. Comput Oper Res 35(3):807–813. doi:10.1016/j.cor.2006.04.002 CrossRefMATHMathSciNet

Lewis M, Kochenberger G, Wang H, Glover F (2013) Exact Solutions to Generalized Vertex Covering Problems: A Comparison of Two Models. working paper

Li D, Sun XL, Liu CL (2012) An exact solution method for unconstrained quadratic 0 1 programming: a geometric approach. J Global Optim 52(4):797–829CrossRefMATHMathSciNet

Li G (2012) Global quadratic minimization over bivalent constraints: necessary and sufficient global optimality condition. J Optim Theory 52:710–726. doi:10.1007/s10957-011-9930-3 CrossRef

Lodi A, Allemand K, Liebling TM (1999) An evolutionary heuristic for quadratic 0–1 programming. Eur J Oper Res 119(3):662–670. doi:10.1016/S0377-2217(98)00359-2 CrossRefMATH

Lu C, Fang A, Jin Q, Wang Z, Xing W (2011) KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems. SIAM J Optim 21(4):1475–1490CrossRefMATHMathSciNet

Lü Z, Glover F, Hao J-K (2010a) A hybrid metaheuristic approach to solving the UBQP problem. Eur J Oper Res 207(3):1254–1262. doi:10.1016/j.ejor.2010.06.039 CrossRefMATH

Lü Z, Hao J-K, Glover F (2010b) A study of memetic search with multi-parent combination for UBQP. In: Evolutionary Computation in Combinatorial Optimization. Springer, Berlin, pp 154–165

Lü Z, Hao J-K, Glover F (2011) Neighborhood analysis: a case study on curriculum-based course timetabling. J Heuristics 17(2):97–118. doi:10.1007/s10732-010-9128-0 CrossRef

Mahdavi Pajouh F, Balasundaram B, Prokopyev OA (2013) On characterization of maximal independent sets via quadratic optimization. J Heuristics 19(4):629–644CrossRef

Mauri GR, Lorena LAN (2011) Lagrangean decompositions for the unconstrained binary quadratic programming problem. Int Trans Oper Res 18(2):257–270. doi:10.1111/j.1475-3995.2009.00743.x CrossRefMATHMathSciNet

Mauri GR, Lorena LAN (2012a) A column generation approach for the unconstrained binary quadratic programming problem. Eur J Oper Res 217(1):69–74. doi:10.1016/j.ejor.2011.09.016 CrossRefMATHMathSciNet

Mauri GR, Lorena LAN (2012b) Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem. Comput Oper Res 39(7):1577–1581. doi:10.1016/j.cor.2011.09.008 CrossRefMATHMathSciNet

Merz P, Freisleben B (1999) Genetic algorithms for binary quadratic programming. In: Proceedings of the genetic and evolutionary computation conference, Citeseer, pp 417–424

Merz P, Freisleben B (2002) Greedy and local search heuristics for unconstrained binary quadratic programming. J Heuristics 8(2):197–213CrossRefMATH

Merz P, Katayama K (2004) Memetic algorithms for the unconstrained binary quadratic programming problem. Biosystems 78(1–3):99–118. doi:10.1016/j.biosystems.2004.08.002 CrossRef

Neven H, Rose G, Macready WG (2008) Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization. arXiv:0804.4457

Oosten M, Rutten J, Spieksma F (2001) The Clique partitioning problem: facets and patching facets. Networks 38(4):209–226CrossRefMATHMathSciNet

Palubeckis G (1995) A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming. Computing 54(4):283–301. doi:10.1007/BF02238228 CrossRefMATHMathSciNet

Palubeckis G (2004) Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann Oper Res 131(1–4):259–282. doi:10.1023/B:ANOR.0000039522.58036.68 CrossRefMATHMathSciNet

Palubeckis G (2006) Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17(2):279–296MATHMathSciNet

Palubeckis G, Tomkevicius A (2002) GRASP implementations for the unconstrained binary quadratic optimization problem. Inf Technol Control 24:14–20

Pan S, Tan T, Jiang Y (2008) A global continuation algorithm for solving binary quadratic programming problems. Comput Optim Appl 41(3):349–362. doi:10.1007/s10589-007-9110-4 CrossRefMATHMathSciNet

Pardalos PM, Jha S (1991) Graph separation techniques for quadratic zero-one programming. Comput Math Appl 21(6–7):107–113. doi:10.1016/0898-1221(91)90165-Z CrossRefMATHMathSciNet

Pardalos PM, Jha S (1992) Complexity of uniqueness and local search in quadratic 0-1 programming. Oper Res Lett 11(2):119–123. doi:10.1016/0167-6377(92)90043-3 CrossRefMATHMathSciNet

Pardalos PM, Prokopyev OA, Busygin S (2006) Continuous approaches for solving discrete optimization problems. In: Handbook on modelling for discrete optimization. Springer, Berlin, pp 39–60

Pardalos PM, Rodgers GP (1990a) Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45(2):131–144CrossRefMATHMathSciNet

Pardalos PM, Rodgers GP (1990b) Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture. Ann Oper Res 22(1–4):271–292CrossRefMATHMathSciNet

Pardalos PM, Rodgers GP (1992) A branch and bound algorithm for the maximum clique problem. Comput Oper Res 19(5):363–375. doi:10.1016/0305-0548(92)90067-F CrossRefMATH

Pardalos PM, Xue J (1994) The maximum clique problem. J Global Optim 4(3):301–328CrossRefMATHMathSciNet

Pham Dinh T, Nguyen Canh N, Le Thi HA (2010) An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs. J Global Optim 48(4):595–632CrossRefMATHMathSciNet

Picard J-C (1976) Maximal closure of a graph and applications to combinatorial problems. Manag Sci 22(11):1268–1272. doi:10.2307/2630227 CrossRefMATHMathSciNet

Pinar MC (2004) Sufficient global optimality conditions for bivalent quadratic optimization. J Optim Theory Appl 122(2):433–440CrossRefMATHMathSciNet

Rao MR (1971) Cluster analysis and mathematical programming. J Am Stat Assoc 66(335):622–626. doi:10.1080/01621459.1971.10482319 CrossRefMATH

Rhys J (1970) A selection problem of shared fixed costs and network flows. Manag Sci 17(3):200–207CrossRefMATH

Shylo V, Shylo O (2011) Systems analysis solving unconstrained binary quadratic programming problem by global equilibrium search. Cybern Syst Anal 47(6):889–897. doi:10.1007/s10559-011-9368-5 CrossRef

Sun XL, Liu CL, Li D, Gao JJ (2012) On duality gap in binary quadratic programming. J Global Optim 53:255–269. doi:10.1007/s10898-011-9683-4 CrossRefMATHMathSciNet

Wang F, Xu Z (2013) Metaheuristics for robust graph coloring. J Heuristics 19(4):529–548CrossRef

Wang H, Alidaee B, Glover F, Kochenberger G (2006) Solving group technology problems via clique partitioning. Int J Flex Manuf Syst 18(2):77–77CrossRefMATH

Wang J, Zhou Y, Yin J (2011) Combining tabu Hopfield network and estimation of distribution for unconstrained binary quadratic programming problem. Expert Syst Appl 38(12):14870–14881. doi:10.1016/j.eswa.2011.05.060 CrossRef

Wang Y, Lü Z, Glover F, Hao J-K (2012a) A multilevel algorithm for large unconstrained binary quadratic optimization. In: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems. Springer, Berlin, pp 395–408

Wang Y, Lü Z, Glover F, Hao J-K (2012b) Path relinking for unconstrained binary quadratic programming. Eur J Oper Res 223(3):595–604. doi:10.1016/j.ejor.2012.07.012 CrossRef

Wang Y, Lü Z, Glover F, Hao J-K (2012c) Probabilistic GRASP-tabu search algorithms for the UBQP problem. Comput Oper Res 40:3100–3107CrossRef

Williams HP (1985) Model building in linear and integer programming. In: Schittkowski K (ed) Computational mathematical programming, vol 15. NATO ASI Series. Springer, Berlin, pp 25–53. doi:10.1007/978-3-642-82450-0_2

Witzgall C (1975) Mathematical methods of site selection for Electronic Message Systems (EMS). NBS Internal report, NBS

Xia Y (2009) New optimality conditions for quadratic optimization problems with binary constraints. Optim Lett 3:253–263. doi:10.1007/s11590-008-0105-6 CrossRefMATHMathSciNet

Zheng XJ, Sun XL, Li D, Xu YF (2012) On zero duality gap in nonconvex quadratic programming problems. J Global Optim 52:229–242. doi:10.1007/s10898-011-9660-y CrossRefMATHMathSciNet

Titel: The unconstrained binary quadratic programming problem: a survey
verfasst von: Gary Kochenberger
Jin-Kao Hao
Fred Glover
Mark Lewis
Zhipeng Lü
Haibo Wang
Yang Wang
Publikationsdatum: 01.07.2014
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9734-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2014

On risk-averse maximum weighted subgraph problems

Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery

Multi-depot vessel routing problem in a direction dependent wavefield

An integer programming framework for critical elements detection in graphs

Minimum number of disjoint linear forests covering a planar graph

A greedy algorithm for the fault-tolerant connected dominating set in a general graph