Large-Scale and Big Data Optimization

大规模、大数据优化

• 批准号: RGPIN-2017-06715
• 负责人: Jaumard, Brigitte
• 金额: $ 2.99万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711861
• 关键词: Large; Scale; Big; Data; Optimization

In today's digital world, with ever increasing amounts of data comes the need to solve optimization problems of unprecedented sizes. Machine learning, communication and social networks, logistics systems are some of the many prominent application domains where optimization problems arise with tens of thousands or millions of variables. Many optimization models and algorithms, while exhibiting great efficiency in modest dimensions, have great difficulties to scale for instances of this size and do not offer satisfactory solution. The primary and long-term objective of my research is to contribute to the design of novel optimization algorithms capable of working in very large-scale setting. I plan to investigate both exact and heuristic methods, and validate the findings on some particular applications in communication, logistics and social networks. For exact methods, the objective is to integrate knowledge based on both theoretical and empirical evidence from several disciplines, and explore the "what, why, how, and do" paradigm with an emphasis on (i) modelling aspects, (ii) combination of mathematical models, and (iii) parallelization techniques in order to take advantage of the heterogeneous environments combining multi-core processors, multi-threaded programming and GPU accelerators for very large scale optimization. While those environment were only available on mainframe computers, they are now available to computers that are easily accessible to the industry. For heuristic methods, focus will be on meta-heuristics, a wide class of solution methods that have been successfully applied to many optimization problems. However, they seem to have reached their limits to solve very large combinatorial problems such as those arising in cross-docking or network optimization. This is because meta-heuristics explore the solution space with ad-hoc methods, whose efficiency and computing time highly depend on the topology of the local optima which, except for some very particular problems, are very difficult to foresee. We plan to replace the ad-hoc exploration of the solution space with an informed exploration guided by machine learning. Comparison will be made with direct machine learning algorithms on practical problems arising in: (i) supply chain management and in particular with cross-docking, and (ii) network optimization and (iii) mechanism design in social networks. Data required by machine learning algorithms will be provided by ClearD and Ciena for the first two applications, and an organization/industrial partner needs to be identified for the third one. The results of my research will provide the industry (like ClearD and Ciena) information technology management tools for efficient and automated cross-docking/network management, not only to improve competitiveness but also to reduce energy consumption and therefore carbon footprint.

在当今的数字世界中，随着数据量的不断增加，需要解决前所未有的规模的优化问题。机器学习、通信和社交网络、物流系统是许多突出的应用领域中的一些，其中出现了数万或数百万变量的优化问题。许多优化模型和算法虽然在适度的尺寸下表现出很高的效率，但很难针对这种尺寸的实例进行扩展，并且不能提供令人满意的解决方案。我研究的主要和长期目标是为设计能够在超大规模环境中工作的新颖优化算法做出贡献。我计划研究精确方法和启发式方法，并验证通信、物流和社交网络中某些特定应用的研究结果。 对于精确方法，目标是整合基于多个学科的理论和经验证据的知识，并探索“什么、为什么、如何和做”范式，重点是（i）建模方面，（ii）数学模型，以及 (iii) 并行化技术，以便利用结合多核处理器、多线程编程和 GPU 加速器的异构环境进行超大规模优化。虽然这些环境仅在大型计算机上可用，但现在可用于业界轻松访问的计算机。 对于启发式方法，重点将放在元启发式上，这是一类广泛的解决方法，已成功应用于许多优化问题。然而，它们似乎已经达到了解决非常大的组合问题（例如越库配送或网络优化中出现的问题）的极限。这是因为元启发式方法用临时方法探索解空间，其效率和计算时间高度依赖于局部最优的拓扑，除了一些非常特殊的问题外，局部最优的拓扑是很难预见的。我们计划用机器学习引导的明智探索来取代对解决方案空间的临时探索。将与直接机器学习算法就以下实际问题进行比较：（i）供应链管理，特别是越库配送，以及（ii）网络优化和（iii）社交网络中的机制设计。 机器学习算法所需的数据将由 ClearD 和 Ciena 为前两个应用程序提供，第三个应用程序需要确定组织/行业合作伙伴。 我的研究成果将为行业（如 ClearD 和 Ciena）提供信息技术管理工具，以实现高效和自动化的越库/网络管理，不仅可以提高竞争力，还可以减少能源消耗，从而减少碳足迹。