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