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

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

• 批准号: RGPIN-2020-06311
• 负责人: Contardo, Claudio
• 金额: $ 2.26万
• 依托单位: Université du Québec à Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=740725
• 关键词: 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将在数学优化、物流和机器学习之间发展强大的分析技能。这是一套对加拿大经济具有极高相关性的技能。