Abstract

In this paper, we review linear programming and we extend these notions to develop the techniques of integer programming. A linear programming problem is a problem in which a function is maximized or minimized subject to constraints that limit possible solutions. The function that is optimized is a linear function, as are the constraints. An integer programming problem is also a Linear Programming problem, with the added constraint that the solution value for one or more of the variables is required to be an integer. We will use a Linear Programming example to define the key terms that create a Linear Programming problem. Decision variables and optimal solutions are defined through the example, and a feasible region is created to represent the set of all possible solutions that satisfy the constraints of the problem. This example is used to help illustrate the Fundamental Theorem of Linear Programming, a result that states that an optimal solution can always be found at a vertex of the feasible region. This crucial statement is needed for the further discussion of Integer Programming, because the key method to solving Integer Programming problems begins by knowing the optimal solution to the linear programming relaxation. Once the solution is found, we can use new techniques that help to ensure that the final solution will exclude non-integer values. This method, the Branch-and-Bound method, finds the optimal integer solution by partitioning the feasible region at integer values above and below the optimal solution of the relaxation of the linear programming problem. Since an integer programming problem adds the constraint that one or more of the variables can only assume integer values, the relaxation solves the problem as if this restriction were not there. Once we have an optimal value for a variable, we then try to force that variable to assume an integer value. We proceed with a partitioning technique until an integer solution is found. The paper outlines the key concepts of the Branch-and-Bound method for solving integer programming problems. The system can get complex, but an integer solution can be found for any problem. The example used to define the linear programming definitions is continued, with the Branch-and-Bound method applied to show the strategy for finding the integer optimal solution for the problem. Although other methods exist for solving Integer Programming problems, we focus here on the Branch and Bound method. A real world application of Integer Programming is provided, and its objective function and constraints are discussed in detail. This application comes from the Chilean soccer league, where the schedule of matches played each season needed to be optimized to garner more fan interest.

Advisor

Pierce, Pam

Second Advisor

Ramsay, John

Department

Mathematics

Disciplines

Operational Research

Keywords

integer programming, branch and bound

Publication Date

2017

Degree Granted

Bachelor of Arts

Document Type

Senior Independent Study Thesis

Download

Available for download on Sunday, April 01, 2125

Share

COinS
 

© Copyright 2017 Matthew John Kelly