An auction algorithm for the max-flow problem

We propose a new algorithm for the max-flow problem. It consists of a sequence of augmentations along paths constructed by an auction-like algorithm. These paths are not necessarily shortest, that is, they need not contain a minimum number of arcs. However, they can be found typically with much less computation than the shortest augmenting paths used by competing methods. Our algorithm outperforms these latter methods as well as state-of-the-art preflow-push algorithms by a very large margin in tests with standard randomly generated problems.This paper is a substantially revised version of Ref. 1.Many thanks are due to David Castanon and Paul Tseng for several helpful comments. The suggestions of the referees were also appreciated. David Castanon, Lakis Polymenakos, and Won-Jong Kim helped with some of the computational experimentation. This research was supported by NSF under Grant CCR-9103804.     

The auction algorithm: A distributed relaxation method for the assignment problem

We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi — like relaxation method for solving a dual problem. Its (sequential) worst — case complexity, for a particular implementation that uses scaling, is O(NAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.Work supported by Grant NSF-ECS-8217668. Thanks are due to J. Kennington and L. Hatay of Southern Methodist Univ. for contributing some of their computational experience.     

A strongly polynomial algorithm for the transportation problem

For the (linear) transportation problem withm supply nodes,n demand nodes andk feasible arcs we describe an algorithm which runs in time proportional tom logm(k + n logn) (assuming w.l.o.g.mn). The algorithm uses excess scaling. The complexity bound is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.Corresponding author. Research supported in part by grant no. I-84-095.06/88 of the German—Israeli-Foundation for Scientific Research and Development.     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path problem.     

A vertex ranking algorithm for the fixed-charge transportation problem

The singular perturbation method is used in dynamic programming to reduce the order and the computational requirements of linear systems composed of slow and fast modes. After the fast modes are separated, a near-optimum solution is computed at two different iteration rates determined by the slow and fast subsystem dynamics. The result is a reduction in the order of the computational requirement of the given system to that of the slow subsystem.Dr. Krikorian was the recipient of a Hughes Doctoral Fellowship during this research.     

A simple algorithm for the source-induced fixed-charge transportation problem

The fixed-charge problem is a non-linear programming problem of practical interest in business and industry. The source-induced fixed-charge transportation problem (SIFCTP) is a variation of the regular fixed-charge transportation problem (FCTP) in which a fixed cost is incurred for every supply point that is used in the solution, along with a variable cost that is proportional to the amount shipped. This problem is significantly different from the widely studied FCTP, where a fixed cost is incurred upon activation of a route. The introduction of the fixed costs in addition to variable costs results in the objective function being a step function. Therefore, fixed-charge problems are usually solved using sophisticated analytical or computer software. This paper deviates from that approach. It presents a computationally simple algorithm for the solution of source-induced fixed-charge problems. The results of empirical tests of the effectiveness of the proposed algorithm are presented.     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

The tridiagonal transportation problem

The Tridiagonal Transportation Problem deals with shipments of goods from n origins to n destination aalong 3n - 2 routes that correspond to the diagonal and off diagonal cells. This paper presents an equivalent Linear Programming Problem with only 2n - 1 decision variables. A greedy algorithm is developed by making simple changes to the right hand side of the L.P. Several extensions are also discussed.     

A modified active set algorithm for transportation discrete network design bi-level problem

Transportation discrete network design problem (DNDP) is about how to modify an existing network of roads and highways in order to improve its total system travel time, and the candidate road building or expansion plan can only be added as a whole. DNDP can be formulated into a bi-level problem with binary variables. An active set algorithm has been proposed to solve the bi-level discrete network design problem, while it made an assumption that the capacity increase and construction cost of each road are based on the number of lanes. This paper considers a more general case when the capacity increase and construction cost are specified for each candidate plan. This paper also uses numerical methods instead of solvers to solve each step, so it provides a more direct understanding and control of the algorithm and running procedure. By analyzing the differences and getting corresponding solving methods, a modified active set algorithm is proposed in the paper. In the implementation of the algorithm and the validation, we use binary numeral system and ternary numeral system to avoid too many layers of loop and save storage space. Numerical experiments show the correctness and efficiency of the proposed modified active set algorithm.     

A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources

We investigate a special case of the bottleneck transportation problem where the number s of sources is bounded by a constant and not part of the input. For the subcase s=2, a best-possible linear-time algorithm has been derived by Varadarajan [Oper. Res. Lett. 10 (1991) 525–529]. In this note we show that for any fixed number s⩾1, the bottleneck transportation problem with s sources can be solved in linear-time. The algorithm is conceptually simple, and easy to implement.     

Cost operator algorithms for the transportation problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.     

A transportation problem formulation for the MAC Airlift Planning problem

The Military Airlift Command (MAC) is responsible for planning the allocation of airlift resources for the movement of cargo and passengers. A heuristic algorithm, the Airlift Planning Algorithm (APA), has recently been developed under subcontract to the Oak Ridge National Laboratory to assist MAC in scheduling airlift resources. In this paper, we present a transportation problem formulation which can be used as a preprocessor to the APA or as an estimator for the APA. This paper examines the robustness and sensitivity of the transportation problem formulation. In particular, the performance of the APA improves by approximately 10% when the transportation problem is used as a preprocessor for two hypothetical problems and improves by up to 50% for derived airlift constrained problems.     

The generalized alternating path algorithm for transportation problems

A new primal extreme point algorithm for solving capacitated transportation problems is developed in this paper. This algorithm, called the generalized alternating path (GAP) algorithm, is a special purpose method specifically designed to take advantage of the often pervasive primal degeneracy of transportation problems.     

On the decentralized transportation problem

The decentralized transportation problem is under study where the customers act individually maximizing their own profits while the producer determines only the sequence of their service. The problem is shown to be NP-hard, and some effective approximation algorithm is suggested with a guaranteed approximation bound in the case of the same demand volumes.     

Interactive solutions for the linear multiobjective transportation problem

Mathematical programming problems that exhibit the mathematical structure of a transportation problem often arise in settings with multiple conflicting objectives. Existing procedures for analyzing these problems fall into two general categories. These methods either generate all nondominated solutions or they construct a single compromise solution. This paper presents two interactive algorithms which take advantage of the special form of the multiple objective transportation problem. Two examples are included to illustrate these algorithms and to demonstrate their viability.     

The savings algorithm for the vehicle routing problem

Survey is given concerning the savings method for the vehicle routing problem. Results for several methods and data sets are compared. Furthermore, modifications of the savings method are presented which show less CPU time and reduced storage requirements. Therefore, the savings method can be implemented on microcomputers.     

The value function of a transportation problem

We investigate the value of an optimal transportation problem with the maximization objective as a function of costs and vectors of production and consumption. The value is concave in production. For generic costs, the numbers of linearity domains and peak points are independent of costs and consumption. The peak points are determined by an auxiliary assignment problem. The volumes of the linearity domains are independent of costs while their dependence on consumption can be expressed via the multinomial distribution.     

The stochastic transportation problem with single sourcing

We propose a branch-and-price algorithm for solving a class of stochastic transportation problems with single-sourcing constraints. Our approach allows for general demand distributions, nonlinear cost structures, and capacity expansion opportunities. The pricing problem is a knapsack problem with variable item sizes and concave costs that is interesting in its own right. We perform an extensive set of computational experiments illustrating the efficacy of our approach. In addition, we study the cost of the single-sourcing constraints.