Synchronized simultaneous lifting in binary knapsack polyhedra

K-REx Repository

Show simple item record

dc.contributor.author Bolton, Jennifer Elaine
dc.date.accessioned 2009-12-17T14:42:41Z
dc.date.available 2009-12-17T14:42:41Z
dc.date.issued 2009-12-17T14:42:41Z
dc.identifier.uri http://hdl.handle.net/2097/2304
dc.description.abstract Integer programs (IP) are used in companies and organizations across the world to reach financial and time-related goals most often through optimal resource allocation and scheduling. Unfortunately, integer programs are computationally difficult to solve and in some cases the optimal solutions are unknown even with today’s advanced computing machines. Lifting is a technique that is often used to decrease the time required to solve an IP to optimality. Lifting begins with a valid inequality and strengthens it by changing the coefficients of variables in the inequality. Often times, this technique can result in facet defining inequalities, which are the theoretically strongest inequalities. This thesis introduces a new type of lifting called synchronized simultaneous lifting (SSL). SSL allows for multiple sets of simultaneously lifted variables to be simultaneously lifted which generates a new class of inequalities that previously would have required an oracle to be found. Additionally, this thesis describes an algorithm to perform synchronized simultaneous lifting for a binary knapsack inequality called the Synchronized Simultaneous Lifting Algorithm (SSLA). SSLA is a quadratic time algorithm that will exactly simultaneously lift two sets of simultaneously lifted variables. Short computational studies show SSLA can sometimes solve IPs to optimality that CPLEX, an advanced integer programming solver, alone cannot solve. Specifically, the SSL cuts allowed a 76 percent improvement over CPLEX alone. en_US
dc.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Lifting en_US
dc.subject Integer programming en_US
dc.subject Operations research en_US
dc.subject Facet defining inequality en_US
dc.subject Simultaneous lifting en_US
dc.subject Industrial engineering en_US
dc.title Synchronized simultaneous lifting in binary knapsack polyhedra 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 & Manufacturing Systems Engineering en_US
dc.description.advisor Todd W. Easton en_US
dc.subject.umi Engineering, Industrial (0546) en_US
dc.subject.umi Mathematics (0405) en_US
dc.subject.umi Operations Research (0796) en_US
dc.date.published 2009 en_US
dc.date.graduationmonth December en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx


Advanced Search

Browse

My Account








Center for the

Advancement of Digital

Scholarship

118 Hale Library

Manhattan KS 66506


(785) 532-7444

cads@k-state.edu