Approved by:

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 o