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

数学编程仍然是最有用的工具，有时也是唯一的工具，用于对物流和机器学习中出现的几个问题进行建模和支持决策。该发现计划的长期目标是提出新颖的模型和算法来解决这两个领域中出现的几类离散优化问题，特别强调处理超大规模数据集。 针对物流和机器学习中出现的几类问题的最先进的模型和算法已被证明可以有效地处理中小型问题，但在大规模问题中的用途仍然有限。该提案中描述的短期目标试图解决以下三个领域：1）大规模优化的递减松弛方法； 2）用于超大规模优化的可扩展元和数学； 3）改进车辆路径和调度问题的精确解决方案。 1. 递减松弛是一种分解技术，其中决策者在受限（但可能很困难）问题和定价子问题（即使在大规模问题中也通常很容易）之间进行迭代。简化的问题提供了原始问题的松弛，而子问题则根据需要细化了该问题。该方案已被证明对于处理极小极大和极大极小目标非常有效。我们将研究这种技术的使用和局限性，以实现与有序中值位置问题所产生的类似（但不是那么极端）的目标。 2. 元数学和数学仍然是处理一些非常大的组合问题的算法方案，因为它们始终避免解决非常难以解决的整数程序。然而，它们仍然可能面临大规模的可扩展性问题。我们将为开发具有更好的大规模可扩展性的新颖元和数学做出贡献。 3. 列生成仍然是处理大量车辆路线和调度问题的领先优化技术。很少有人关注处理简并性的技术。该拨款提案将研究涉及子问题和受限主问题加速的改进。对于前者，我们将研究选择性定价策略。对于后者，我们将专注于开发一个能够有效处理简并性的理论框架。 在所有情况下，总部的培训仍然是该发现研究计划的核心。与该研究项目相关的总部将在数学优化、物流和机器学习之间培养强大的分析技能。这是一套与加拿大经济极​​其相关的技能。

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.