Applying Methods from Combinatorial Optimization in Solving Real World Problems

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

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

实际上，许多实际上重要的问题是本质上的组合。 此类问题的一些示例包括设计可靠的通信网络，快速印刷电路板的生产，调度问题和路由问题。 已知许多这样的问题属于称为“ NP-HARD”的类别，这是这些问题非常难以解决的有力证据，并且不太可能存在有效的技术来找到最佳（最好的）解决方案。 由于存在大规模的实例，需要解决方案的现实世界实例，因此缺乏有效的方法是真正的重要性。 幸运的是，在实践中，获得这些问题的解决方案通常是令人满意的，如果不是最佳的话，至少可以保证在最佳解决方案的一定令人满意的百分比内。