Return to search

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

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / 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.

Identiferoai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/13729
Date January 1900
CreatorsIrvine, Chelsea Nicole
PublisherKansas State University
Source SetsK-State Research Exchange
Languageen_US
Detected LanguageEnglish
TypeThesis

Page generated in 0.0016 seconds