Masters Theses

Date of Award

12-2003

Degree Type

Thesis

Degree Name

Master of Science

Major

Mathematics

Major Professor

Yueh-er Kuo

Abstract

The purpose of this thesis is to provide analysis of the modem development of the methods for solution to the integer linear programming problem. The thesis simultaneously discusses some main approaches that lead to the development of the algorithms for the solution to the integer linear programming problem. Chapter 1 introduces the Generalized Linear Programming Problem alongside with the properties of a solution to the Linear Programming Problem. The simplex procedure presented to solve the Linear Programming Problem by adding slack variables along with the artificial-basis technique. Chapter 2 refers to the primal-dual simplex procedure. The dual simplex algorithm reflects the dual simplex procedure. Chapter 3 discusses the mixed and alternative formulations of the integer programming problem. Chapter 4 considers the optimality conditions with the imposed relaxations to solve the Linear Programming Relaxation Problem. The methods of the Integer Programming are introduced for the Linear Programming Relaxation. Chapter 5 discusses the concepts of the Branch-and Bound method followed by the direct application of the Branch-and-Bound method. Chapter 6 introduces the fundamental concepts of the cutting method. The main concept of the valid inequalities presented for the Linear Programming Problem as well as for the Integer Programming Problem. Gomory's Fractional cutting plane Algorithm represents the desired step to obtain the solution for the Integer Programming Problem. Furthermore, the mixed integer cuts generalizes the concepts to provide the corresponding solution for the Integer Programming Problem. Chapter 7 describes the Gomory method for the pure Integer Program followed by the Gomory method for the mixed Integer Program. In the Appendix the computer program LINDO is used. Throughout the whole thesis this computer program is applied to emphasize the very helpful tool in Linear Programming. All above mentioned chapters include the variety of examples corresponding to the Linear Programming Problem and the Integer Program.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS