Simultaneously lifting sets of variables in binary Knapsack problems

dc.contributor.authorSharma, Kamana
dc.date.accessioned2007-12-04T20:08:08Z
dc.date.available2007-12-04T20:08:08Z
dc.date.graduationmonthDecemberen
dc.date.issued2007-12-04T20:08:08Z
dc.date.published2007en
dc.description.abstractInteger programming (IP) has been and continues to be widely used by industries to minimize cost and effectively manage resources. Faster computers and innovative IP techniques have enabled the solution to many large-scale IPs. However, IPs are NP-hard and many IPs require exponential time to solve. Lifting is one of the most widely used techniques that helps to reduce computational time and is widely applied in today's commercial IP software. Lifting was first introduced by Gomory for bounded integer programs and a theoretical and computationally intractible technique to simultaneously lift sets of variables was introduced by Zemel in 1978. This thesis presents a new algorithm called the Maximal Simultaneous Lifting Algorithm (MSLA), to simultaneously uplift sets of binary integer variables into a cover inequality. These lifted inequalities result in strong inequalities that are facet defining under fairly moderate assumptions. A computational study shows that this algorithm can find numerous strong inequalities for random Knapsack (KP) instances. The pre-processing time observed for these instances is less than 1/50th of a second, which is negligible. These simultaneously lifted inequalities are easy to find and incorporating these cuts to KP instances reduced the solution time by an average of 41%. Therefore, implementing MSLA should be highly beneficial for large real-world problems.en
dc.description.advisorTodd W. Eastonen
dc.description.degreeMaster of Scienceen
dc.description.departmentDepartment of Industrial & Manufacturing Systems Engineeringen
dc.description.levelMastersen
dc.identifier.urihttp://hdl.handle.net/2097/469
dc.language.isoen_USen
dc.publisherKansas State Universityen
dc.subjectSimultaneous Liftingen
dc.subjectknapsack problemen
dc.subjectinteger programmingen
dc.subject.umiEngineering, Industrial (0546)en
dc.subject.umiOperations Research (0796)en
dc.titleSimultaneously lifting sets of variables in binary Knapsack problemsen
dc.typeThesisen

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
KamanaSharma2007.pdf
Size:
379.81 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.69 KB
Format:
Item-specific license agreed upon to submission
Description: