Suns: a new class of facet defining structures for the node packing polyhedron

dc.contributor.authorIrvine, Chelsea Nicole
dc.date.accessioned2012-04-27T19:29:28Z
dc.date.available2012-04-27T19:29:28Z
dc.date.graduationmonthMay
dc.date.issued2012-04-27
dc.date.published2012
dc.description.abstractGraph theory is a widely researched topic. A graph contains a set of nodes and a set of edges. The nodes often represent resources such as machines, employees, or plant locations. Each edge represents the relationship between a pair of nodes such as time, distance, or cost. Integer programs are frequently used to solve graphical problems. Unfortunately, IPs are NP-hard unless P = NP, which implies that it requires exponential effort to solve them. Much research has been focused on reducing the amount of time required to solve IPs through the use of valid inequalities or cutting planes. The theoretically strongest cutting planes are facet defining cutting planes. This research focuses on the node packing problem or independent set problem, which is a combinatorial optimization problem. The node packing problem involves coloring the maximum number of nodes such that no two nodes are adjacent. Node packings have been applied to airline traffic and radio frequencies. This thesis introduces a new class of graphical structures called suns. Suns produce previously undiscovered valid inequalities for the node packing polyhedron. Conditions are provided for when these valid inequalities are proven to be facet defining. Sun valid inequalities have the potential to more quickly solve node packing problems and could even be extended to general integer programs through conflict graphs.
dc.description.advisorTodd W. Easton
dc.description.degreeMaster of Science
dc.description.departmentDepartment of Industrial and Manufacturing Systems Engineering
dc.description.levelMasters
dc.identifier.urihttp://hdl.handle.net/2097/13729
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.subjectSun
dc.subjectSuns
dc.subjectNode packing
dc.subjectGraph theory
dc.subjectPolyhedral theory
dc.subjectFacet defining
dc.subject.umiIndustrial Engineering (0546)
dc.subject.umiTheoretical Mathematics (0642)
dc.titleSuns: a new class of facet defining structures for the node packing polyhedron
dc.typeThesis

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ChelseaIrvine2012.PDF
Size:
644.99 KB
Format:
Adobe Portable Document Format

License bundle

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