Optimization with Decision Diagrams: Theory and Applications

随着数据的无处不在和技术的使用，数据分析方法已经成为企业和政府决策的关键。这些方法应用复杂的数学方法来帮助确定在稀缺条件下交付产品和服务的最有效方式，例如如何为公共汽车布线以更有效地满足需求，如何优化投资组合，或如何布线卡车以降低成本交付产品。根据运筹学和管理科学研究所的数据，保守地说，从1974年到2013年，这些方法带来的好处节省了超过2130亿美元。然而，医疗保健、智能城市和交通等领域当前的许多问题涉及海量数据和复杂的操作限制，这些问题仍然与现有方法不相容-尽管IBM等主要利益攸关方正在将先进的分析确定为商业/经济增长的肥沃土壤，这是加拿大可以极大受益的一个领域。这项建议旨在研究新的数学和计算方法，以解决优化中具有挑战性的问题。研究方向是基于决策图(DD)的创新使用，决策图是最初在逻辑和计算机科学中引入的一种数学数据结构。申请人最近的研究表明，新的DDS对于解决具有巨大数据集的优化问题特别有用，因为数据在一开始并不是明确和全面的表示，而是在求解过程中逐步引入。因此，申请者将开发新的理论和计算数据分析方法，在五年内将重点放在路由、医疗保健、在线安全、奖励拍卖和体育领域的五个具有挑战性的应用案例上。这些方法将在短期和长期的学术上推动该领域的发展，并为广泛的其他场景和持久挑战的强大实际应用奠定基础，帮助确立加拿大作为大数据分析领域的领导者之一。由于调查方法的实用性和多样性，拟议的研究促进了与行业合作伙伴的合作，并将旨在利用五年期计划后的大量赠款申请。根据NSERC Discovery，来自卡内基梅隆大学、康涅狄格大学、IBM T.J.Watson研究中心和谷歌的合作者将在项目上进行合作。**

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.**