Three set inequalities in integer programming

K-REx Repository

Show simple item record McAdoo, Michael John 2007-12-10T15:53:47Z 2007-12-10T15:53:47Z 2007-12-10T15:53:47Z
dc.description.abstract Integer programming is a useful tool for modeling and optimizing real world problems. Unfortunately, the time required to solve integer programs is exponential, so real world problems often cannot be solved. The knapsack problem is a form of integer programming that has only one constraint and can be used to strengthen cutting planes for general integer programs. These facts make finding new classes of facet-defining inequalities for the knapsack problem an extremely important area of research. This thesis introduces three set inequalities (TSI) and an algorithm for finding them. Theoretical results show that these inequalities will be of dimension at least 2, and can be facet defining for the knapsack problem under certain conditions. Another interesting aspect of these inequalities is that TSIs are some of the first facet-defining inequalities for knapsack problems that are not based on covers. Furthermore, the algorithm can be extended to generate multiple inequalities by implementing an enumerative branching tree. A small computational study is provided to demonstrate the effectiveness of three set inequalities. The study compares running times of solving integer programs with and without three set inequalities, and is inconclusive. en
dc.language.iso en_US en
dc.publisher Kansas State University en
dc.subject Knapsack problem en
dc.subject Cutting planes en
dc.title Three set inequalities in integer programming en
dc.type Thesis en Master of Science en
dc.description.level Masters en
dc.description.department Department of Industrial & Manufacturing Systems Engineering en
dc.description.advisor Todd W. Easton en
dc.subject.umi Engineering, Industrial (0546) en 2007 en December en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx

Advanced Search


My Account


Center for the

Advancement of Digital


118 Hale Library

Manhattan KS 66506

(785) 532-7444