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

该研究对一种新的分解方法进行了初步调查，该方法为有效解决一类重要图问题的大规模实例提供了潜力。这门课程包括最大权无关子集、最大团、最大平面子图和图形着色等难题，在许多应用中具有重要的经济影响，包括工厂布局、自动图形绘制、计算几何和电路设计。本研究的目的是演示这种技术的可能性，重点关注类中的一个典型问题，目标是在合理的平均情况运行时间内优化大规模实例。研究目标为：(1)分解的理论基础；(2)有效的实施技术；(3)效能的计算评价。这类图可以分解成不相交的子图，每个子图上可以解一个与原问题相同类型的问题。该方法应用现有算法在合理的平均情况时间内解决小的子问题，生成将在分支-价格和分支-切割方法中使用的解。一个主问题协调子问题的解决方案来优化原来的大规模问题。智力价值基于六个研究问题。答案将实现所有三个目标，并需要基础研究和工程贡献。基础研究包括扩展Co-PI最近在分支分解和facet生成过程方面的研究。工程贡献包括设计有效的实现技术和计算评估。这项研究将产生广泛的影响。它将通过基础研究促进发现和理解，为知识库做出贡献。它将设法从代表性不足的群体中招收学生，并促进教学和培训，使他们参与最优化领域，为研究和教育的基础设施作出贡献。传播计划将有助于培训分析人员、工程师和管理人员。研究成果将被纳入合作项目负责人及其在其他大学的同事所教授的课程中。为这种新办法奠定基础将使整个社会受益。未来的研究可以扩展这一基础，将分解专门化到该类别的问题上，并推广到其他类的问题上。

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.