Note: A Graph-Theoretical Approach to Level of Repair Analysis

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

Interior point methods for large-scale linear programming

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

Efficiency and Fairness of System-Optimal Routing with User Constraints

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

Robust Capacity Expansion of Transit Networks

In this paper we present a methodology to decide capacity expansions for a transit network that finds a robust solution with respect to the uncertainty in demands and travel times. We show that solving for a robust solution is a computationally tractable problem under conditions that are reasonable for a transportation system. For example, the … Read more

Solving large scale linear multicommodity flow problems with an active set strategy and Proximal-ACCPM

In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant … Read more

Fortran subroutines for network flow optimization using an interior point algorithm

We describe FORTRAN subroutines for network flow optimization using an interior point network flow algorithm. We provide FORTRAN and C language drivers, as well as C language functions that, together with the subroutines, make up PDNET (Portugal, Resende, Veiga, and Júdice, 2000). The algorithm is described in detail and its implementation is outlined. Usage of … Read more

Extreme Point Solutions for Infinite Network Flow Problems

We study capacitated network flow problems with supplies and demands defined on a countably infinite collection of nodes having finite degree. This class of network flow models includes, for example, all infinite horizon deterministic dynamic programs with finite action sets since these are equivalent to the problem of finding a shortest infinite path in an … Read more

Selfish routing in the presence of side constraints

The natural approach for describing network flow problems is to introduce side constraints that capture restrictions of a logical or technological nature, e.g., capacity constraints. We study the traffic equilibria arising from selfish routing of individual users in networks with side constraints. We examine first the case of linear latency functions. Under very general assumptions … Read more

Quadratic interior-point methods in statistical disclosure control

The safe dissemination of statistical tabular data is one of the main concerns of National Statistical Institutes (NSIs). Although each cell of the tables is made up of the aggregated information of several individuals, the statistical confidentiality can be violated. NSIs must guarantee that no individual information can be derived from the released tables. One … Read more

Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more