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.