Sequential and simultaneous lifting in the node packing polyhedron
dc.contributor.author | Pavelka, Jeffrey William | |
dc.date.accessioned | 2011-05-18T13:54:56Z | |
dc.date.available | 2011-05-18T13:54:56Z | |
dc.date.graduationmonth | August | |
dc.date.issued | 2011-05-18 | |
dc.date.published | 2011 | |
dc.description.abstract | Integer 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.advisor | Todd W. Easton | |
dc.description.degree | Master of Science | |
dc.description.department | Department of Industrial & Manufacturing Systems Engineering | |
dc.description.level | Masters | |
dc.identifier.uri | http://hdl.handle.net/2097/9162 | |
dc.language.iso | en_US | |
dc.publisher | Kansas 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.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Node packing | |
dc.subject | Lifting | |
dc.subject | Sequential | |
dc.subject | Simultaneous | |
dc.subject | Polyhedral theory | |
dc.subject.umi | Industrial Engineering (0546) | |
dc.subject.umi | Operations Research (0796) | |
dc.title | Sequential and simultaneous lifting in the node packing polyhedron | |
dc.type | Thesis |