Abstract

Integer Linear Programming has been a growing area of study since the development of modern economies. This project explores the Branch-and-Cut algorithm, one of the methods used to solve large Integer Linear Programming problems. The Simplex method and the Dual Simplex method, the basic computational machines in the Branch-and-Cut algorithm, are discussed. The Branch-and-Bound algorithm and the Cutting Plane algorithm that form the Branch-and-Cut algorithm are also explored. In addition, Gomory's Finiteness proof for the Cutting Plane algorithm is outlined in this thesis. Parallel Computing using MATLAB is investigated. Shared memory parallel computing, distributed memory parallel computing, and computer classifications are some of the main concepts of parallel computing that are explored. A parallel Branch-and-Bound algorithm is implemented in MATLAB. The performance of a parallel Branch-and-Bound algorithm is compared to that of a sequential Branch-and-Bound algorithm and the results are recorded.

Advisor

Byrnes, Denise

Second Advisor

Ramsay, John

Department

Mathematics; Computer Science

Disciplines

Applied Mathematics

Publication Date

2011

Degree Granted

Bachelor of Arts

Document Type

Senior Independent Study Thesis

Share

COinS
 

© Copyright 2011 Itai Njanji