Theory, computations and applications of structured Mixed-Integer Programs

混合规划是现代企业定量决策的重要工具。其应用包括航空运输、电信、物流和制造业。我的研究的长期目标是改进MIP的解决方案，通过提供对其属性的更好的理论理解，改进算法思想，并最终允许在更大范围内解决现实世界的优化问题。该建议通过研究在某些应用中出现的特定结构来推进这一目标。两个研究流将得到解决。 第一个流涉及在MIP中考虑稀疏性，特别是在切割平面中。稀疏性是非零分量数量的度量，它是允许几种算法变得更快的重要因素。这是来自实际应用的几个基准MIP中的一个突出特征-在大量这样的基准MIP中，平均稀疏度接近1%。 切割平面是MIP实际解决方案中最重要的组成部分之一，在所有切割平面中，分裂切割是影响最大的切割平面。在最近的一项工作中，我们已经调查了分裂削减稀疏分裂和显示，通过计算实验，这子类的分裂削减是非常重要的。 因此，这第一个流将解决理论和计算问题，出现在这样的稀疏参数的基础上，最终目标是提高MIP算法的性能。 第二个流是专门研究的MIP配方的车辆路径（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.