ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
  • Articles  (19)
  • Linear Programming  (19)
  • 2005-2009
  • 1980-1984  (19)
  • Mathematics  (19)
Collection
  • Articles  (19)
Source
Keywords
Publisher
Years
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    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
    Keywords: Linear Programming ; Relaxation Method ; Polynomiality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581028
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Polynomial algorithms for a class of linear programs (1981)
    Springer
    Mathematical programming 21 (1981), S. 121-136 
    Details
    ISSN: 1436-4646
    Keywords: Linear Programming ; Polynomial Algorithms ; Total Unimodularity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes several algorithms for solution of linear programs. The algorithms are polynomial when the problem data satisfy certain conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584235
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    An algorithm for computing equilibria in a linear monetary economy (1981)
    Springer
    Mathematical programming 21 (1981), S. 182-189 
    Details
    ISSN: 1436-4646
    Keywords: Equilibrium ; Linear Monetary Economy ; Linear Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is presented for computing equilibria in a linear monetary economy, that is, an exchange economy in which all individuals have linear utility functions and in which goods are bought and sold only in exchange for money. The algorithm computes the equilibrium prices by solving a finite sequence of linear programming problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584239
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Optimum matching forests II: General weights (1982)
    Springer
    Mathematical programming 22 (1982), S. 12-38 
    Details
    ISSN: 1436-4646
    Keywords: Graph ; Matching ; Branching ; Linear Programming ; Polyhedron
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581023
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    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
    Keywords: Polytopes ; Linear Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588326
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Optimality in transient markov chains and linear programming (1980)
    Springer
    Mathematical programming 18 (1980), S. 1-6 
    Details
    ISSN: 1436-4646
    Keywords: Discrete Dynamic Programming ; Optimal Markov Chains ; Linear Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588291
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Modifications and implementation of the ellipsoid algorithm for linear programming (1982)
    Springer
    Mathematical programming 23 (1982), S. 1-19 
    Details
    ISSN: 1436-4646
    Keywords: Ellipsoid Algorithm ; Linear Programming ; Polynomial Boundedness ; Khachian's Method ; Linear Inequalities
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583776
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Optimum matching forests I: Special weights (1982)
    Springer
    Mathematical programming 22 (1982), S. 1-11 
    Details
    ISSN: 1436-4646
    Keywords: Graph ; Matching ; Branching ; Linear Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581022
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    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
    Keywords: Linear Programming ; Variable Upper Bounds ; Degeneracy ; Triangular Factorization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583778
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Solving staircase linear programs by the simplex method, 1: Inversion (1982)
    Springer
    Mathematical programming 23 (1982), S. 274-313 
    Details
    ISSN: 1436-4646
    Keywords: Large-Scale Optimization ; Linear Programming ; Staircase Linear Programs ; Simplex Method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583795
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    On degeneracy in enumeration (1983)
    Springer
    BIT 23 (1983), S. 267-270 
    Details
    ISSN: 1572-9125
    Keywords: Linear Programming ; Enumeration ; Degeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In the case of degeneracy in an LP-formulation, there is not a one-to-one correspondence between extreme points and feasible bases. If the task is to find thek best extreme points in the set of feasible solutions to an LP, this lack of correspondence has a certain importance, since methods based on the Simplex Algorithm are oriented towards feasible bases instead of the relevant extreme points. We therefore present an easily implementable method to avoid this problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02218448
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    A bump triangular dynamic factorization algorithm for the simplex method (1980)
    Springer
    Mathematical programming 18 (1980), S. 49-61 
    Details
    ISSN: 1436-4646
    Keywords: Linear Programming ; Simplex Method ; Large-scale Programming ; Sparse Matrices ; Triangular Factorization of the Basis ; Partitioning Methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588296
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Random polytopes: Their definition, generation and aggregate properties (1982)
    Springer
    Mathematical programming 24 (1982), S. 39-54 
    Details
    ISSN: 1436-4646
    Keywords: Random Polytopes ; Linear Programming ; Problem Generation ; Aggregate Polytope Properties
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585093
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    A degeneracy exploiting LU factorization for the simplex method (1980)
    Springer
    Mathematical programming 19 (1980), S. 239-254 
    Details
    ISSN: 1436-4646
    Keywords: Linear Programming ; LU Factorization ; Degeneracy ; Bartels—Golub Updating
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581646
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    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
    Keywords: Stochastic Programming ; Linear Programming ; Expected Value of Perfect Information
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585113
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    Optimal scaling of balls and polyhedra (1982)
    Springer
    Mathematical programming 23 (1982), S. 138-147 
    Details
    ISSN: 1436-4646
    Keywords: Linear Programming ; Quadratic Programming ; Optimal Scaling ; Cells ; Balls ; Polyhedral ; Meet ; Containment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583784
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    Dynamically restricted pricing in the simplex method for linear programming (1982)
    Springer
    Mathematical programming 23 (1982), S. 314-325 
    Details
    ISSN: 1436-4646
    Keywords: Sampling Techniques ; Linear Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01583796
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    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
    Keywords: Linear Programming ; Sparse LU Decomposition ; Updating Ip Basis Factorizations ; Bartels—Golub Decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585094
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Polyhedral extensions of some theorems of linear programming (1982)
    Springer
    Mathematical programming 24 (1982), S. 162-176 
    Details
    ISSN: 1436-4646
    Keywords: Polyhedral Convexity ; Tucker's Theorem ; Williams' Theorems ; Monotone Complementarity Problem ; Complementary Unboundedness ; Linear Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585102
    Location Call Number Expected 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...