Approximation techniques for mixed-integer quadratic programs
Abstract/Contents
- Abstract
- This thesis studies the class of NP-hard mixed-integer optimization problems with quadratic objective function and constraints that are not necessarily convex. We propose the Suggest-and-Improve framework, which encapsulates and generalizes a number of known techniques and provides heuristics for computing approximate solutions to quadratically constrained quadratic programs, for which no specialized methods are available. Using numerical examples, we show that the Suggest-and-Improve framework can yield strong upper and lower bounds on the optimal value. We also show a provable bound on the semidefinite relaxation applied to the NP-hard problem of minimizing a convex quadratic function over the integer lattice. Finally, we discuss the family of concave quadratic inequalities that can be added to general mixed-integer quadratic programs. This technique allows the Suggest-and-Improve framework to be applied to any mixed-integer quadratically constrained quadratic problems.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Park, Jaehyun | |
|---|---|---|
| Associated with | Stanford University, Computer Science Department. | |
| Primary advisor | Boyd, Stephen P | |
| Thesis advisor | Boyd, Stephen P | |
| Thesis advisor | Charikar, Moses | |
| Thesis advisor | Valiant, Gregory | |
| Advisor | Charikar, Moses | |
| Advisor | Valiant, Gregory |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Jaehyun Park. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Jaehyun Park
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...