Optimization with Decision Diagrams: Theory and Applications

使用决策图进行优化：理论与应用

• 批准号: RGPIN-2015-04152
• 负责人: Cire, Andre
• 金额: $ 1.75万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612802
• 关键词: Optimization; Decision; Diagrams; Theory; Applications

With both ubiquitous data and use of technology, data-analysis methods have become key in decision-making for businesses and government. These methods apply sophisticated mathematical approaches to help identify the most effective ways to deliver products and services under conditions of scarcity, such as how to route public buses to satisfy demand more efficiently, to optimize an investment portfolio, or to route trucks to deliver products at reduced cost. According to the Institute for Operations Research and Management Science, benefits from such methods provided, conservatively, more than $213 billion in savings between 1974 and 2013. Nevertheless, many current problems in areas such as health care, smart cities and transport involve huge amounts of data and complex operational restrictions that remain incompatible with existing approaches—even as major stakeholders, such as IBM, are identifying advanced analytics as fertile ground for business/economic growth, a sector in which Canada can greatly benefit from. This proposal aims to investigate new mathematical and computational methods to tackle challenging problems in optimization. The research direction is based on innovative uses of decision diagrams (DD), a mathematical data structure originally introduced in logic and computer science. As demonstrated by the applicant’s recent research, novel DDs can be particularly useful for solving optimization problems with huge data sets, whereby data is not represented explicitly and comprehensively at the outset, but introduced incrementally during the solution procedure. The applicant will consequently develop new theoretical and computational data-analytics methodologies focusing, over five years, on five challenging applied cases in routing, healthcare, online security, incentive auctions and sports. These methods will advance the field academically short and long term, as well as lay the foundation for robust practical applications for a wide range of other scenarios and persistent challenges, helping establish Canada as one of the leaders in Big Data Analytics. Due to the practical and diverse applicability of the investigated methods, the proposed research fosters collaboration with industrial partners and will be aimed at leveraging substantial grant applications post the five-year program. Under NSERC Discovery, collaborators from Carnegie Mellon University, the University of Connecticut, IBM T. J. Watson Research Center and Google will partner on projects.

随着无处不在的数据和技术的使用，数据分析方法已经成为企业和政府决策的关键。这些方法采用复杂的数学方法来帮助确定在稀缺条件下提供产品和服务的最有效方法，例如如何更有效地安排公共汽车的路线以满足需求，优化投资组合，或安排卡车以降低成本交付产品。据美国运筹学与管理科学研究所（Institute for Operations Research and Management Science）的数据，保守地说，从1974年到2013年，这些方法节省了2130多亿美元。然而，医疗保健、智慧城市和交通等领域的许多当前问题涉及大量数据和复杂的操作限制，这些问题仍然与现有方法不兼容，即使IBM等主要利益相关者将高级分析视为商业/经济增长的沃土，而加拿大可以从中受益匪浅。本提案旨在研究新的数学和计算方法来解决优化中的挑战性问题。研究方向是基于决策图（DD）的创新使用，决策图是一种最初在逻辑和计算机科学中引入的数学数据结构。正如申请人最近的研究所证明的那样，新颖的dd对于解决具有庞大数据集的优化问题特别有用，因为数据在开始时没有明确和全面地表示，而是在解决过程中逐步引入。因此，申请人将在五年内开发新的理论和计算数据分析方法，重点关注路由，医疗保健，在线安全，激励拍卖和体育方面的五个具有挑战性的应用案例。这些方法将在短期和长期内推动该领域的学术发展，并为广泛的其他场景和持续挑战的强大实际应用奠定基础，帮助加拿大成为大数据分析的领导者之一。由于研究方法的实用性和多样化适用性，拟议的研究促进了与工业伙伴的合作，并将旨在利用五年计划后的大量拨款申请。在NSERC Discovery项目下，来自卡内基梅隆大学、康涅狄格大学、IBM沃森研究中心和b谷歌的合作者将在项目上合作。