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

Date

2012-04-27

Journal Title

Journal ISSN

Volume Title

Publisher

Kansas State University

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.

Description

Keywords

Sun, Suns, Node packing, Graph theory, Polyhedral theory, Facet defining

Graduation Month

May

Degree

Master of Science

Department

Department of Industrial and Manufacturing Systems Engineering

Major Professor

Todd W. Easton

Date

2012

Type

Thesis

Citation