Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Optimization  (2)
  • Network programming  (1)
  • Out-of-Kilter  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Auction algorithms for network flow problems: A tutorial introduction (1992)
    Springer
    Computational optimization and applications 1 (1992), S. 7-66 
    Details
    ISSN: 1573-2894
    Keywords: Network programming ; auction ; assignment ; transportation ; shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00247653
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Parallel primal-dual methods for the minimum cost flow problem (1993)
    Springer
    Computational optimization and applications 2 (1993), S. 317-336 
    Details
    ISSN: 1573-2894
    Keywords: Optimization ; network programming ; primal-dual ; transshipment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we discuss the parallel asynchronous implementation of the classical primaldual method for solving the linear minimum cost network flow problem. Multiple augmentations and price rises are simultaneously attempted starting from several nodes with possibly outdated price and flow information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show that this algorithm is valid, terminating finitely to an optimal solution. We also present computational results using an Encore MULTIMAX that illustrate the speedup that can be obtained by parallel implementation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01299544
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A generic auction algorithm for the minimum cost network flow problem (1993)
    Springer
    Computational optimization and applications 2 (1993), S. 229-259 
    Details
    ISSN: 1573-2894
    Keywords: Optimization ; network programming ; auction ; transportation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01299450
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A unified framework for primal-dual methods in minimum cost network flow problems (1985)
    Springer
    Mathematical programming 32 (1985), S. 125-145 
    Details
    ISSN: 1436-4646
    Keywords: Primal-Dual ; Out-of-Kilter ; Relaxation ; Network Flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. The algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586087
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...