This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and … Read more
In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results … Read more
We investigate a network design problem under traffic uncertainty which arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network so as to support all … Read more
We describe a two-stage robust optimization approach for solving network flow and design problems with demand uncertainty. We give an explicit characterization of the first-stage decisions and prove that the corresponding separation problem is NP-hard even for a network flow problem on a bipartite graph. We show, however, that if the second-stage network topology is … Read more
We introduce a new extension of Punnen’s exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen’s neighborhood by De Franceschi, Fischetti and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including … Read more
Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing … Read more
A traffic matrix $D^1$ dominates a traffic matrix $D^2$ if $D^2$ can be routed on every (capacitated) network where $D^1$ can be routed. We prove that $D^1$ dominates $D^2$ if and only if $D^1$, considered as a capacity vector, supports $D^2$. We show several generalizations of this result. Citation Centro Vito Volterra, Universita’ di Roma … Read more
Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize … Read more
We discuss interior point methods for large-scale linear programming, with an emphasis on methods that are useful for problems arising in telecommunications. We give the basic framework of a primal-dual interior point method, and consider the numerical issues involved in calculating the search direction in each iteration, including the use of factorization methods and/or preconditioned … Read more
We study the route-guidance system proposed by Jahn, Möhring, Schulz and Stier-Moses (2004) from a theoretical perspective. This approach computes a traffic pattern that minimizes the total travel time subject to user constraints, which ensure that routes suggested to users are not much longer than shortest paths. We show that when distances are measured with … Read more