Back to results

Michigan Technological University

Parallel algorithm for solving integer linear programs

Abstract

dc:description.abstract

Linear programs, or LPs, are often used in optimization problems, such as improving manufacturing efficiency of maximizing the yield from limited resources. The most common method for solving LPs is the Simplex Method, which will yield a solution, if one exists, but over the real numbers. From a purely numerical standpoint, it will be an optimal solution, but quite often we desire an optimal integer solution. A linear program in which the variables are also constrained to be integers is called an integer linear program or ILP. It is the focus of this report to present a parallel algorithm for solving ILPs. We discuss a serial algorithm using a breadth-first branch-and-bound search to check the feasible solution space, and then extend it into a parallel algorithm using a client-server model. In the parallel mode, the search may not be truly breadth-first, depending on the solution time for each node in the solution tree. Our search takes advantage of pruning, often resulting in super-linear improvements in solution time. Finally, we present results from sample ILPs, describe a few modifications to enhance the algorithm and improve solution time, and offer suggestions for future work.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Mathematical Sciences (MS)
Level thesis:degree_level
Master's report
Discipline thesis:degree_discipline
Department of Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Torrey, David O., Jr.
Contributors dc:contributor
  • Donald L. Kreher

Subjects

dc:subject × 2

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Michigan Technological University
Base URL
digitalcommons.mtu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Torrey, David O., Jr.. Parallel algorithm for solving integer linear programs. Master's report thesis, https://doi.org/10.37099/mtu.dc.etds/549