Three set inequalities in integer programming

K-REx Repository

Show simple item record

dc.contributor.author McAdoo, Michael John
dc.date.accessioned 2007-12-10T15:53:47Z
dc.date.available 2007-12-10T15:53:47Z
dc.date.issued 2007-12-10T15:53:47Z
dc.identifier.uri http://hdl.handle.net/2097/476
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
dc.description.degree 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
dc.date.published 2007 en
dc.date.graduationmonth December en


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx


Advanced Search

Browse

My Account

Statistics








Center for the

Advancement of Digital

Scholarship

118 Hale Library

Manhattan KS 66506


(785) 532-7444

cads@k-state.edu