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  (12)
  • Linear Programming  (12)
  • Springer  (12)
  • American Chemical Society (ACS)
  • 1980-1984  (12)
  • 1982  (12)
  • Computer Science  (12)
Collection
  • Articles  (12)
Source
Keywords
Publisher
  • Springer  (12)
  • American Chemical Society (ACS)
Years
  • 1980-1984  (12)
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
    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
  • 3
    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
  • 4
    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
  • 5
    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
  • 6
    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
  • 7
    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
  • 8
    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
  • 9
    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
  • 10
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...