# Lifted equality cuts for the multiple knapsack equality problem

## K-REx Repository

 dc.contributor.author Talamantes, Alonso dc.date.accessioned 2017-04-21T21:45:37Z dc.date.available 2017-04-21T21:45:37Z dc.date.issued 2017-05-01 en_US dc.identifier.uri http://hdl.handle.net/2097/35516 dc.description.abstract Integer programming is an important discipline in operation research that positively impacts society. Unfortunately, no algorithm currently exists to solve IP's in polynomial time. Researchers are constantly developing new techniques, such as cutting planes, to help solve IPs faster. For example, DeLissa discovered the existence of equality cuts limited to zero and one coefficients for the multiple knapsack equality problem (MKEP). An equality cut is an improper cut because every feasible point satisfies the equality. However, such a cut always reduces the dimension of the linear relaxation space by at least one. en_US This thesis introduces lifted equality cuts, which can have coefficients greater than or equal to two. Two main theorems provide the conditions for the existence of lifted equalities. These theorems provide the foundation for The Algorithm of Lifted Equality Cuts (ALEC), which finds lifted equality cuts in quadratic time. The computational study verifies the benefit of lifted equality cuts in random MKEP instances. ALEC generated millions of lifted equality cuts and reduced the solution time by an average of 15%. To the best of the author's knowledge, ALEC is the first algorithm that has found over 30.7 million cuts on a single problem, while reducing the solving time by 18%. dc.language.iso en_US en_US dc.publisher Kansas State University en dc.subject Integer programming en_US dc.subject Polyhedral theory en_US dc.subject Lifting en_US dc.subject Equality cuts en_US dc.subject Cutting planes en_US dc.subject Knapsack problem en_US dc.title Lifted equality cuts for the multiple knapsack equality problem en_US dc.type Thesis en_US dc.description.degree 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 W. Easton en_US dc.date.published 2017 en_US dc.date.graduationmonth May en_US
﻿

Center for the