Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / 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.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/476 |
| Date | January 1900 |
| Creators | McAdoo, Michael John |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0018 seconds