Document Type
Thesis
Degree
Master of Science
Major
Computer Science
Date of Defense
4-20-2017
Graduate Advisor
Sharlee Climer
Committee
Sharlee Climer
Sanjiv Bhatia
Wenjie He
Abstract
The commercial solver CPLEX has been one of the top solvers of mixed-integer and purely integer linear problems for some time. Its method of solving, Branch-and-Cut, has been shown to be highly effective, but has its limits in terms of input sizes which are tractable, and cannot be effectively parallelized beyond a small number. Here we present a different method of solution, Cut-and-Solve, which utilizes the power of CPLEX to effectively parallelize any mixed-integer or integer linear problem. We have utilized Cut-and-Solve in a novel way to offer optimal solution guarantees more quickly. We will show comparisons of Cut-and-Solve to CPLEX and show that it has definite promise as a solver of these types of problems. It offers a less memory intensive solution and one with power equal to the limitations only of the hardware it can be parallelized on. This method does not perform better than CPLEX at the level of parallelization tested here, but with some minor adjustments has the potential to solve previously intractable problems. Importantly, our current implementation shows an effective use as an anytime solver.
Recommended Citation
Brandenburg, John, "A Parallelized Method for Solving Large Scale Integer Linear Optimization Problems using Cut-and-Solve with Applications to cGWAS" (2017). Theses. 295.
https://irl.umsl.edu/thesis/295
Included in
Artificial Intelligence and Robotics Commons, Numerical Analysis and Scientific Computing Commons, Theory and Algorithms Commons