Network Analysis Using Inverse Optimization

这项研究的目的是使用数学优化来解决广泛的问题，包括改进互联网路由协议，设计有效的电信带宽定价方法，以及从匿名手机数据实时推断流量。最常见的域内互联网路由协议需要为网络中的每条链路创建虚构的“成本”。执行此操作的标准启发式方法可能会导致不必要的网络拥塞。对带宽市场的观察表明，定价往往效率低下，这允许套利：聪明的购买者往往可以建造比他们支付的更有价值的连接。美国国家公路交通安全管理局的一项研究估计，在任何给定的时间，3%的美国司机都在打手机；通过匿名跟踪每个呼叫从一个手机发射塔到另一个手机发射塔的进程，有可能在不侵犯任何呼叫者隐私的情况下估计该地区的交通模式。尽管这些问题看似无关，但它们都有相似的潜在数学结构。将研究这些优化问题的共享数学结构，并将利用所获得的知识来开发方法，以获得这些问题以及具有相同特性的其他问题的更好解决方案。实际成果包括减少网络拥堵，提高带宽市场的效率，以及实时减少和响应道路拥堵的方法。

This research is aimed at using mathematical optimization to solve a wide range of problems, including improving internet routing protocols, devising efficient methods of pricing telecommunications bandwidth, and inferring traffic flows in real-time from anonymous cell phone data. The most common intra-domain internet routing protocol requires creating fictitious "costs" for each link in the network. The standard heuristic method for doing that may lead to unnecessary network congestion. Observations of the bandwidth market show that there is often inefficiency in pricing, which allows arbitrage: clever purchasers can often construct more valuable connectivity than they pay for. A National Highway Traffic Safety Administration study estimated that 3% of American drivers are talking on cell phones at any given time; by anonymously tracking the progression of each call from one cell tower to another, it may be possible to estimate traffic patterns in the area without violating any individual caller's privacy.Although seemingly unrelated, these problems all have similar underlying mathematical structure. The shared mathematical structure of these optimization problems will be investigated and the knowledge gained will be used to develop ways of obtaining better solutions to each of these problems, as well as others which share the same properties. Practical outcomes include a decrease in network congestion, increased efficiency in the bandwidth marketplace, and real-time methods for deducing and responding to roadway congestion.