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.
Mathematics; Computer Science
Njanji, Itai, "Exploring the Branch-And-Cut Algorithm" (2011). Senior Independent Study Theses. Paper 922.
linear programming, integer linear programming, cutting plane algorithm, branch-and-bound algorithm, branch-and-cut algorithm, parallel computing
Bachelor of Arts
Senior Independent Study Thesis
© Copyright 2011 Itai Njanji