The theory of simultaneous lifting: constellations in conflict hypergraphs

K-REx Repository

Show simple item record Pahwa, Samir 2009-12-17T20:40:47Z 2009-12-17T20:40:47Z 2009-12-17T20:40:47Z
dc.description.abstract Integer programming (IP) is a powerful technique used by many companies and organizations to determine optimal strategies for making decisions and managing resources to achieve their goals. One class of IP problems is the multiple knapsack (MK) problem. However, MK and other IP problems, are extremely complicated since they are ${\cal NP}$-hard problems. Furthermore, there exist numerous instances that can not be solved. One technique commonly used to reduce the solution time for IP problems is lifting. This method, introduced by Gomory, takes an existing valid inequality and strengthens it. Lifting has the potential to form facet defining inequalities, which are the strongest inequalities to solve an IP problem. As a result, lifting is frequently used in integer programming applications. This research takes a broad approach to simultaneous lifting and provides its theoretical background for. The underlying hypergraphic structure for simultaneous lifting in an MK problem is identified and called a constellation. A constellation contains two hypercliques and multiple hyperstars from various conflict hypergraphs. Theoretical results demonstrate that a constellation induces valid inequalities that could be obtained by simultaneous lifting. Moreover, these constellation inequalities can be facet defining. The primary advancements, constellations and the associated valid inequalities, of this thesis are theoretical in nature. By providing the theory behind simultaneous lifting, researchers should be able to apply this knowledge to develop new algorithms that enable simultaneous lifting to be performed faster and over more complex integer programs. en_US
dc.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Simultaneous Lifting en_US
dc.subject Constellations en_US
dc.subject Conflict Hypergraphs en_US
dc.title The theory of simultaneous lifting: constellations in conflict hypergraphs en_US
dc.type Thesis en_US 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 Operations Research (0796) en_US 2009 en_US December 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