Theory, computations and applications of structured Mixed-Integer Programs

混合整数规划（MIP）是现代企业定量决策的重要工具。它的应用包括航空运输、电信、物流和制造业。我研究的长期目标是改进MIPs的解决方法，通过对其特性提供更好的理论理解，改进算法思想，最终允许人们在更大的范围内解决现实世界的优化问题。本提案通过研究在某些应用中出现的特定结构来推进这一目标。将讨论两个研究方向。第一个流处理的是考虑mip的稀疏性，特别是在裁剪平面时。稀疏性是对非零组件数量的度量，它是使一些算法变得更快的一个重要因素。这是来自实际应用的几个基准mip的一个突出特征——在大量这样的基准mip中，平均稀疏度接近1%。切割平面是MIPs实际解决方案中最重要的组成部分之一，在所有切割平面中，劈开切割是影响较大的切割平面。在最近的一项工作中，我们研究了从稀疏分割得到的分割分割，并通过计算实验表明，这类分割分割是非常重要的。因此，第一个流将解决基于这种稀疏度参数产生的理论和计算问题，最终目标是提高MIP算法的性能。第二流致力于研究在车辆路由（VRP）的MIP公式背景下获得的结构，特别是在不确定的情况下。VRP是一个重要的优化问题，它寻求找到成本最低的方式来安排车队，以满足一组客户的需求，同时每辆车的容量都得到尊重。它在物流和运输领域得到了应用。VRP中的一个限制假设是，所有的客户需求都是事先已知的，但情况并非总是如此。因此，最近，新的研究兴趣一直致力于研究需求不确定的问题的变体（即随机VRP）。因此，第二流旨在显著推进解决随机VRP的最新技术。特别感兴趣的是数据驱动的方法，即仅使用历史数据作为输入进行优化的方法。该提案将研究该问题现有版本的新算法，以及为其更现实的版本建模的新范例。最终，这些方法的发展将显著提高VRP模型在实际应用中的适用性。通过这项建议培训的HQP将获得定量决策的宝贵技能，获得理论和实施知识，这在学术界和工业界都很重要。

Mixed-Integer Programming (MIP) is an extremely important tool in quantitative decision making within modern corporations. Its applications include air transportation, telecommunications, logistics and manufacturing. The long-term goal of my research is to improve solution methods for MIPs, by providing better theoretical understanding of its properties, improving algorithmic ideas and ultimately allowing one to solve real-world optimization problems at a larger scale. This proposal advances this goal by studying particular structures that appear in some applications. Two research streams will be addressed. The first stream deals with considering sparsity in MIPs, particularly in cutting planes. Sparsity is a measure of the number of nonzero components, and it is an important factor that allows several algorithms to become faster. It is a prominent feature in several benchmark MIPs that came from practical applications - in a large set of such benchmark MIPs, the average sparsity is close to 1%. Cutting planes are one of the most important components in the practical solution of MIPs and, among all cutting planes, split cuts are the ones with greater impact. In a recent work, we have investigated split cuts obtained from sparse splits and show, through computational experiments, that this subclass of split cuts is very important. Therefore, this first stream will address theoretical and computational questions that arise based on such a sparsity parameter, with the ultimate goal to improve the performance of MIP algorithms. The second stream is dedicated to studying the structure obtained in the context of MIP formulations for vehicle routing (VRP), particularly under uncertainty. The VRP is an important optimization problem that seeks to find the minimum cost way to route a fleet of vehicles to satisfy a set of customer demands in such a way that the capacity of each vehicle is respected. It finds applications in logistics and transportation. One limiting assumption in the VRP is that all customer demands are known in advance, which is not always the case. Thus, recently, renewed research interest has been devoted to studying variants of the problem where demands are uncertain (i.e. stochastic VRP). Thus, this second stream aims to significantly advance the state-of-the-art in solving the stochastic VRP. Of particular interest are data-driven approaches, i.e. approaches that optimize using only historical data as input. The proposal will investigate new algorithms for existing versions of the problem and new paradigms for modeling more realistic versions of it. Ultimately, the development of such approaches will significantly increase the applicability of VRP models in real-world applications. HQP trained as a result of this proposal will gain valuable skills in quantitative decision making, acquiring both theoretical and implementation knowledge, which is important in both academia and industry.