Conley, Clark Logan2009-12-172009-12-172009-12-17http://hdl.handle.net/2097/2300Graph 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.en-US© 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).http://rightsstatements.org/vocab/InC/1.0/Node packingCliqueGraphsSimultaneous liftingGraph theoryFacetThesisEngineering, Industrial (0546)Mathematics (0405)Operations Research (0796)