Computing approximate Nash equilibria in general network revenue management games

Computing optimal capacity allocations in network revenue management is computationally hard. The problem of computing exact Nash equilibria in non-zero-sum games is computationally hard, too. We present a fast heuristic that, in case it cannot converge to an exact Nash equilibrium, computes an approximation to it in general network revenue management problems under competition. We also investigate the question whether it is worth taking competition into account when making (network) capacity allocation decisions. Computational results show that the payoffs in the approximate equilibria are very close to those in exact ones. Taking competition into account never leads to a lower revenue than ignoring competition, no matter what the competitor does. Since we apply linear continuous models, computation time is very short.     

Single-commodity robust network design problem: Complexity,instances and heuristic solutions

We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {−1, 0, 1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

The non-approximability of bicriteria network design problems

Let G be an undirected graph with two edge costs (c-cost and d-cost). We want to minimize the diameter of a spanning subgraph S (under d-cost) subject to the constraint that the total cost of the edges in S (with respect to c) does not exceed a given budget. We prove that this problem is non-approximable, even in some special cases. Similar results are proved if the stretch factor or the root stretch factor is considered instead of the diameter.     

Predicting the bioactivity of glasses using the network connectivity or split network models

Bioactive glasses (BG) are used as bone substitutes and re-mineralising additives in toothpastes. They work by precipitating apatite on their surface, and the network connectivity (NC) and split network models can be used to predict their bioactivity, i.e. their ability to form apatite.While NC predicts glass degradation and has been used successfully to predict the bioactivity of BG, it does not take into account their phosphate content. Our experimental data confirm predictions using the split network model by Edén [Journal of Non-Crystalline Solids 357 (2011) 1595–1602], that “as long as P remains predominantly as Q_P⁰ tetrahedra and the average silicate network-polymerisation is ‘favourable’, the bioactivity enhances monotonically for increasing phosphorus content of the BG”. Results show that phosphate plays a key role in bioactivity and apatite formation of BG. This can be explained by the fact that phosphorus does not form part of the silicate network, but instead forms a separate orthophosphate phase. However, NC and split network models are still useful approaches for predicting BG bioactivity and apatite formation, if care is exercised when applying the models to glasses that contain more components than simple SiO₂–P₂O₅–CaO–Na₂O systems.     

Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε ⁻² + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492.     

Wireless network capacity management: A real options approach

This paper applies financial option valuation methods to new wireless network capacity investment decision timing. In particular, we consider the case of network capacity for cellular telephone service. Given a cluster of base stations (with a certain traffic capacity per base station), we determine when it is optimal to increase capacity for each of the base stations contained in the cluster. We express this in terms of the fraction of total cluster capacity in use, i.e. we calculate the optimal time to upgrade in terms of the ratio of observed usage to existing capacity. We study the optimal decision problem of adding new capacity in the presence of stochastic wireless demand for services. A four factor algorithm is developed, based on a real options formulation. Numerical examples are provided to illustrate various aspects of the model.