AF: Small: Approximation Algorithms for Problems in Logistics

物流问题是当今经济运作的核心：如何最好地将包裹运送到预定目的地，如何最好地设计零售商的供应网络，如何最好地管理零售商供应链中物品的库存水平。这只是为了在当今的商业世界中有效地管理资源而必须经常解决的优化问题类型的一个小示例。这些问题中的每一个都可以被表述为一个精确的数学优化问题——通过精确地指定什么构成了一个可行的解决方案，一些可以在实践中实现的东西，并使用一个目标函数来捕捉这个解决方案有多好，PI为寻找特定物流问题的最佳解决方案提供了一个精确的意义。不幸的是，从计算复杂性的角度来看，这些问题中的大多数都属于一类被认为是难以解决的问题，因此假设了一个更容易的目标：设计有效的算法来找到可证明的接近最优的解决方案，因为找到的解决方案保证在最佳可能的指定百分比内。优化和分析工具将在培养下一代学生方面发挥基础作用，这些学生将继续发明和管理未来的颠覆性行业。结合算法设计的前沿思想来解决物流问题是让学生了解这些工具的潜力的有效方法。这个项目既可以培养成为未来学术界和工业界领袖的博士生，也可以在这一研究领域和本科课堂之间建立联系，将有助于有效地教育下一代。本项目主要针对出现的离散优化问题,在物流,包括臭名昭著的旅行商问题(以及车辆路径问题密切相关,其目的不仅仅是找到最短的路线覆盖一组点,但其目的是达到每个点每个点集,这样达到一路上不迟于一个特殊用途的最短路径只是一个目的地的服务),安装轮辐服务网络的中心网络设计问题，以便最大限度地减少安装轮毂的成本和轮辐选择隐含的服务成本（同时尊重一个轮毂可以服务的轮辐数量的容量限制），以及许多多项目库存管理问题，这些问题模拟了批量订购的固定成本与维持额外库存的成本之间的权衡，直到需要为止。装箱问题，其目标是将给定尺寸的物品划分成尽可能少的部分，同时尊重每个部分在给定容量范围内的约束。该项目侧重于开发新的算法技术，为这些关键问题提供良好的解决方案。在设计这些问题的有效算法时，无论是从理论还是从实践的角度来看，经常出现的一个因素是发展数学规划，使问题放松，从而能够有效地计算边界，从而证明手头的解决方案几乎是最优的。该项目将探索一些新的方向，以开发比传统方法更强大的扩展配方。该项目将解决一些具体的离散确定性随机优化问题，重点关注一些似乎处于适当抽象水平的问题——足够简单，可以设计和分析具有性能保证的算法——并且足够复杂，以便从这些程式化模型中获得的算法见解将以有意义的方式转化为激励现实世界的应用。

Logistics problems lie at the heart of the functioning of today's economy: how best to have packages routed to their intended destination, how best to design the supply networks for retailers, how best to manage the inventory levels for items in a retailer's supply chain. This is just a small sample of the types of optimization problems that must be routinely solved for the efficient management of resources in today's business world. Each of these problems can be formulated as a precise mathematical optimization problem - by specifying exactly what constitutes a feasible solution, something that can be implemented in practice, and using an objective function that captures how good that solution is, the PI gives a precise meaning to the issue of finding the best solution to a particular logistics problem. Unfortunately, most of these problems, from the perspective of computational complexity, belong to a class of problems that are believed to be intractable, and hence an easier goal is posited: to design efficient algorithms that find solutions that are provably near-optimal, in that the solutions found are guaranteed to be within a specified percent of the best possible.Tools in optimization and analytics will play a foundational role in the training of the next generation of students who will go on to invent and manage the disruptive industries of the future. Incorporating cutting-edge ideas from algorithm design for the problems in logistics is an effective way to get students to understand the potential that these tools have. This project, by both training PhD students who will be future leaders in both academia and industry, as well as by providing a link between this line of research and the undergraduate classroom, will help effectively educate this next generation.This project focuses on a number of discrete optimization problems that arise in logistics, including the notorious traveling salesman problem (as well as a closely related vehicle-routing problem, where the aim is not merely to find the shortest route covering a set of points, but the aim is to reach each point in the set so that each point is reached along the way not much later than a special-purpose shortest path just serving that one destination), a central network-design problem of installing a hub-and-spoke service network, so as to minimize the cost of the hubs installed plus the service costs implicit in that spoke selection (while respecting capacity constraints on the number of spokes that can be served by one hub), a number of multi-item inventory management problems that model the tradeoffs between the fixed costs in placing bulk orders versus the cost of maintaining the additional inventory until it is needed, and the bin-packing problem, in which one aims to partition items of given sizes into as few parts as possible, while respecting the constraint that each part is within a given capacity bound. This project focuses on the development of new algorithmic techniques to produce good solutions for these critical problems. One element that is frequently present in the design of an effective algorithm for these problems, either from a theoretical or a practical vantage point, is the development of a mathematical programming relaxation of the problem that enables the efficient computation of bounds that can prove that a solution at hand is nearly optimal. This project will pursue a number of new directions for developing extended formulations that are stronger than traditional approaches. This project will address a number of specific discrete deterministic & stochastic optimization problems, focusing on a few problems that appear to be at the right level of abstraction -- simple enough to permit the design & analysis of algorithms with performance guarantees -- and complex enough so that algorithmic insights gained from these stylized models will translate in a meaningful way to the motivating real-world application.