Lifted equality cuts for the multiple knapsack equality problem

K-REx Repository

Show simple item record Talamantes, Alonso 2017-04-21T21:45:37Z 2017-04-21T21:45:37Z 2017-05-01 en_US
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. 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%. en_US
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 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 2017 en_US May en_US

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