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）超大规模优化的可扩展Meta和数学方法; 3）车辆路径和调度问题的精确解的改进。1.递减松弛是一种分解技术，其中决策者在受限（但可能很难）问题和定价子问题（即使在大规模下也很容易）之间迭代。简化问题提供了原始问题的松弛，而子问题根据需要细化此问题。该方案已被证明是非常有效的处理极小极大和极大极小的目标。我们将调查这种技术的使用和限制类似---但不是那么极端---目标所产生的有序中位数定位问题。2. Meta和matheuristics仍然是处理一些非常大的组合问题的算法方案的选择，因为它们在任何时候都避免了非常困难的整数规划的解决方案。然而，它们仍然可能在大规模中遭受可扩展性问题。我们将致力于开发新的Meta和数学，在非常大的规模具有更好的可扩展性。3.列生成仍然是处理大量车辆路径和调度问题的主要优化技术。很少有人注意到处理简并的技术。这个拨款建议将调查涉及加速子问题和限制主问题的改进。对于前者，我们将研究选择性定价策略。对于后者，我们将专注于一个理论框架的发展，允许一个有效的处理简并。在所有情况下，HQP的培训仍然是这个发现研究计划的核心。与该研究计划相关的HQP将在数学优化，物流和机器学习之间的界面上开发强大的分析技能。这是一套与加拿大经济极其相关的技能。