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