Solving combinatorial problems by grounding from specifications

通过规范接地解决组合问题

• 批准号: 238987-2010
• 负责人: Mitchell, David
• 金额: $ 1.46万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=547158
• 关键词: Solving; combinatorial; problems; grounding; specifications

Challenging combinatorial search and optimization problems are ubiquitous and diverse. A few examples include finding exam timetables, scheduling machines, constructing phylogenetic trees, configuring complex systems, and finding bugs in computer systems. Most of these problems belong to a class of problems (known as the NP-complete problems) for which no known algorithms exist which are guaranteed to be efficient, and moreover, instances that arise in practice often cannot be solved by current methods in reasonable time. They thus present major scientific and practical challenges. The proposed research aims to develop new methods for handling such problems, in particular addressing two issues with the current state-of-the-art in combinatorial problem solving methods. First, while current algorithms and computers are able to easily produce solutions for many problems that workers in many areas face, the technology to do so is not accessible to - or even known to - many of these workers. A primary goal is to develop methods that are much more accessible, in particular by providing modelling languages and software tools which allow complex underlying computational resources to be used by workers who are not specialists in combinatorial problem solving. Second, there remain a number of areas where the best existing combinatorial solving methods do not work effectively or robustly, in spite of the fact that the mainstream technologies are highly developed and based on decades of high quality science. Another goal is to further develop a newer algorithmic approach for solving such problems, and for exploiting computer processors with many cores - which will soon be in standard desktop computers - in the service of solving these problems. In our approach, both modelling languages and computational solving methods are based on an underlying formalization in mathematical logic, which provides a number of benefits in both theoretical and practical work.

具有挑战性的组合搜索和优化问题无处不在和多样化。一些示例包括查找考试时间表，调度机，构造系统发育树，配置复杂系统以及在计算机系统中查找错误。 这些问题中的大多数属于一类问题（称为NP完整问题），而这些问题不存在已知的算法，这些算法可以保证是有效的，而且实际上在实践中出现的实例通常无法在合理时间内通过当前方法来解决。因此，他们提出了重大的科学和实践挑战。 拟议的研究旨在开发解决此类问题的新方法，特别是解决了组合问题解决方法中最新的两个问题。 首先，虽然当前的算法和计算机能够轻松地为许多领域的工人面临的许多问题提供解决方案，但这样做的技术无法访问许多工人。 一个主要目标是开发更容易访问的方法，尤其是通过提供建模语言和软件工具，这些方法允许不属于组合问题解决方案的专家的工人使用复杂的基础计算资源。 其次，尽管主流技术是高度发展，并且基于数十年的高质量科学，但仍有许多领域，其中最好的现有组合解决方法无法有效或坚固。 另一个目标是进一步开发一种解决此类问题的较新算法方法，并用许多核心（很快将在标准台式计算机中）利用计算机处理器来解决这些问题。在我们的方法中，建模语言和计算求解方法均基于数学逻辑中的基本形式化，该形式在理论和实际工作中都提供了许多好处。