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
    Relaxation methods for monotropic programs (1990)
    Springer
    Mathematical programming 46 (1990), S. 127-151 
    Details
    ISSN: 1436-4646
    Keywords: Dual descent ; monotropic program ; Tucker tableau ; elementary vector
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a dual descent method for the problem of minimizing a convex, possibly nondifferentiable, separable cost subject to linear constraints. The method has properties reminiscent of the Gauss-Seidel method in numerical analysis and uses theε-complementary slackness mechanism introduced in Bertsekas, Hosein and Tseng (1987) to ensure finite convergence to near optimality. As special cases we obtain the methods in Bertsekas, Hosein and Tseng (1987) for network flow programs and the methods in Tseng and Bertsekas (1987) for linear programs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585734
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On the convergence of the exponential multiplier method for convex programming (1993)
    Springer
    Mathematical programming 60 (1993), S. 1-19 
    Details
    ISSN: 1436-4646
    Keywords: Convex programming ; linear programming ; multiplier method ; exponential penalty ; Augmented Lagrangian
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy “proximal” term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580598
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Necessary and sufficient conditions for a penalty method to be exact (1975)
    Springer
    Mathematical programming 9 (1975), S. 87-99 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper identifies necessary and sufficient conditions for a penalty method to yield an optimal solution or a Lagrange multiplier of a convex programming problem by means of a single unconstrained minimization. The conditions are given in terms of properties of the objective and constraint functions of the problem as well as the penalty function adopted. It is shown among other things that all linear programs with finite optimal value satisfy such conditions when the penalty function is quadratic.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01681332
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A new algorithm for the assignment problem (1981)
    Springer
    Mathematical programming 21 (1981), S. 152-171 
    Details
    ISSN: 1436-4646
    Keywords: Assignment Problems ; Network Flows ; Hungarian Method ; Computational Complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a new algorithm for the classical assignment problem. The algorithm resembles in some ways the Hungarian method but differs substantially in other respects. The average computational complexity of an efficient implementation of the algorithm seems to be considerably better than the one of the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. The factor of improvement increases with the problem dimensionN and reaches an order of magnitude forN equal to several hundreds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584237
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    The relax codes for linear minimum cost network flow problems (1988)
    Springer
    Annals of operations research 13 (1988), S. 125-190 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We describe a relaxation algorithm [1,2] for solving the classical minimum cost network flow problem. Our implementation is compared with mature state-of-the-art primal simplex and primal-dual codes and is found to be several times faster on all types of randomly generated network flow problems. Furthermore, the speed-up factor increases with problem dimension. The codes, called RELAX-II and RELAXT-II, have a facility for efficient reoptimization and sensitivity analysis, and are in the public domain.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02288322
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    The auction algorithm for the transportation problem (1989)
    Springer
    Annals of operations research 20 (1989), S. 67-96 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02216923
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Rollout Algorithms for Stochastic Scheduling Problems (1999)
    Springer
    Journal of heuristics 5 (1999), S. 89-108 
    Details
    ISSN: 1572-9397
    Keywords: rollout algorithms ; scheduling ; neuro-dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009634810396
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Rollout Algorithms for Combinatorial Optimization (1997)
    Springer
    Journal of heuristics 3 (1997), S. 245-262 
    Details
    ISSN: 1572-9397
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential application. In particular, we embed the problem within a dynamic programming framework, and we introduce several types of rollout algorithms, which are related to notions of policy iteration. We provide conditions guaranteeing that the rollout algorithm improves the performance of the original heuristic algorithm. The method is illustrated in the context of a machine maintenance and repair problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009635226865
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    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...