ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • Artikel  (16)
  • Linear Programming  (16)
  • Springer  (16)
  • Blackwell Publishing Ltd
  • Elsevier
  • Periodicals Archive Online (PAO)
  • Wiley
  • 2005-2009
  • 1990-1994
  • 1980-1984  (16)
  • 2008
  • 2007
  • 2005
  • 1982  (12)
  • 1980  (4)
  • Mathematik  (16)
  • Philosophie
  • Werkstoffwissenschaften, Fertigungsverfahren, Fertigung
Sammlung
  • Artikel  (16)
Datenquelle
Schlagwörter
Verlag/Herausgeber
  • Springer  (16)
  • Blackwell Publishing Ltd
  • Elsevier
  • Periodicals Archive Online (PAO)
  • Wiley
Erscheinungszeitraum
  • 2005-2009
  • 1990-1994
  • 1980-1984  (16)
Jahr
Thema
  • Mathematik  (16)
  • Philosophie
  • Werkstoffwissenschaften, Fertigungsverfahren, Fertigung
  • Informatik  (16)
  • 1
    Digitale Medien
    Digitale Medien
    On the non-polynomiality of the relaxation method for systems of linear inequalities (1982)
    Springer
    Mathematical programming 22 (1982), S. 93-103 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Programming ; Relaxation Method ; Polynomiality
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A class of linear programs is given in which the relaxation method for inequalities, under the same operating rules as Khacian's method, is not polynomial in the length of the input. This result holds for any value of the relaxation parameter.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581028
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Optimum matching forests II: General weights (1982)
    Springer
    Mathematical programming 22 (1982), S. 12-38 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Graph ; Matching ; Branching ; Linear Programming ; Polyhedron
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Matching forests generalize branchings in a directed graph and matchings in an undirected graph. We present an efficient algorithm, the PMF Algorithm, for the problem: given a mixed graphG and a real weight on each of its edges, find a perfect matching forest of maximum weight-sum. The PMF Algorithm proves the sufficiency of a linear system which definesP = (G) andP(G), the convex hull of incidence vectors of perfect matching forests and matching forests respectively ofG. The algorithm also provides a generalization of Tutte's theorem on the existence of perfect matchings in an undirected graph.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581023
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    Computational results on an algorithm for finding all vertices of a polytope (1980)
    Springer
    Mathematical programming 18 (1980), S. 308-329 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Polytopes ; Linear Programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper provides answers to several questions raised by V. Klee regarding the efficacy of Mattheiss' algorithm for finding all vertices of convex polytopes. Several results relating to the expected properties of polytopes are given which indicate thatn-polytopes defined by “large” numbers of constraints are difficult to obtain by random processes, the expected value of the number of vertices of polytope is considerably less than Klee's least upper bound the expected performance of Mattheiss' algorithm is far better than Klee's upper bound would suggest.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01588326
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Optimality in transient markov chains and linear programming (1980)
    Springer
    Mathematical programming 18 (1980), S. 1-6 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Discrete Dynamic Programming ; Optimal Markov Chains ; Linear Programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01588291
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    Modifications and implementation of the ellipsoid algorithm for linear programming (1982)
    Springer
    Mathematical programming 23 (1982), S. 1-19 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Ellipsoid Algorithm ; Linear Programming ; Polynomial Boundedness ; Khachian's Method ; Linear Inequalities
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01583776
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    Optimum matching forests I: Special weights (1982)
    Springer
    Mathematical programming 22 (1982), S. 1-11 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Graph ; Matching ; Branching ; Linear Programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We introduce the concept of matching forests as a generalization of branchings in a directed graph and matchings in an undirected graph. Given special weights on the edges of a mixed graph, we present an efficient algorithm for finding an optimum weight-sum matching forest. The algorithm is a careful application of known branching and matching algorithms. The maximum cardinality matching forest problem is solved as a special case.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581022
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    An implementation of the simplex method for linear programming problems with variable upper bounds (1982)
    Springer
    Mathematical programming 23 (1982), S. 34-49 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Programming ; Variable Upper Bounds ; Degeneracy ; Triangular Factorization
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Special methods for dealing with constraints of the formx j ≤ x k , called variable upper bounds, were introduced by Schrage. Here we describe a method that circumvents the massive degeneracy inherent in these constraints and show how it can be implemented using triangular basis factorizations.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01583778
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Digitale Medien
    Digitale Medien
    Solving staircase linear programs by the simplex method, 1: Inversion (1982)
    Springer
    Mathematical programming 23 (1982), S. 274-313 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Large-Scale Optimization ; Linear Programming ; Staircase Linear Programs ; Simplex Method
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The present paper looks at ‘inversion’ routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines ‘pricing’ routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01583795
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 9
    Digitale Medien
    Digitale Medien
    A bump triangular dynamic factorization algorithm for the simplex method (1980)
    Springer
    Mathematical programming 18 (1980), S. 49-61 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Programming ; Simplex Method ; Large-scale Programming ; Sparse Matrices ; Triangular Factorization of the Basis ; Partitioning Methods
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A dynamic factorization algorithm is developed which algebraically partitions the basis inverse in such a manner so that the simplex method can be executed from a series of small inverses and the basis itself. This partition is maintained dynamically so that the additional memory required to represent the basis inverse reduces to this series of small inverses for in-core implementations. The algorithm is intended for use in solving general large-scale linear programming problems. This new method of basis representation should permit rather large problems to be solved completely in-core. Preliminary computational experience is presented and comparisons are made with Reid's sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. The computational experience indicated that a significant reduction in memory requirements can usually be obtained using the dynamic factorization approach with only a slight (up to about 20%) degradation of execution time.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01588296
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 10
    Digitale Medien
    Digitale Medien
    Random polytopes: Their definition, generation and aggregate properties (1982)
    Springer
    Mathematical programming 24 (1982), S. 39-54 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Random Polytopes ; Linear Programming ; Problem Generation ; Aggregate Polytope Properties
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 n wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585093
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 11
    Digitale Medien
    Digitale Medien
    A degeneracy exploiting LU factorization for the simplex method (1980)
    Springer
    Mathematical programming 19 (1980), S. 239-254 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Programming ; LU Factorization ; Degeneracy ; Bartels—Golub Updating
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract For general sparse linear programs two of the most efficient implementations of the LU factorization with Bartels—Golub updating are due to Reid and Saunders. This paper presents an alternative approach which achieves fast execution times for degenerate simplex method iterations, especially when used with multiple pricing. The method should have wide applicability since the simplex method performs a high proportion of degenerate iterations on most practical problems. A key feature of Saunders' method is combined with the updating strategy of Reid so as to make the scheme suitable for implementation out of core. Its efficiency is confirmed by experimental results.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581646
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 12
    Digitale Medien
    Digitale Medien
    The value of the stochastic solution in stochastic linear programs with fixed recourse (1982)
    Springer
    Mathematical programming 24 (1982), S. 314-325 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Stochastic Programming ; Linear Programming ; Expected Value of Perfect Information
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585113
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 13
    Digitale Medien
    Digitale Medien
    Optimal scaling of balls and polyhedra (1982)
    Springer
    Mathematical programming 23 (1982), S. 138-147 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Programming ; Quadratic Programming ; Optimal Scaling ; Cells ; Balls ; Polyhedral ; Meet ; Containment
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract The concern is with solving as linear or convex quadratic programs special cases of the optimal containment and meet problems. The optimal containment or meet problem is that of finding the smallest scale of a set for which some translation contains a set or meets each element in a collection of sets, respectively. These sets are unions or intersections of cells where a cell is either a closed polyhedral convex set or a closed solid ball.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01583784
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 14
    Digitale Medien
    Digitale Medien
    Dynamically restricted pricing in the simplex method for linear programming (1982)
    Springer
    Mathematical programming 23 (1982), S. 314-325 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Sampling Techniques ; Linear Programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A modification of the conventional simplex method has been developed for use on linear programming problems with large numbers of columns. The basic concept underlying the method is the trade-off between the cost of calculating many reduced costs and the increase in number of iterations resulting from calculating very vew. Under suitable assumptions a cost function can be constructed. The optimal choice of the number of reduced costs can then be computed by means of Dynamic Programming. Several approximated solutions are developed which are computationally simpler. Experiments on a number of problems indicate that the method may offer a promising technique for large-scale problems.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01583796
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 15
    Digitale Medien
    Digitale Medien
    A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases (1982)
    Springer
    Mathematical programming 24 (1982), S. 55-69 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear Programming ; Sparse LU Decomposition ; Updating Ip Basis Factorizations ; Bartels—Golub Decomposition
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We describe a sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. It includes interchanges that, whenever this is possible, avoid the use of any eliminations (with consequent fill-ins) when revising the factorization at an iteration. Test results on some medium scale problems are presented and comparisons made with the algorithm of Forrest and Tomlin.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585094
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 16
    Digitale Medien
    Digitale Medien
    Polyhedral extensions of some theorems of linear programming (1982)
    Springer
    Mathematical programming 24 (1982), S. 162-176 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Polyhedral Convexity ; Tucker's Theorem ; Williams' Theorems ; Monotone Complementarity Problem ; Complementary Unboundedness ; Linear Programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Three theorems of linear programming form our starting point: Tucker's theorem (1956) concerning the existence of optimal solutions satisfying the complementary slackness conditions strictly, and Williams' two theorems (1970) concerning the coordinatewise complementary behavior of feasible and optimal solutions. Here, we establish that the same phenomena hold in another, more versatile framework involving general polyhedral convexity. As one main application, the results are transferred into the context of the monotone complementarity problem. Several other theoretical applications are indicated.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585102
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...