Theory, computations and applications of structured Mixed-Integer Programs

混合整数规划(MIP)是现代企业定量决策的一种非常重要的工具。它的应用包括航空运输、电信、物流和制造。我研究的长期目标是改进MIP的求解方法，通过更好地从理论上理解MIP的性质，改进算法思想，最终允许人们在更大范围内解决现实世界的优化问题。这项建议通过研究某些应用中出现的特定结构来推进这一目标。将讨论两个研究方向。第一个流程涉及到在MIP中考虑稀疏性，特别是在切割平面中。稀疏性是对非零组件数量的度量，它是使几种算法变得更快的一个重要因素。这是来自实际应用的几个基准MIP中的一个突出特征-在大量这样的基准MIP中，平均稀疏度接近1%。切割面是MIP实际解决方案中最重要的组成部分之一，而在所有切割面中，影响较大的是裂割面。在最近的一项工作中，我们研究了由稀疏分裂得到的分裂割，并通过计算实验表明，分裂割的这一子类是非常重要的。因此，这第一个流将解决基于这样的稀疏性参数而产生的理论和计算问题，最终目标是提高MIP算法的性能。第二个流致力于研究在车辆路径(VRP)的MIP公式的背景下获得的结构，特别是在不确定的情况下。车辆路径问题是一个重要的优化问题，它试图找到一种最小成本的方法来安排一支车队的路线，以满足一组客户的需求，同时尊重每辆车的能力。它在物流和运输中得到了应用。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.