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
  • 1
    Electronic Resource
    Electronic Resource
    Dual coordinate step methods for linear network flow problems (1988)
    Springer
    Mathematical programming 42 (1988), S. 203-243 
    Details
    ISSN: 1436-4646
    Keywords: Network flows ; relaxation ; distributed algorithms ; complexity ; asynchronous algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion ofε-complementary slackness, and most do not explicitly manipulate any “global” objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of newserial computational complexity results. We develop the basic theory of these methods and present two specific methods, theε-relaxation algorithm for the minimum-cost flow problem, and theauction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N 3 logNC) and O(NA logNC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implementε-relaxation in a completely asynchronous, “chaotic” environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589405
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators (1992)
    Springer
    Mathematical programming 55 (1992), S. 293-318 
    Details
    ISSN: 1436-4646
    Keywords: Monotone operators ; proximal point algorithm ; decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper shows, by means of an operator called asplitting operator, that the Douglas—Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm. Therefore, applications of Douglas—Rachford splitting, such as the alternating direction method of multipliers for convex programming decomposition, are also special cases of the proximal point algorithm. This observation allows the unification and generalization of a variety of convex programming algorithms. By introducing a modified version of the proximal point algorithm, we derive a new,generalized alternating direction method of multipliers for convex programming. Advances of this sort illustrate the power and generality gained by adopting monotone operator theory as a conceptual framework.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581204
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Smooth methods of multipliers for complementarity problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 65-90 
    Details
    ISSN: 1436-4646
    Keywords: Key words: complementarity problems – smoothing – proximal algorithms – augmented Lagrangians
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows that this class of algorithms is effective at solving many of the standard complementarity test problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101079900076
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5 (1997)
    Springer
    Computational optimization and applications 7 (1997), S. 199-220 
    Details
    ISSN: 1573-2894
    Keywords: parallel computing ; mixed integer programming ; branch and bound methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes parallel, non-shared-memoryimplementation of the classical general mixed integer branch and boundalgorithm, with experiments on the CM-5 family of parallel processors. Themain issue in such an implementation is whether task scheduling and certaindata-storage functions should be handled by a single processor, orspread among multiple processors. The centralized approach riskscreating processing bottlenecks, while the more decentralizedimplementations differ more from the fundamental serial algorithm.Extensive computational tests on standard MIPLIB problems comparecentralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-basedglobal load balancing, along with a distributed “control by token”technique. Further experiments compare centralized and distributedschemes for storing heuristic “pseudo-cost” branching data. The distributed storage method is based on continual asynchronous reductionalong a tree of redundant storage sites. On average, decentralized taskscheduling appears at least as effective as central control, butpseudo-cost storage should be kept as centralized as possible.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008699010646
    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...