Optimization with Decision Diagrams: Theory and Applications

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

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

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