Synchronized simultaneous approximate lifting for the multiple knapsack polytope

K-REx Repository

Show simple item record Morrison, Thomas Braden 2012-04-03T14:06:26Z 2012-04-03T14:06:26Z 2012-04-03
dc.description.abstract Integer programs (IPs) are mathematical models that can provide an optimal solution to a variety of different problems. They have the ability to maximize profitability and decrease wasteful spending, but IPs are NP-complete resulting in many IPs that cannot be solved in reasonable periods of time. Cutting planes or valid inequalities have been used to decrease the time required to solve IPs. These valid inequalities are commonly created using a procedure called lifting. Lifting is a technique that strengthens existing valid inequalities without cutting off feasible solutions. Lifting inequalities can result in facet defining inequalities, the theoretically strongest valid inequalities. Because of these properties, lifting procedures are used in software to reduce the time required to solve an IP. This thesis introduces a new algorithm for synchronized simultaneous approximate lifting for multiple knapsack problems. Synchronized Simultaneous Approximate Lifting (SSAL) requires O(|E1|SLP_|E1|+|E2|,m + |E1|2) effort, where |E1| and |E2| are the sizes of sets used in the algorithm and SLP is the time to solve a linear program. It approximately uplifts two sets simultaneously to creates multiple inequalities of a particular form. These new valid inequalities generated by SSAL can be facet defining. A small computational study shows that SSAL is quick to execute, requiring fractions of a second. Additionally, applying SSAL inequalities to large knapsack problem enabled commercial software to solve faster and also eliminate off the initial linear relaxation point. en_US
dc.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Lifting en_US
dc.subject Polyhedral theory en_US
dc.subject Approximate en_US
dc.subject Sychronized en_US
dc.subject Simultaneous en_US
dc.subject Knapsack en_US
dc.title Synchronized simultaneous approximate lifting for the multiple knapsack polytope en_US
dc.type Thesis en_US Master of Science en_US
dc.description.level Masters en_US
dc.description.department Department of Industrial and Manufacturing Systems Engineering en_US
dc.description.advisor Todd Easton en_US
dc.subject.umi Operations Research (0796) en_US 2012 en_US May en_US

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