Applying Methods from Combinatorial Optimization in Solving Real World Problems

许多具有实际意义的问题本质上都是组合问题。这些问题的一些例子包括可靠通信网络的设计、快速印刷电路板的生产、调度问题和布线问题。许多这样的问题已知属于一类被称为NP-Hard的问题，这有力地证明了这些问题是极难解决的，而且不太可能存在找到最优(即最佳)解决方案的有效技术。对于这样的问题，缺乏有效的方法是真正重要的，因为存在需要解决的大规模的现实世界实例。幸运的是，在实践中，得到这些问题的解往往是令人满意的，即使不是最优的，至少可以保证在最优解的某个令人满意的百分比内。我们的研究目标是扩大这样的问题的集合，这些问题可以实际地和令人满意地解决。为了实现这一目标，我们将使用以下三种方法：1)利用问题的密切相关的松弛来研究开发新的，一种有效的方法，提供的解决方案保证在最优解的满意百分比内。2)开发问题的基本组合结构，为特定问题的改进隐式枚举方案提供必要的工具。3)研究组合优化模型的构建和应用，应用于计算机科学的其他领域。

Many practically important problems are combinatorial in nature.  Some examples of such problems include the design of reliable communication networks, fast printed circuit board production, scheduling problems and routing problems.  Many such problems are known to belong to a class called "NP-hard", which is strong evidence that these problems are extremely difficult to solve, and that it is unlikely that efficient techniques for finding the optimal (i.e. the best) solution exist.  The lack of efficient methods for such problems is of real importance as there exist large scale, real world instances requiring solutions.  Fortunately, in practice, it is often satisfactory to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal solution.Our research objective is to enlarge the set of such problems which can be practically and satisfactorily solved.  To achieve this objective we will use the following three approaches:1)  Investigate using closely-related relaxations of a problem to develop new, efficient methods which provide solutions which are guaranteed to lie within a satisfactory percentage of the optimal solution.2)  Exploit the underlying combintorial structure of a problem to provide the necessary tools for improved problem-specific implicit enumeration schemes for certain problems of interest.3)  Investigate constructing and applying combinatorial optimization models for applications arising in other areas of computer science.