Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / 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.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/9162 |
| Date | January 1900 |
| Creators | Pavelka, Jeffrey William |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0023 seconds