Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Graph Theory is a widely studied topic. A graph is defined by two important features:
nodes and edges. Nodes can represent people, cities, variables, resources, products, while
the edges represent a relationship between two nodes. Using graphs to solve problems
has played a major role in a diverse set of industries for many years.
Integer Programs (IPs) are mathematical models used to optimize a problem. Often
this involves maximizing the utilization of resources or minimizing waste. IPs are
most notably used when resources must be of integer value, or cannot be split. IPs
have been utilized by many companies for resource distribution, scheduling, and conflict
management.
The node packing or independent set problem is a common combinatorial optimization
problem. The objective is to select the maximum nodes in a graph such that no two
nodes are adjacent. Node packing has been used in a wide variety of problems, which
include routing of vehicles and scheduling machines.
This thesis introduces several new graph structures, cliqued hole, odd bipartite hole,
and odd k-partite hole, and their corresponding valid inequalities for the node packing
polyhedron. These valid inequalities are shown to be new valid inequalities and conditions
are provided for when they are facet defining, which are known to be the strongest
class of valid inequalities. These new valid inequalities can be used by practitioners to
help solve node packing instances and integer programs.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/2300 |
| Date | January 1900 |
| Creators | Conley, Clark Logan |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.003 seconds