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

应用组合优化方法解决大规模现实世界问题

基本信息

批准号：
36740-2013
负责人：
Boyd, Sylvia
金额：
$ 1.82万
依托单位：
University of Ottawa
依托单位国家：
加拿大
项目类别：
Discovery Grants Program - Individual
财政年份：
2015
资助国家：
加拿大
起止时间：
2015-01-01 至 2016-12-31
项目状态：
已结题

来源：
https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568774
关键词：
Applying Methods Combinatorial Optimization Solving

项目摘要

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.

实际上，许多实际上重要的优化问题本质上是组合。一些示例包括可靠通信网络的最低成本设计，快速印刷电路板的生产，遗传进化树的建造以及各种调度和路由问题的优化。不幸的是，此类问题可能属于称为“ NP-HARD”的类别，该类别被认为是很难解决的有力证据，而且我们很不可能找到解决方案的技术，这些技术在所有情况下都可以保证实用和有效。由于存在需要解决方案的大规模现实世界实例，因此缺乏有效的方法很重要。幸运的是，实际上，获得这些问题的解决方案通常足够，如果不是最佳的，至少可以保证在最佳（最佳）解决方案的一定令人满意的百分比之内，在许多情况下，这是更可行的任务。我们的研究目的是扩大由应用组合优化模型引起的此类NP硬质问题，这些模型可以在实际和令人满意地解决。为了实现这一目标，我们将使用以下三种方法： 1）研究为提供的这些问题开发新的和改进的有效方法解决方案保证在最佳解决方案的令人满意的百分比之内。 2）研究提高试图找到准确方法的当前方法的成功率的方法解决此类问题的最佳解决方案。 3）研究将组合优化模型和方法应用于应用程序的方法在计算机科学的其他领域产生。