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