Publication Date
2025
Document Type
Dissertation/Thesis
First Advisor
Krislock, Nathan
Degree Name
Ph.D. (Doctor of Philosophy)
Legacy Department
Department of Mathematical Sciences
Abstract
A standard technique for bounding a combinatorial optimization problem is to form a semidefinite relaxation of the problem by "lifting" the problem into a higher dimensional space of symmetric matrices. For some combinatorial problems such as maximum k-cluster, the resulting semidefinite relaxation is not strictly feasible. In the context of the maximum k-cluster problem, we present an equivalent, strictly feasible semidefinite relaxation by way of the dimensionality reduction technique known as facial reduction. We provide a recipe to form this semidefinite relaxation directly, bypassing the lifting and facial reduction steps entirely. We then present our work on generalizing this result, and provide a recipe for constructing a strictly feasible semidefinite relaxation of binary quadratic problems with a single linear constraint with non-zero right-hand side. In addition, we also present numerical results that support the inclusion of facial reduction in the binary quadratic solver BiqCrunch, as well as results supporting the use of facial reduction when solving a semidefinite relaxation of the maximum k-cluster problem.
Recommended Citation
Sugrue, Ian, "Facial Reduction of Semidefinite Relaxations of Binary Quadratic Problems" (2025). Graduate Research Theses & Dissertations. 8091.
https://huskiecommons.lib.niu.edu/allgraduate-thesesdissertations/8091
Extent
134 pages
Language
en
Publisher
Northern Illinois University
Rights Statement
In Copyright
Rights Statement 2
NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.
Media Type
Text
