Mathematical Programming Models and Exact Algorithms

Abraham P. Punnen () and Renata Sotirov ()
Additional contact information
Abraham P. Punnen: Simon Fraser University
Renata Sotirov: Tilburg School of Economics and Management, Tilburg University

Chapter Chapter 6 in The Quadratic Unconstrained Binary Optimization Problem, 2022, pp 139-185 from Springer

Abstract: Abstract This chapter focusses on exact solution approaches for QUBO. We first discuss various mixed integer linear programming formulations, compare their relative strength in terms of LP relaxations, and resulting upper bounding strategies. Then, new developments based on semidefinite programming approaches are discussed in detail. The mathematical programming formulations discussed here can be used to solve small size problems and the resulting tight upper bounds on the optimal objective function values can be used in developing specialized enumerative algorithms. Capabilities of some promising enumerative algorithms and solvers are also briefly reviewed.

Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-3-031-04520-2_6

Ordering information: This item can be ordered from
http://www.springer.com/9783031045202

DOI: 10.1007/978-3-031-04520-2_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().