The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications

Preface
Contents
Contributors
Acronyms
1 Introduction to QUBO
	1.1 Introduction
	1.2 The Ising Model
	1.3 Representations of the Q Matrix
	1.4 Some Equivalent Optimization Problems
		1.4.1 QUBO as a Bilinear Program
		1.4.2 The Maximum Cut Problem and QUBO
		1.4.3 Equivalence with the Stable Set Problem
		1.4.4 QUBO and the Generalized Stable Set Problem
		1.4.5 Quadratic Pseudo-Boolean Optimization
	1.5 Roof Duality
	1.6 Model Building Using QUBO
		1.6.1 Person Detection and Tracking in a Crowded Environment
		1.6.2 Module Flipping in Circuit Layout Design
		1.6.3 Side-Chain Positioning in Protein Design
		1.6.4 QUBO and Machine Scheduling
	1.7 Mixed Integer Programming Formulations
	1.8 Conclusion
	References
2 Applications and Computational Advances for Solving the QUBO Model
	2.1 Introduction
	2.2 Applications of the QUBO Model
		2.2.1 Additional Applications by Category
	2.3 Creating QUBO Models
		2.3.1 Creating QUBO Models: A General Purpose Approach
		2.3.2 Illustrative Computational Experience
	2.4 Summary and Conclusion
	References
3 Complexity and Polynomially Solvable Special Cases of QUBO
	3.1 Introduction and Notations
	3.2 Computational Complexity
	3.3 Polynomially Solvable Matrix Structures
		3.3.1 Linear Restrictions on the Cost Matrices
		3.3.2 Low Rank Cost Matrices
			3.3.2.1 The Special Case c=0
			3.3.2.2  The General Case: cRn
	3.4 Polynomially Solvable Graph Structures
		3.4.1 QUBO and the Maximum Cut Problem
		3.4.2 Stable Sets and Cliques
	3.5 Pseudopolynomial and Subexponential Algorithms
		3.5.1 Low Rank Cost Matrices
		3.5.2 The Half-Product QUBO
		3.5.3 Subexponential Algorithms
	3.6 Conclusions
	References
4 The Boolean Quadric Polytope
	4.1 Introduction
	4.2 Elementary Polyhedral Theory
	4.3 The Boolean Quadric Polytope
	4.4 Some More Valid Inequalities
	4.5 Some Related Polytopes
		4.5.1 The Cut Polytope
		4.5.2 Polytopes Which Exploit Sparsity
	4.6 Some Other Related Convex Sets
		4.6.1 A Non-polyhedral Convex Set
		4.6.2 A Convex Set Related to Max-Cut
		4.6.3 Cones
	4.7 Algorithms
		4.7.1 Cut-and-Branch
		4.7.2 Separation Algorithms
		4.7.3 Branch-and-Cut
	4.8 Concluding Remarks
	References
5 Autarkies and Persistencies for QUBO
	5.1 Introduction
	5.2 Basic Definitions
	5.3 Functional Pesistency
	5.4 Autarkies
	5.5 Polyhedral Persistency
	5.6 Persistencies and Autarkies for Quadratic Functions and Posiforms
	References
6 Mathematical Programming Models and Exact Algorithms
	6.1 Introduction
	6.2 MILP Formulations
		6.2.1 Compact MILP Formulations
	6.3 QUBO and Semidefinite Programming
		6.3.1 The QUBO Formulation and SDP
		6.3.2 The Ising QUBO Formulation and SDP
		6.3.3 Linearly Constrained Quadratic Problems and the Maximum Cut Problem
		6.3.4 The Stable Set Problem
		6.3.5 The Maximum k-Colorable Subgraph Problem
	6.4 Upper Bounds by Decomposition
	6.5 Variable Fixing
	6.6 Algorithms and Solvers
	Appendix: Linear Programming and Duality
	References
7 The Random QUBO
	7.1 Introduction
	7.2 An Upper Bound on the Expected Optimal Value
	7.3 Quadratic Convex Reformulation (QCR)
		7.3.1 QCR Method for Determinsitic QUBO
		7.3.2 QCR Methods for Random QUBO
		7.3.3 Numerical Experiments
			7.3.3.1 Random Instances
			7.3.3.2 Robustness Tests Using Permutations
	7.4 The Sherrington-Kirkpatrick Model
	References
8 Fast Heuristics and Approximation Algorithms
	8.1 Introduction
	8.2 Rounding Algorithms
	8.3 The Normalized Relative Error
		8.3.1 Average Value of Solutions of the Ising QUBO
	8.4 Domination Analysis of Algorithms
	8.5 Relative Performance Ratio and Approximation Algorithms
		8.5.1 ε-Approximation Algorithms for the Ising QUBO
		8.5.2 Computing ε-Optimal Solutions from SDP Relaxation
		8.5.3 Other Special Cases
	8.6 Conclusion
	References
9 Metaheuristic Algorithms
	9.1 Basic Ingredients of Local Search
	9.2 Fast Solving Heuristics
	9.3 Local Search Based Methods
		9.3.1 Simulated Annealing
		9.3.2 Tabu Search
	9.4 Population Based Search Methods
	9.5 Selected Metaheuristic Approaches for QUBO
		9.5.1 Diversification-Driven Tabu Search
		9.5.2 Memetic Search
		9.5.3 Path Relinking
		9.5.4 Automatic Grammar-Based Design of Heuristic Algorithms
		9.5.5 A Systematic Evaluation of Heuristics
	9.6 Computational Results
		9.6.1 Benchmark Instances
		9.6.2 Computational Results on the QUBO Instances
		9.6.3 Computational Results on the MaxCut Instances
	References
10 The Bipartite QUBO
	10.1 Introduction
	10.2 Applications
	10.3 MILP Formulations
		10.3.1 Compact Formulations
	10.4 Polynomially Solvable Special Cases
		10.4.1 Polynomially Solvable Biclique Problems
	10.5 Approximation Algorithms
		10.5.1 Domination Analysis
		10.5.2 Approximation Algorithms for the Ising BQUBO
	10.6 Local Search and Metaheuristics
		10.6.1 Flip Based Neighborhoods
			10.6.1.1 The Flip and Float Neighborhood
		10.6.2 Metaheuristics
	10.7 Exact Algorithms
	10.8 Concluding Remarks
	References
11 QUBO Software
	11.1 Introduction
	11.2 General Purpose Solvers
	11.3 Exact Solvers for QUBO
	11.4 Heuristics for QUBO
	11.5 QUBO Tools
	11.6 Hardware for QUBO
	11.7 Miscellaneous
	11.8 Benchmark Instances
	References
Index