Applying Methods from Combinatorial Optimization in Solving Large-Scale Real World Problems

许多实际重要的优化问题本质上都是组合优化问题。一些例子包括可靠通信网络的最低成本设计、快速印刷电路板生产、遗传进化树的构建以及各种调度和布线问题的优化。不幸的是，这类问题可能属于一种称为“NP-Hard”的类别，这被认为是它们极难解决的有力证据，而且我们极不可能找到保证在所有情况下都实用和有效的解决它们的技术。缺乏有效的方法来解决这类问题是非常重要的，因为存在需要解决的大规模现实世界实例。幸运的是，在实践中，通常获得这些问题的解就足够了，即使不是最优的，至少可以保证在最优(最佳)解的某个令人满意的百分比内，而在许多情况下，最优(最佳)解是更可行的任务。 我们的研究目标是扩大从实用的组合优化模型中产生的这类NP-Hard问题的集合，使其能够得到实用而令人满意的解决。为了实现这一目标，我们将采用以下三种方法： 1)研究为此类问题开发新的和改进的有效方法，以提供 保证在最优解的满意百分比范围内的解。 2)研究如何提高当前方法的成功率，这些方法试图找到准确的 这类问题的最优解。 3)探索组合优化模型和方法在实际应用中的应用途径。 出现在计算机科学的其他领域。

Many practically important optimization problems are combinatorial in nature. Some examples include the minimum cost design of reliable communication networks, fast printed circuit board production, the building of genetic evolutionary trees as well as the optimization of various scheduling and routing problems. Unfortunately, may such problems belong to a class called "NP-hard", which is considered strong evidence that they are extremely difficult to solve, and that it is highly unlikely that we will find techniques for solving them that are guarantee to be practical and efficient in all cases. The lack of efficient methods for such problems is of significant importance as there exist large-scale, real world instances requiring solutions. Fortunately, in practice, it is often sufficient to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal (best) solution, which in many cases is much more viable task. Our research objective is to enlarge the set of such NP-hard problems arising from applied combinatorial optimization models which can be practically and satisfactorily solved. To achieve this goal we will use the following three approaches: 1) Investigate developing new and improved efficient methods for such problems which provide solutions guaranteed to lie within a satisfactory percentage of the optimal solution. 2) Investigate ways to improve the success rate of current methods which attempt to find an exact optimal solution for such problems. 3) Investigate ways of applying combinatorial optimization models and methods to applications arising in other areas of Computer Science.