Master of Science
Date of Defense
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.
Brandenburg, John, "A Parallelized Method for Solving Large Scale Integer Linear Optimization Problems using Cut-and-Solve with Applications to cGWAS" (2017). Theses. 295.
Available for download on Sunday, October 21, 2018