AF: Small: Approximation Algorithms for Problems in Logistics

点击翻译按钮获取中文摘要

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.