A New Decomposition Approach for a Class of NP-hard Graph Problems

Texas A&M Engineering Experiment Station, College Station TX

Investigators

Abstract

The research undertakes a preliminary investigation of a new decomposition approach that offers the potential for solving large-scale instances of an important class of graph problems effectively. This class, comprising such difficult problems as maximum weight independent subset, maximum clique, maximal planar sub-graph, and graph coloring, has significant economic impact in numerous applications, including plant layout, automatic graph drawing, computational geometry and circuit design. The purpose of the research is to demonstrate the possibilities for this technology, focusing on a typical problem from the class with the goal of optimizing large-scale instances within reasonable average-case run times. Research objectives are: (1) theoretical basis for the decomposition, (2) effective implementation techniques, and (3) computational evaluation of efficacy. Graphs in this class may be decomposed into disjoint sub-graphs and a problem of the same type as the original problem may be solved on each sub-graph. The method of approach applies existing algorithms to solve small sub-problems within reasonable average-case times, generating solutions that will be used in both branch-and-price and branch-and-cut methods. A master problem coordinates sub-problem solutions to optimize the original, large-scale problem. Intellectual merit is based on six research questions. Answers will achieve all three objectives and entail both basic research and engineering contributions. Basic research includes extending the Co-PI's recent research on branch decompositions and the facet generation procedure. Engineering contributions include designing effective implementation techniques and computational evaluation. The research will have broad impact. It will advance discovery and understanding through basic research, contributing to the knowledge base. It will seek to recruit students from under-represented groups and promote teaching and training by engaging them in the field of optimization, contributing to the infrastructure for research and education. The plan for dissemination will contribute to training analysts, engineers, and managers. Research results will be incorporated in courses taught by the Co-PIs and by their colleagues at other universities. Benefits to society at large will accrue from laying the foundation for this new approach. Future research can extend this foundation, specializing the decomposition to other problems in this class and generalizing it to other classes of problems.