Lifted equality cuts for the multiple knapsack equality problem

dc.contributor.authorTalamantes, Alonso
dc.date.accessioned2017-04-21T21:45:37Z
dc.date.available2017-04-21T21:45:37Z
dc.date.graduationmonthMay
dc.date.issued2017-05-01
dc.description.abstractInteger 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%.
dc.description.advisorTodd W. Easton
dc.description.degreeMaster of Science
dc.description.departmentDepartment of Industrial and Manufacturing Systems Engineering
dc.description.levelMasters
dc.identifier.urihttp://hdl.handle.net/2097/35516
dc.language.isoen_US
dc.publisherKansas State University
dc.rights© the author. This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectInteger programming
dc.subjectPolyhedral theory
dc.subjectLifting
dc.subjectEquality cuts
dc.subjectCutting planes
dc.subjectKnapsack problem
dc.titleLifted equality cuts for the multiple knapsack equality problem
dc.typeThesis

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
AlonsoTalamantes2017.pdf
Size:
308.84 KB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.62 KB
Format:
Item-specific license agreed upon to submission
Description: