Publication Date
2025
Document Type
Dissertation/Thesis
First Advisor
Krislock, Nathan
Degree Name
M.S. (Master of Science)
Legacy Department
Department of Mathematical Sciences
Abstract
BiqAlps is an extension of the BiqCrunch project that leverages its bounding procedures within a computer cluster environment. The primary goal of this work was to investigate whether distributing the branch-and-bound tree search across multiple CPUs could improve solve times. While some problem instances demonstrated speedups of up to fivefold, others showed no measurable improvement, revealing that parallelization benefits are problem-dependent.
Beyond parallelization, BiqAlps introduces enhanced heuristics for generating high-quality initial solutions and refining existing ones. Additionally, the framework explores the impact of propagating triangle inequality cuts to child nodes during search, with the aim of accelerating bounding processes and improving solution confidence. These algorithmic enhancements broaden the applicability of BiqAlps, especially in problem settings where exact solutions are computationally prohibitive.
Recommended Citation
Haas, James, "Methods for Finding High Quality and Optimal Solutions of Binary Quadratic Optimization Problems" (2025). Graduate Research Theses & Dissertations. 8157.
https://huskiecommons.lib.niu.edu/allgraduate-thesesdissertations/8157
Extent
45 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
