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
Recommended Citation
Njanji, Itai, "Exploring the Branch-And-Cut Algorithm" (2011). Senior Independent Study Theses. Paper 922.
https://openworks.wooster.edu/independentstudy/922
Disciplines
Applied Mathematics
Keywords
linear programming, integer linear programming, cutting plane algorithm, branch-and-bound algorithm, branch-and-cut algorithm, parallel computing
Publication Date
2011
Degree Granted
Bachelor of Arts
Document Type
Senior Independent Study Thesis
© Copyright 2011 Itai Njanji