Mathematical programming models and exact algorithms

Abraham P.  Punnen; Renata Sotirov

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

Mathematical programming models and exact algorithms

Abraham P. Punnen
, Renata Sotirov

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific

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.

Original language	English
Title of host publication	The Quadratic Unconstrained Binary Optimization Problem Theory, Algorithms, and Applications
Editors	A.P. Punnen
Place of Publication	Switzerland
Publisher	Springer
Chapter	6
Pages	139-185
DOIs	https://doi.org/10.1007/978-3-031-04520-2_6
Publication status	Published - 2022

Access to Document

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

Cite this

@inbook{051d44195cc544bba0f6e2b192b989ab,

title = "Mathematical programming models and exact algorithms",

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.",

author = "Punnen, \{Abraham P.\} and Renata Sotirov",

year = "2022",

doi = "10.1007/978-3-031-04520-2\_6",

language = "English",

pages = "139--185",

editor = "A.P. Punnen",

booktitle = "The Quadratic Unconstrained Binary Optimization Problem Theory, Algorithms, and Applications",

publisher = "Springer",

address = "Germany",

}

TY - CHAP

T1 - Mathematical programming models and exact algorithms

AU - Punnen, Abraham P.

AU - Sotirov, Renata

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-031-04520-2_6

DO - 10.1007/978-3-031-04520-2_6

M3 - Chapter

SP - 139

EP - 185

BT - The Quadratic Unconstrained Binary Optimization Problem Theory, Algorithms, and Applications

A2 - Punnen, A.P.

PB - Springer

CY - Switzerland

ER -

Mathematical programming models and exact algorithms

Abstract

Access to Document

Fingerprint

Cite this