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.