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.

Share

COinS