# The theory of simultaneous lifting: constellations in conflict hypergraphs

## K-REx Repository

 dc.contributor.author Pahwa, Samir dc.date.accessioned 2009-12-17T20:40:47Z dc.date.available 2009-12-17T20:40:47Z dc.date.issued 2009-12-17T20:40:47Z dc.identifier.uri http://hdl.handle.net/2097/2317 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. en_US 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. 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 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 Operations Research (0796) en_US dc.date.published 2009 en_US dc.date.graduationmonth December en_US
﻿

Center for the