On the benefits of a new continuous reformulation for QUBO problems

Petra Maria Bartmeyer () and Christiano Lyra ()
Additional contact information
Petra Maria Bartmeyer: School of Electrical and Computer Engineering, University of Campinas (UNICAMP)
Christiano Lyra: School of Electrical and Computer Engineering, University of Campinas (UNICAMP)

Annals of Operations Research, 2025, vol. 351, issue 1, No 25, 653-665

Abstract: Abstract The quadratic unconstrained binary optimization (QUBO) emerges as an alternative to modeling and solving a wide range of challenging practical applications. This paper proposes reformulating QUBO as a continuous quadratic optimization problem considering theoretical results concerning constraint penalization and diagonal regularization on the objective function. Our findings show that it is possible to address convexity by addressing the problem with the proposed continuous reformulation. The problem is explored with a series of computational experiments using reference instances for the QUBO problem, where up-to-date solutions are provided for benchmark instances. Complementary studies on custom instances show the benefits of using the proposed reformulations for cases with defined negative matrices.

Keywords: Quadratic unconstrained binary optimization; Combinatorial optimization; Continuous reformulations (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-05887-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:351:y:2025:i:1:d:10.1007_s10479-024-05887-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-05887-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().