We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addition, it can scale to very large problems because its core operation is matrix-vector multiplications. PDLP is derived by applying the primal-dual hybrid gradient (PDHG) method, popularized by Chambolle and Pock (2011), to a saddle-point formulation of LP. PDLP enhances PDHG for LP by combining several new techniques with older tricks from the literature; the enhancements include diagonal preconditioning, presolving, adaptive step sizes, and adaptive restarting. PDLP improves the state of the art for first-order methods applied to LP. We compare PDLP with SCS, an ADMM-based solver, on a set of 383 LP instances derived from MIPLIB 2017. With a target of $10^{-8}$ relative accuracy and 1 hour time limit, PDLP achieves a 6.3x reduction in the geometric mean of solve times and a 4.6x reduction in the number of instances unsolved (from 227 to 49). Furthermore, we highlight standard benchmark instances and a large-scale application (PageRank) where our open-source prototype of PDLP, written in Julia, outperforms a commercial LP solver.

When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover. The indoor dominant path (IDP) model, introduced by Wölfle et al., is shown in the literature to have good validation and generalization error, is faster to compute than competing methods, and is used in commercial software such as WinProp, iBwave Design, and CellTrace. The previous algorithms known for computing it involved a worst-case exponential-time tree search, with pruning heuristics for speed.

As smartphone users increasingly rely on cellular networks to access voice, video, and web applications, guaranteeing good performance and high availability is more important than ever. Historically, managing cellular network configuration has been a manual, error-prone process; recently, automated solutions such as SON (Self-Organizing Networks) controllers are being deployed for dynamic tuning of network configuration to improve end-user service performance under dynamic network and traffic conditions. SON automates many aspects of cellular network configuration, but it is nonetheless susceptible to software bugs and expected traffic changes that could result in sub-optimal performance. In this paper, we propose a capability (Veracity) to analyze and quantify the performance effects of SON actions. Assessing the effects of SON control is difficult because of the dynamic nature of SON and the dependency of end-user performance on factors such as radio channel quality, mobility and traffic load. Veracity addresses these using model-driven impact detection and quantification. Our evaluation using data collected from an operational cellular network demonstrates that Veracity is accurate. Veracity is now being used by the service providers' field operation teams for the assessment of SON effectiveness in arenas and stadiums.

IPTV service providers offering Video-on-Demand currently use servers at each metropolitan office to store all the videos in their library. With the rapid increase in library sizes, it will soon become infeasible to replicate the entire library at each office. We present an approach for intelligent content placement that scales to large library sizes (e.g., 100 Ks of videos). We formulate the problem as a mixed integer program (MIP) that takes into account constraints such as disk space, link bandwidth, and content popularity. To overcome the challenges of scale, we employ a Lagrangian relaxation-based decomposition technique combined with integer rounding. Our technique finds a near-optimal solution (e.g., within 1%-2%) with orders of magnitude speedup relative to solving even the linear programming (LP) relaxation via standard software. We also present simple strategies to address practical issues such as popularity estimation, content updates, short-term popularity fluctuation, and frequency of placement updates. Using traces from an operational system, we show that our approach significantly outperforms simpler placement strategies. For instance, our MIP-based solution can serve all requests using only half the link bandwidth used by least recently used (LRU) or least frequently used (LFU) cache replacement policies. We also investigate the tradeoff between disk space and network bandwidth.

Ever wonder why that Kia Ad ran during Iron Chef? Traditional advertising methodology on television is a fascinating mix of marketing, branding, measurement, and predictive modeling. While still a robust business, it is at risk with the recent growth of online and time-shifted (recorded) television. A particular issue is that traditional methods for television advertising are far less efficient than their counterparts in the online world which employ highly sophisticated computational techniques. This paper formalizes an approach to eliminate some of these inefficiencies by recasting the process of television advertising media campaign generation in a computational framework. We describe efficient mathematical approaches to solve for the task of finding optimal campaigns for specific target audiences. In two case studies, our campaigns report gains in key operational metrics of up to 56% compared to campaigns generated by traditional methods.

Multidimensional distributions are often used in data mining to describe and summarize different features of large datasets. It is natural to look for distinct classes in such datasets by clustering the data. A common approach entails the use of methods like k-means clustering. However, the k-means method inherently relies on the Euclidean metric in the embedded space and does not account for additional topology underlying the distribution.

IPTV service providers offering Video-on-Demand currently use servers at each metropolitan office to store all the videos in their library. With the rapid increase in library sizes, it will soon become infeasible to replicate the entire library at each office. We present an approach for intelligent content placement that scales to large library sizes (e.g., 100Ks of videos). We formulate the problem as a mixed integer program (MIP) that takes into account constraints such as disk space, link bandwidth, and content popularity. To overcome the challenges of scale, we employ a Lagrangian relaxation-based decomposition technique combined with integer rounding. Our technique finds a near-optimal solution (e.g., within 1-2%) with orders of magnitude speedup relative to solving even the LP relaxation via standard software. We also present simple strategies to address practical issues such as popularity estimation, content updates, short-term popularity fluctuation, and frequency of placement updates. Using traces from an operational system, we show that our approach significantly outperforms simpler placement strategies. For instance, our MIP-based solution can serve all requests using only half the link bandwidth used by LRU or LFU cache replacement policies. We also investigate the trade-off between disk space and network bandwidth.

Link and node failures in IP networks pose a challenge for network control algorithms. Routing restoration, which computes new routes that avoid failed links, involves fundamental tradeoffs between efficient use of network resources, complexity of the restoration strategy and disruption to network traffic. In order to achieve a balance between these goals, obtaining routings that provide good performance guarantees under failures is desirable.In this paper, building on previous work that provided performance guarantees under uncertain (and potentially unknown) traffic demands, we develop algorithms for computing optimal restoration paths and a methodology for evaluating the performance guarantees of routing under failures. We then study the performance of route restoration on a diverse collection of ISP networks. Our evaluation uses a competitive analysis type framework, where performance of routing with restoration paths under failures is compared to the best possible performance on the failed network. We conclude that with careful selection of restoration paths one can obtain restoration strategies that retain nearly optimal performance on the failed network while minimizing disruptions to traffic flows that did not traverse the failed parts of the network.

MPLS is becoming an important protocol for intradomain routing. MPLS routers are offered by the major vendors and many ISPs are deploying MPLS in their IP backbones, as well as in ATM and frame relay networks. For this period of possible transition to MPLS, it is urgent to increase our understanding of the power and limitation of MPLS. An attraction to MPLS is the flexibility it offers in engineering the routing of traffic in a network, e.g., to support higher demands without overloading any links. Mitra and Ramakrishnan [GLOBECOM'99] showed that optimal routing solutions may be found for a diverse set of traffic engineering goals. However, for a network with N nodes (routers) and M edges (links), their MPLS implementation may use /spl Omega/(N /spl times/ M) different labels. This is prohibitive since the number of labels is the number of entries needed in the router tables. We present an algorithm reducing the number of MPLS labels to N + M without increasing any link load. Our explicit N + M bound makes it easy to limit the table size requirement for a planned network, and the linearity allows for tables implemented in fast memory. For differentiated services with K traffic classes with different load constraints, our bound increases to K(N + M). Our stack-depth is only one, justifying implementations of MPLS with limited stack-depth.

Intra-domain traffic engineering can significantly enhance the performance of large IP backbone networks. Two important components of traffic engineering are understanding the traffic demandsand configuring the routing protocols. These two components are inter-linked, as it is widely believed that an accurate view of traffic is important for optimizing the configuration of routing protocols and through that, the utilization of the network.This basic premise, however, never seems to have been quantified --How important is accurate knowledge of traffic demands for obtaining good utilization of the network? Since traffic demand values are dynamic and illusive, is it possible to obtain a routing that is "robust" to variations in demands? Armed with enhanced recent algorithmic tools we explore these questions on a diverse collection of ISP networks. We arrive at a surprising conclusion: it is possible to obtain a robust routing that guarantees a nearly optimal utilization with a fairly limited knowledge of the applicable traffic demands.

We discuss several issues that arise in the implementation of Martin, Otto, and Felten's Chained Lin-Kernighan heuristic for large-scale traveling salesman problems. Computational results are presented for TSPLIB instances ranging in size from 11,849 cities up to 85,900 cities; for each of these instances, solutions within 1% of the optimal value can routinely be found in under one CPU minute on a 300 MHz Pentium II workstation, and solutions within 0.5% of optimal can routinely be found in under ten CPU minutes. We also demonstrate the scalability of the heuristic, presenting results for randomly generated Euclidean instances having up to 25,000,000 cities. For the largest of these random instances, a tour within 1% of an estimate of the optimal value was obtained in under one CPU day on a 64-bit IBM RS6000 workstation.

The Shannon capacity equation defines the total data transmission capacity of a transmission channel as a function of receiver SNR and bandwidth. When the frequency-overlapped (FO) duplex mode of operation with an echo canceller is implemented on a digital subscriber loop (DSL) channel, then the near-end receiver SNR that determines the inbound capacity is not only a function of the far-end transmitted signal power, but also of the residual near-end transmit signal power that leaks through the echo canceller. This 'coupling' occurs on both ends of the copper loop for upstream and downstream reception. Consequently, maximization of the data transmission capacity is a "bidirectional" problem. This problem has not been analyzed in the literature. We define the notion of the total bidirectional data capacity of a copper loop and formulate the maximum bidirectional capacity that can be achieved when a power budget is allocated to each of the two transmitters. We then compute the channel capacity by an integer linear programming (ILP) technique for various channel and noise conditions and also compare the results with the data rates that are obtained by a modified "water-filling" algorithm designed for FO duplex operation and with the channel capacities of the conventional frequency-division (FD) simplex transmission.

We use a branch-and-cut search to solve the Whizzkids'96 vehicle routing problem, demonstrating that the winning solution in the 1996 competition is in fact optimal. Our algorithmic framework combines the LP-based traveling salesman code of Applegate, Bixby, Chvátal, and Cook, with specialized cutting planes and a distributed search algorithm, permitting the use of a computing network located across Rice, Princeton, AT&T, and Bonn. The 1996 problem instance wasdeveloped by E. Aartsand J. K. Lenstra, and the competition was sponsored by the information technology firm CMG and the newspaper De Telegraaf.

An important class of functions that arise in statistics and other areas are the log-concave functions.Here we provide the first polynomial time algorithm to generate samples from a given log-concave distribution.The algorithm is fairly simple and natural; it is the proof of its fast convergence that is new.To this end, we prove a general isoperimetric inequality for convex sets and use this together with recent developments in the theory of rapidly mixing Markov chains.We use our sampling algorithm to develop an algorithm for integrating log-concave functions.As one application, we are able to develop an algorithm for approximating the volume of convex bodies given by an oracle; we do so by enclosing the given body in a cube, defining a log-concave function that is 1 on the body and exponentially falls off outside, and integrating this function.This a.llo ws us to avoid one of the complications in prior algorithms for computing volumes -dealing with sharp corners -and results in an algorithm which is faster than previous algorithms.

The job-shop scheduling problem is a notoriously difficult problem in combinatorial optimization. Although even modest sized instances remain computationally intractable, a number of important algorithmic advances have been made in recent years by J. Adams, E. Balas and D. Zawack; J. Carlier and E. Pinson; B. J. Lageweg, J. K. Lenstra and A. H. G. Rinnooy Kan; and others. Making use of a number of these advances, we have designed and implemented a new heuristic procedure for finding schedules, a cutting-plane method for obtaining lower bounds, and a combinatorial branch and bound algorithm. Our optimization procedure, combining the heuristic method and the combinatorial branch and bound algorithm, solved the well-known 10×10 problem of J. F. Muth and G. L. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.