Simultaneously lifting sets of variables in binary Knapsack problems

K-REx Repository

Show simple item record Sharma, Kamana 2007-12-04T20:08:08Z 2007-12-04T20:08:08Z 2007-12-04T20:08:08Z
dc.description.abstract Integer 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.language.iso en_US en
dc.publisher Kansas State University en
dc.subject Simultaneous Lifting en
dc.subject knapsack problem en
dc.subject integer programming en
dc.title Simultaneously lifting sets of variables in binary Knapsack problems en
dc.type Thesis en Master of Science en
dc.description.level Masters en
dc.description.department Department of Industrial & Manufacturing Systems Engineering en
dc.description.advisor Todd W. Easton en
dc.subject.umi Engineering, Industrial (0546) en
dc.subject.umi Operations Research (0796) en 2007 en December en

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


118 Hale Library

Manhattan KS 66506

(785) 532-7444