Simultaneously lifting multiple sets in binary knapsack integer programs

K-REx Repository

Show simple item record Kubik, Lauren Ashley 2009-05-18T16:50:41Z 2009-05-18T16:50:41Z 2009-05-18T16:50:41Z
dc.description.abstract Integer programs (IPs) are mathematical models that can provide organizations with the ability to optimally obtain their goals through appropriate utilization and allocation of available resources. Unfortunately, IPs are NP-complete in the strong sense, and many integer programs cannot be solved. Introduced by Gomory, lifting is a technique that takes a valid inequality and strengthens it. Lifting can result in facet defining inequalities, which are the theoretically strongest inequalities; because of this, lifting techniques are commonly used in commercial IP software to reduce the time required to solve an IP. This thesis introduces two new algorithms for exact simultaneous up lifting multiple sets into binary knapsack problems and introduces sequential simultaneous lifting. The Dynamic Programming Multiple Lifting Set Algorithm (DPMLSA) is a pseudopolynomial time algorithm bounded by O(nb) effort that can exactly uplift an arbitrary number of sets. The Three Set Simultaneous Lifting Algorithm (TSSLA) is a polynomial time algorithm bounded by O(n2) and can exact simultaneously up lift three sets. The simultaneously lifted inequalities generated by the DPMLSA and the TSSLA can be facet defining, and neither algorithm requires starting with a minimal cover. A brief computational study shows that the DPMLSA is fast and required an average of only 0.070 seconds. The computational study also shows these sequential simultaneously lifted inequalities are useful, as the solution time decreased by an overall average of 18.4%. Therefore, implementing the DPMLSA should be beneficial for large IPs. en
dc.language.iso en_US en
dc.publisher Kansas State University en
dc.subject Integer Program en
dc.subject Knapsack en
dc.subject Sequential Simultaneous Lifting en
dc.subject Lifting Sets en
dc.title Simultaneously lifting multiple sets in binary knapsack integer programs 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
dc.subject.umi Operations Research (0796) en 2009 en May 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