Sequential and simultaneous lifting in the node packing polyhedron

dc.contributor.authorPavelka, Jeffrey William
dc.date.accessioned2011-05-18T13:54:56Z
dc.date.available2011-05-18T13:54:56Z
dc.date.graduationmonthAugust
dc.date.issued2011-05-18
dc.date.published2011
dc.description.abstractInteger programs (IPs) are a commonly researched class of decision problems. These problems are used in various applications to help companies, governments, or individuals make better decisions by determining optimal resource allocations. While IPs are practical tools, they require an exponential amount of effort to solve, unless P = NP. This fact has led to much research focused on reducing the time required to solve IPs. Cutting planes are a commonly used tool for reducing IP solving time. Lifting, a process of changing the coefficients in an inequality, is often employed to strengthen cutting planes. When lifting, the goal is often to create a facet defining inequality, which is theoretically the strongest cutting plane. This thesis introduces two new lifting procedures for the Node Packing problem. The Node Packing problem seeks to select the maximum number of nodes in a graph such that no two nodes are adjacent. The first lifting method, the Simultaneous Lifting Expansion, takes two inequalities and combines them to make a stronger cut. It works for any two general classes of inequalities, as long as the requisite graph structures are met. The second method, the Cliques On Odd-holes Lifting (COOL) procedure, lifts from an odd-hole inequality to a facet defining inequality. COOL makes use of the Odd Gap Lifting procedure, an efficient method for finding lifting coefficients on odd holes. A computational study shows COOL to be effective in creating cuts in graphs with low edge densities.
dc.description.advisorTodd W. Easton
dc.description.degreeMaster of Science
dc.description.departmentDepartment of Industrial & Manufacturing Systems Engineering
dc.description.levelMasters
dc.identifier.urihttp://hdl.handle.net/2097/9162
dc.language.isoen_US
dc.publisherKansas State University
dc.rights© the author. This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectNode packing
dc.subjectLifting
dc.subjectSequential
dc.subjectSimultaneous
dc.subjectPolyhedral theory
dc.subject.umiIndustrial Engineering (0546)
dc.subject.umiOperations Research (0796)
dc.titleSequential and simultaneous lifting in the node packing polyhedron
dc.typeThesis

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
JeffreyPavelka2011.pdf
Size:
1.66 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.61 KB
Format:
Item-specific license agreed upon to submission
Description: