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

点击翻译按钮获取中文摘要

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.