Suns: a new class of facet defining structures for the node packing polyhedron
dc.contributor.author | Irvine, Chelsea Nicole | |
dc.date.accessioned | 2012-04-27T19:29:28Z | |
dc.date.available | 2012-04-27T19:29:28Z | |
dc.date.graduationmonth | May | |
dc.date.issued | 2012-04-27 | |
dc.date.published | 2012 | |
dc.description.abstract | Graph 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.advisor | Todd W. Easton | |
dc.description.degree | Master of Science | |
dc.description.department | Department of Industrial and Manufacturing Systems Engineering | |
dc.description.level | Masters | |
dc.identifier.uri | http://hdl.handle.net/2097/13729 | |
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 | Sun | |
dc.subject | Suns | |
dc.subject | Node packing | |
dc.subject | Graph theory | |
dc.subject | Polyhedral theory | |
dc.subject | Facet defining | |
dc.subject.umi | Industrial Engineering (0546) | |
dc.subject.umi | Theoretical Mathematics (0642) | |
dc.title | Suns: a new class of facet defining structures for the node packing polyhedron | |
dc.type | Thesis |