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.


Byrnes, Denise

Second Advisor

Ramsay, John


Mathematics; Computer Science


Applied Mathematics


linear programming, integer linear programming, cutting plane algorithm, branch-and-bound algorithm, branch-and-cut algorithm, parallel computing

Publication Date


Degree Granted

Bachelor of Arts

Document Type

Senior Independent Study Thesis



© Copyright 2011 Itai Njanji