IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v28y2014i1d10.1007_s10878-014-9734-0.html
   My bibliography  Save this article

The unconstrained binary quadratic programming problem: a survey

Author

Listed:
  • Gary Kochenberger

    (University of Colorado at Denver)

  • Jin-Kao Hao

    (Université d’Angers)

  • Fred Glover

    (OptTek Inc.)

  • Mark Lewis

    (Missouri Western State University)

  • Zhipeng Lü

    (Huazhong University of Science and Technology)

  • Haibo Wang

    (Texas A&M International University)

  • Yang Wang

    (Northwestern Polytechnical University)

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.

Suggested Citation

  • Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    • Handle: RePEc:spr:jcomop:v:28:y:2014:i:1:d:10.1007_s10878-014-9734-0
    DOI: 10.1007/s10878-014-9734-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-014-9734-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-014-9734-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Guoyin Li, 2012. "Global Quadratic Minimization over Bivalent Constraints: Necessary and Sufficient Global Optimality Condition," Journal of Optimization Theory and Applications, Springer, vol. 152(3), pages 710-726, March.
    2. Glover, Fred & Alidaee, Bahram & Rego, Cesar & Kochenberger, Gary, 2002. "One-pass heuristics for large-scale unconstrained binary quadratic problems," European Journal of Operational Research, Elsevier, vol. 137(2), pages 272-287, March.
    3. J. M. W. Rhys, 1970. "A Selection Problem of Shared Fixed Costs and Network Flows," Management Science, INFORMS, vol. 17(3), pages 200-207, November.
    4. X. Sun & C. Liu & D. Li & J. Gao, 2012. "On duality gap in binary quadratic programming," Journal of Global Optimization, Springer, vol. 53(2), pages 255-269, June.
    5. David Gao & Ning Ruan, 2010. "Solutions to quadratic minimization problems with box and integer constraints," Journal of Global Optimization, Springer, vol. 47(3), pages 463-484, July.
    6. M. Ç. Pinar, 2004. "Sufficient Global Optimality Conditions for Bivalent Quadratic Optimization," Journal of Optimization Theory and Applications, Springer, vol. 122(2), pages 433-440, August.
    7. Billionnet, A. & Sutter, A., 1994. "Minimization of a quadratic pseudo-Boolean function," European Journal of Operational Research, Elsevier, vol. 78(1), pages 106-115, October.
    8. Tao Pham Dinh & Nam Nguyen Canh & Hoai Le Thi, 2010. "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs," Journal of Global Optimization, Springer, vol. 48(4), pages 595-632, December.
    9. Katayama, Kengo & Narihisa, Hiroyuki, 2001. "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 134(1), pages 103-119, October.
    10. Alidaee, Bahram & Kochenberger, Gary & Lewis, Karen & Lewis, Mark & Wang, Haibo, 2008. "A new approach for modeling and solving set packing problems," European Journal of Operational Research, Elsevier, vol. 186(2), pages 504-512, April.
    11. D. Li & X. Sun & C. Liu, 2012. "An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach," Journal of Global Optimization, Springer, vol. 52(4), pages 797-829, April.
    12. D. J. Laughhunn, 1970. "Quadratic Binary Programming with Application to Capital-Budgeting Problems," Operations Research, INFORMS, vol. 18(3), pages 454-461, June.
    13. Vaithilingam Jeyakumar & Zhiyou Wu, 2007. "Conditions For Global Optimality Of Quadratic Minimization Problems With Lmi Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 24(02), pages 149-160.
    14. Panos M Pardalos & Oleg A Prokopyev & Stanislav Busygin, 2006. "Continuous Approaches for Solving Discrete Optimization Problems," International Series in Operations Research & Management Science, in: Gautam Appa & Leonidas Pitsoulis & H. Paul Williams (ed.), Handbook on Modelling for Discrete Optimization, chapter 0, pages 39-60, Springer.
    15. Fred Glover & Gary A. Kochenberger & Bahram Alidaee, 1998. "Adaptive Memory Tabu Search for Binary Quadratic Programs," Management Science, INFORMS, vol. 44(3), pages 336-345, March.
    16. Gintaras Palubeckis, 2004. "Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem," Annals of Operations Research, Springer, vol. 131(1), pages 259-282, October.
    17. X. Zheng & X. Sun & D. Li & Y. Xu, 2012. "On zero duality gap in nonconvex quadratic programming problems," Journal of Global Optimization, Springer, vol. 52(2), pages 229-242, February.
    18. Jean-Claude Picard, 1976. "Maximal Closure of a Graph and Applications to Combinatorial Problems," Management Science, INFORMS, vol. 22(11), pages 1268-1272, July.
    19. L.D. Iasemidis & P. Pardalos & J.C. Sackellares & D.-S. Shiau, 2001. "Quadratic Binary Programming and Dynamical System Approach to Determine the Predictability of Epileptic Seizures," Journal of Combinatorial Optimization, Springer, vol. 5(1), pages 9-26, March.
    20. Gulati, V. P. & Gupta, S. K. & Mittal, A. K., 1984. "Unconstrained quadratic bivalent programming problem," European Journal of Operational Research, Elsevier, vol. 15(1), pages 121-125, January.
    21. Pierre Hansen & Brigitte Jaumard & Vincent Mathon, 1993. "State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming," INFORMS Journal on Computing, INFORMS, vol. 5(2), pages 97-119, May.
    22. Mark Lewis & Bahram Alidaee & Fred Glover & Gary Kochenberger, 2009. "A note on xQx as a modelling and solution framework for the Linear Ordering Problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 5(2), pages 152-162.
    23. Francisco Barahona & Martin Grötschel & Michael Jünger & Gerhard Reinelt, 1988. "An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design," Operations Research, INFORMS, vol. 36(3), pages 493-513, June.
    24. Alkhamis, Talal M. & Hasan, Merza & Ahmed, Mohamed A., 1998. "Simulated annealing for the unconstrained quadratic pseudo-Boolean function," European Journal of Operational Research, Elsevier, vol. 108(3), pages 641-652, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gili Rosenberg & Mohammad Vazifeh & Brad Woods & Eldad Haber, 2016. "Building an iterative heuristic solver for a quantum annealer," Computational Optimization and Applications, Springer, vol. 65(3), pages 845-869, December.
    2. Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2010. "A hybrid metaheuristic approach to solving the UBQP problem," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1254-1262, December.
    3. Wang, Yang & Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2012. "Path relinking for unconstrained binary quadratic programming," European Journal of Operational Research, Elsevier, vol. 223(3), pages 595-604.
    4. Alidaee, Bahram & Kochenberger, Gary & Lewis, Karen & Lewis, Mark & Wang, Haibo, 2008. "A new approach for modeling and solving set packing problems," European Journal of Operational Research, Elsevier, vol. 186(2), pages 504-512, April.
    5. Xue-Gang Zhou & Xiao-Peng Yang & Bing-Yuan Cao, 2015. "Global optimality conditions for cubic minimization problems with cubic constraints," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(3), pages 243-264, December.
    6. Mauri, Geraldo Regis & Lorena, Luiz Antonio Nogueira, 2012. "A column generation approach for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 69-74.
    7. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.
    8. Wei Chen & Liansheng Zhang, 2010. "Global optimality conditions for quadratic 0-1 optimization problems," Journal of Global Optimization, Springer, vol. 46(2), pages 191-206, February.
    9. V. Jeyakumar & G. Li & S. Srisatkunarajah, 2014. "Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations," Journal of Global Optimization, Springer, vol. 58(1), pages 31-50, January.
    10. Katayama, Kengo & Narihisa, Hiroyuki, 2001. "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 134(1), pages 103-119, October.
    11. Gary Kochenberger & Fred Glover & Bahram Alidaee & Cesar Rego, 2005. "An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem," Annals of Operations Research, Springer, vol. 139(1), pages 229-241, October.
    12. Shenshen Gu & Xinyi Chen, 2020. "The Basic Algorithm for the Constrained Zero-One Quadratic Programming Problem with k -diagonal Matrix and Its Application in the Power System," Mathematics, MDPI, vol. 8(1), pages 1-16, January.
    13. Ricardo N. Liang & Eduardo A. J. Anacleto & Cláudio N. Meneses, 2022. "Data structures for speeding up Tabu Search when solving sparse quadratic unconstrained binary optimization problems," Journal of Heuristics, Springer, vol. 28(4), pages 433-479, August.
    14. Thai Doan Chuong, 2020. "Semidefinite Program Duals for Separable Polynomial Programs Involving Box Constraints," Journal of Optimization Theory and Applications, Springer, vol. 185(1), pages 289-299, April.
    15. Ali Fattahi & Sriram Dasu & Reza Ahmadi, 2019. "Mass Customization and “Forecasting Options’ Penetration Rates Problem”," Operations Research, INFORMS, vol. 67(4), pages 1120-1134, July.
    16. Chunli Liu & Jianjun Gao, 2015. "A polynomial case of convex integer quadratic programming problems with box integer constraints," Journal of Global Optimization, Springer, vol. 62(4), pages 661-674, August.
    17. Domenico Moramarco & Umutcan Salman, 2023. "Equal opportunities in many-to-one matching markets," Working Papers 649, ECINEQ, Society for the Study of Economic Inequality.
    18. X. Zheng & X. Sun & D. Li & Y. Xu, 2012. "On zero duality gap in nonconvex quadratic programming problems," Journal of Global Optimization, Springer, vol. 52(2), pages 229-242, February.
    19. Z. Y. Wu & A. M. Rubinov, 2010. "Global Optimality Conditions for Some Classes of Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 145(1), pages 164-185, April.
    20. Goldengorin, Boris & Ghosh, Diptesh, 2004. "A Multilevel Search Algorithm for the Maximization of Submodular Functions," Research Report 04A20, University of Groningen, Research Institute SOM (Systems, Organisations and Management).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:28:y:2014:i:1:d:10.1007_s10878-014-9734-0. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.