Search

We present a subgradient algorithm for minimizing the maximum of a finite collection of functions. It is assumed that each function is the sum of a finite collection of basic convex functions and that the number of different subgradient sets associated with nondifferentiable points of each basic function is finite on any bounded set. Problems belonging to this class include the linear approximation problem and both the minimax and minisum problems of location theory. Convergence of the algorithm to an epsilon-optimal solution is proven and its effectiveness is demonstrated by solving a number of location problems and linear approximation problems.

Simplicial decomposition is an important form of decomposition for large non-linear programming problems with linear constraints. Von Hohenbalken has shown that if the number of retained extreme points is n + 1, where n is the number of variables in the problem, the method will reach an optimal simplex after a finite number of master problems have been solved (i.e., after a finite number of major cycles). However, on many practical problems it is infeasible to allocate computer memory for n + 1 extreme points. In this paper, we present a version of simplicial decomposition where the number of retained extreme points is restricted to r, 1 =< r =< n + 1, and prove that if r is sufficiently large, an optimal simplex will be reached in a finite number of major cycles. This result insures rapid convergence when r is properly chosen and the decomposition is implemented using a second order method to solve the master problem.

In two recent papers published in Transportation Research , Daganzo presented a modification of the Frank-Wolfe algorithm to solve certain link capacitated traffic assignment problems satisfying certain conditions. In order to show convergence of the modified algorithm, the assumption was made that the integral of the volume delay formula for each link tends to infinity as the link flow approaches the link capacity. In this paper we give a Theorem which establishes convergence of the modified algorithm under much weaker conditions. This result is then used to show convergence if the objective function of the assignment model is sufficiently large (not necessarily infinite) when the link flows are at capacity. Thus the modified method is applicable to a broader class of assignment problems. Two numerical examples illustrate (a) when the method converges and when it does not, and (b) that our Theorem provides a weaker condition for convergence of the method.

This paper presents a convergent simplicial decomposition algorithm for the variational inequality formulation of the asymmetric traffic assignment problem. It alternates between generating minimum path trees based on the cost function evaluated at the current iterate and the approximate solving of a master variational inequality subject to simple convexity constraints. Thus it generalizes the popular Frank-Wolfe method (where the master problem is a line search) to the asymmetric problem. Rules are given for dropping flow patterns which are not needed to express the current iterate as a convex combination of previous patterns. The results of some computational testing are reported.

The minimum covering sphere problem, with applications in location theory, is that of finding the sphere of smallest radius which encloses a set of points in En. For a finite set of points, it is shown that the Wolfe dual is equivalent to a particular quadratic programming problem and that converse duality holds. A finite decomposition algorithm, based on the Simplex method of quadratic programming, is developed for which computer storage requirements are independent of the number of points and computing time is approximately linear in the number of points.

In a recent edition of this journal, Wesolowsky (Trans. Sci. 6, 103–113) presents a formulation of a multifoxility minimax location problem for rectilinear distances as a parametric linear program. It is shown here that a modification of Wesolowsky's approach will result in a nonparametric linear program, and further, that a different approach to the problem will yield a simpler formulation as a smaller linear program.

Four closely related minimax location problems are considered. Each involves locating a point in the plane to minimize the maximum distance (plus a possible constant) to a given finite set of points. The distance measures considered are the Euclidean and the rectilinear. In each case efficient, finite solution procedures are given. The arguments are geometrical.

We report the first numerical simulation of the relative resistance noise in percolating networks of dimensions higher than two. The results confirm the scaling estimates of the corresponding noise exponents up to six dimensions. Since hypercontinuum systems with unit resistors are used, this confirmation indicates the universality of the derived exponents.

In prior work we have given an intuitive development of Transfer Decomposition, a decomposition of the traffic assignment problem into two traffic assignment problems. The intent of this paper is to provide a rigorous basis for this technique by establishing that it is a generalized Benders decomposition. As an illustration of the result, we give a decomposition algorithm that is based on the familiar Frank-Wolfe method. This research was supported in part by the National Science Foundation under Grant CEE-8420830.

Restricted simplicial decomposition (RSD) is a very useful technique for certain large-scale pseudoconvex programming problems such as the traffic assignment problem and other network flow problems. The “restricted” version of this method allows the user to treat the maximum size of the generated simplices as a parameter. When the parameter is at its minimum value, the method reduces to the Frank-Wolfe algorithm; when at its maximum, the original simplicial decomposition of von Hohenbalken and Holloway results. Computer storage requirements increase linearly with the parameter, but our computational experiments on a variety of test problems show that there is a payoff in improved progress of the method as measured by the relative error in the objective function. Included in the tests are a number of real-world traffic networks, some large electrical networks, a water distribution network, and linearly constrained problems of the Colville study.

We present an implementable feasible direction subgradient algorithm for minimizing the maximum of a finite collection of functions subject to constraints. It is assumed that each function involved in defining the objective function is the sum of a finite collection of basic convex functions and that the number of different subgradient sets associated with nondifferentiable points of each basic function is finite on any bounded set. It is demonstrated that under certain conditions, including continuous differentiability of the constraints and a regularity condition of the µ feasible region, that the algorithm generates a feasible sequence which converges to an ?-optimal solution. Computational results for some example problems are included.

The properties were studied of the direction formed by taking the difference of two successive dual iterates of generalized linear programming (GLP), and pointed out that this direction is also solution to an associated direction finding problem. This study shows that this direction finding problem belongs to a new class of direction finding problems and propose a modification of GLP in which its original direction finding problems is replaced by another in this new class. This new direction finding problem is similar to the one used by Demyanov for minimax problems and guarantees an ascent direction for the dual function. Finally, we state and prove the convergence for the modified GLP. Keywords: Linear programming; Decomposition; Lagrangian dual; Subgradient.

This paper describes recently developed nonlinear programming algorithms for certain large-scale congested network models. The techniques include Restricted Simplicial Decomposition (RSD) applied to the single commodity flow problem (RSDNET) and the standard traffic assignment problem (RSDTA), and the basic simplicial strategy applied to the network variational inequality problem (SDVI). Computational results are presented for each method, including tests conducted on large networks from real world models.