Applying Methods from Combinatorial Optimization in Solving Real World Problems

应用组合优化方法解决现实问题

• 批准号: 36740-2007
• 负责人: Boyd, Sylvia
• 金额: $ 1.46万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=363140
• 关键词: Applying; Methods; Combinatorial; Optimization; Solving

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.

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