Algorithms for solving linear integer progamming problems

Author

Lisa Catherine Watkins

Date of Award

12-1999

Degree Type

Thesis

Degree Name

Master of Science

Major

Mathematics

Major Professor

Yueh-er Kuo

Abstract

This thesis discusses several methods used to solve linear integer programming problems. Chapters 1-3 give the necessary linear programming background. Chapter 4 introduces integer programming and describes, in general, the two classes of solution methods -enumeration and cutting planes. Chapter 5 details two specific cutting plane methods, one all-integer approach and one fractional approach.Chapter 6 describes the branch-and-bound method, one of the enumeration methods. In Chapter 7 the additive algorithm for 0-1 programming problems is discussed. Chapter 8 describes the branch and-cut method, a combination of the cutting plane and branch-and bound approaches. Chapter 9 presents the plant location problem as an example of the integer programming problem. Examples of each method are included in the thesis.

Recommended Citation

Watkins, Lisa Catherine, "Algorithms for solving linear integer progamming problems. " Master's Thesis, University of Tennessee, 1999.
https://trace.tennessee.edu/utk_gradthes/10042