Results 211 to 220 of about 8,257 (239)
Some of the next articles are maybe not open access.
The simplex algorithm for multicommodity networks
Networks, 2001AbstractWe consider multicommodity network flow problems, where external flow is allowed to vary and where flows of individual commodities may be constrained. For this problem, we describe the simplex algorithm. The simplex algorithm is based upon the inverse of the basis matrix. We discuss an approach where we only have to invert a working matrix with
Detlefsen, Nina, Wallace, Stein W
openaire +3 more sources
A continuous‐time network simplex algorithm
Networks, 1989AbstractGiven a network having costs and upper bound constraints on the flows in its arcs, the minimum‐cost network flow problem is that of finding flows which satisfy a flow‐conservation constraint at each node and minimize the total cost of the flow. If the arc capacities vary as functions of time, and storage is permitted at the nodes of the network,
Edward J. Anderson, Andrew B. Philpott
openaire +2 more sources
A Strongly Convergent Primal Simplex Algorithm for Generalized Networks
Mathematics of Operations Research, 1979A major computational problem that arises in the attempt to solve generalized network and network-related problems is degeneracy. In fact, using primal simplex solution techniques, the number of degenerate pivots performed frequently ranges as high as 90% in large-scale applications.
Joyce J. Elam +2 more
openaire +2 more sources
Parallel network simplex algorithm for the minimum cost flow problem
Concurrency and Computation: Practice and Experience, 2021AbstractIn this work, we contribute a parallel implementation of the network simplex algorithm that is used for the solution of minimum cost flow problem. In the network simplex algorithm, finding an entering arc requires searching through many arcs to decide which one should be included in the spanning tree solution on the next iteration.
Gökçehan Kara, Can C. Özturan
openaire +1 more source
A simplex algorithm for minimum‐cost network‐flow problems in infinite networks
Networks, 2008AbstractWe study minimum‐cost network‐flow problems in networks with a countably infinite number of nodes and arcs and integral flow data. This problem class contains many nonstationary planning problems over time where no natural finite planning horizon exists. We use an intuitive natural dual problem and show that weak and strong duality hold.
Thomas C. Sharkey, H. Edwin Romeijn
openaire +2 more sources
Implementing an LU Factorization for the Embedded Network Simplex Algorithm
INFORMS Journal on Computing, 2004This paper presents an LU factorization specialized for embedded network simplex algorithms. Specializing the LU factorization in this fashion poses a challenge as the embedded network algorithm uses a very compressed working basis inverse. Using publicly available test problems, we demonstrate the impact of this factorization on the EMNET ...
Richard D. McBride, John W. Mamer
openaire +1 more source
Anti‐stalling pivot rules for the network simplex algorithm
Networks, 1990AbstractStalling in the simplex algorithm is defined as an exponentially long sequence of consecutive degenerate pivots without cycling. Pivot rules for the network simplex algorithm that prevent both cycling and stalling are considered. For several of these, the number of consecutive degenerate pivots is shown to be at most k (k + 1)/2, where k is the
Donald Goldfarb +2 more
openaire +1 more source
An efficient generalized network-simplex-based algorithm for manufacturing network flows
Journal of Combinatorial Optimization, 2007zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Prahalad Venkateshan +2 more
openaire +1 more source
2013
For practical applications, by far the most useful optimization algorithm for solving linear programs is the celebrated simplex algorithm. This suggests trying to apply this algorithm also to problems from graph theory. Indeed, the most important network optimization problems may be formulated in terms of linear programs; this holds, for instance, for ...
openaire +1 more source
For practical applications, by far the most useful optimization algorithm for solving linear programs is the celebrated simplex algorithm. This suggests trying to apply this algorithm also to problems from graph theory. Indeed, the most important network optimization problems may be formulated in terms of linear programs; this holds, for instance, for ...
openaire +1 more source
A Subtree-Partitioning Algorithm for Inducing Parallelism in Network Simplex Dual Updates
Computational Optimization and Applications, 1997zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Betty L. Hickman, Dan Scott
openaire +1 more source