Algorithms for large-scale discrete optimization problems arising in logistics and machine learning

物流和机器学习中出现的大规模离散优化问题的算法

• 批准号: RGPIN-2020-06311
• 负责人: Contardo, Claudio
• 金额: $ 0.96万
• 依托单位: Université du Québec à Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758119
• 关键词: Algorithms; large; scale; discrete; optimization

Mathematical programming remains the most useful ---and sometimes only--- tool to model and support the decision making of several problems arising in logistics and machine learning. The long-term goal of this Discovery program points toward proposing novel models and algorithms for the solution of several classes of discrete optimization problems arising in these two areas, with a particular emphasis in the handling of very large--scale datasets. State--of--the--art models and algorithms for several classes of problems arising in logistics and machine learning have shown to be efficient to handle small-- to medium--size problems, but remain of limited use in the large--scale. The short--term objectives described in this proposal attempt to address the following three areas: 1) decremental relaxation methods for large-scale optimization; 2) scalable meta and matheuristics for very large-scale optimization; 3) refinements for the exact solution of vehicle routing and scheduling problems. 1. Decremental relaxation is a decomposition technique in which the decision maker iterates between a restricted (yet potentially hard) problem and a pricing subproblem (often easy even in the large--scale). The reduced problem provides a relaxation of the original problem, while the subproblem refines this problem as needed. This scheme has been proven to be exceptionally efficient for handling minimax and maximin objectives. We will investigate the use and limits of this technique for similar ---yet not so extreme--- objectives as those arising from ordered median location problems. 2. Meta and matheuristics remain the algorithmic schemes of choice for handling some very large combinatorial problems, as they avoid at all times the solution of very hard--to--solve integer programs. However, they may still suffer from scalability issues in the large-scale. We will contribute towards the development of novel meta and matheuristics with better scalability properties in the very-large scale. 3. Column generation remains the leading optimization technique for handling a vast family of vehicle routing and scheduling problems. Little attention has been given to techniques to handle degeneracy. This grant proposal will investigate refinements involving the acceleration of subproblems and of the restricted master problem. For the former, we will investigate selective pricing strategies. For the latter, we will focus on the development of a theoretical framework allowing for an efficient handling of degeneracy. In all cases, the training of HQP remains at the heart of this Discovery research program. The HQP associated with this research program will develop strong analytical skills at the interface between mathematical optimization, logistics and machine learning. This is a set of skills of extremely high relevance for the Canadian economy.

数学编程仍然是最有用的 - 有时甚至是 - - - - 建模和支持在物流和机器学习中引起的几个问题的决策。该发现计划的长期目标指出，为解决这两个领域引起的几类离散优化问题解决新的模型和算法，特别强调处理非常大的数据集。在物流和机器学习中出现的几类问题的态度 - - 艺术模型和算法已经有效地处理小型问题，但在大型问题中仍然存在有限的使用量-规模。本提案中描述的短期目标试图解决以下三个方面：1）减少大规模优化的放松方法； 2）可扩展的元和数学学，以进行非常大规模的优化； 3）改进了车辆路由和调度问题的精确解决方案。 1。减少放松是一种分解技术，在这种技术中，决策者在受限制（但可能难的）问题和定价子问题之间迭代（即使在大规模的情况下也很容易）。减少的问题提供了原始问题的放松，而子问题根据需要完善了此问题。事实证明，该方案在处理最小值和最大值目标方面非常有效。我们将调查此技术的使用和限制，但对于类似的（但不是由有序位置问题引起的目标）而不是极端的目标。 2。元数和数学学仍然是处理一些非常大的组合问题的首选算法方案，因为它们始终避免了解决非常难以解决的整数程序的解决方案。但是，它们可能仍遭受大规模的可伸缩性问题。我们将为新型的元和数学学的发展做出贡献，并在很大程度上具有更好的可伸缩性。 3.专栏生成仍然是处理大量车辆路由和调度问题的领先优化技术。很少关注处理退化的技术。该赠款提案将调查涉及子问题加速和受限制的主问题的改进。对于前者，我们将调查选择性定价策略。对于后者，我们将重点关注一个理论框架的发展，以有效地处理堕落。在所有情况下，HQP的培训仍然是该发现研究计划的核心。与该研究计划相关的HQP将在数学优化，物流和机器学习之间的接口上发展强大的分析技能。这是一组对加拿大经济具有极高相关性的技能。