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

K-REx Repository

Show simple item record Irvine, Chelsea Nicole 2012-04-27T19:29:28Z 2012-04-27T19:29:28Z 2012-04-27
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. en_US
dc.language.iso en_US en_US
dc.publisher Kansas State University en
dc.subject Sun en_US
dc.subject Suns en_US
dc.subject Node packing en_US
dc.subject Graph theory en_US
dc.subject Polyhedral theory en_US
dc.subject Facet defining en_US
dc.title Suns: a new class of facet defining structures for the node packing polyhedron en_US
dc.type Thesis en_US Master of Science en_US
dc.description.level Masters en_US
dc.description.department Department of Industrial and Manufacturing Systems Engineering en_US
dc.description.advisor Todd Easton en_US
dc.subject.umi Industrial Engineering (0546) en_US
dc.subject.umi Theoretical Mathematics (0642) en_US 2012 en_US May en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx

Advanced Search


My Account


Center for the

Advancement of Digital