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
  • Books
  • Articles  (8)
  • Data
  • linear programming  (8)
  • 1995-1999
  • 1985-1989  (8)
  • 1950-1954
  • 1988  (8)
  • Mathematics  (8)
  • 1
    Electronic Resource
    Electronic Resource
    Parametric linear programming and anti-cycling pivoting rules (1988)
    Springer
    Mathematical programming 41 (1988), S. 317-325 
    Details
    ISSN: 1436-4646
    Keywords: Parametric methods ; linear programming ; anti-cycling pivoting rules
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The traditional perturbation (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore, restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anticycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580770
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Survey of solved and open problems in the degeneracy phenomenon (1988)
    Springer
    Mathematical programming 42 (1988), S. 125-133 
    Details
    ISSN: 1436-4646
    Keywords: Cycling ; degeneracy ; graph theory ; linear programming ; sensitivity analysis ; simplex method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589397
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Layering strategies for creating exploitable structure in linear and integer programs (1988)
    Springer
    Mathematical programming 40 (1988), S. 165-181 
    Details
    ISSN: 1436-4646
    Keywords: Relaxation ; network ; integer programming ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The strategy of subdividing optimization problems into layers by splitting variables into multiple copies has proved useful as a method for inducing exploitable structure in a variety of applications, particularly those involving embedded pure and generalized networks. A framework is proposed in this paper which leads to new relaxation and restriction methods for linear and integer programming based on our extension of this strategy. This framework underscores the use of constructions that lead to stronger relaxations and more flexible strategies than previous applications. Our results establish the equivalence of all layered Lagrangeans formed by parameterizing the equal value requirement of copied variables for different choices of the principal layers. It is further shown that these Lagrangeans dominate traditional Lagrangeans based on incorporating non-principal layers into the objective function. In addition a means for exploiting the layered Lagrangeans is provided by generating subgradients based on a simple averaging calculation. Finally, we show how this new layering strategy can be augmented by an integrated relaxation/restriction procedure, and indicate variations that can be employed to particular advantage in a parallel processing environment. Preliminary computational results on fifteen real world zero-one personnel assignment problems, comparing two layering approaches with five procedures previously found best for those problems, are encouraging. One of the layering strategies tested dominated all non-layering procedures in terms of both quality and solution time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580728
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs (1988)
    Springer
    Annals of operations research 14 (1988), S. 41-59 
    Details
    ISSN: 1572-9338
    Keywords: Parallel algorithms ; SOR ; gradient projection ; linear programming ; linear complementarity problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02186473
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Parallel computing in combinatorial optimization (1988)
    Springer
    Annals of operations research 14 (1988), S. 245-289 
    Details
    ISSN: 1572-9338
    Keywords: 90C27 ; 68Q15 ; 68Q25 ; 68Rxx ; Parallel computer ; computational complexity ; polylog parallel algorithm ; P-completeness ; sorting ; shortest paths ; minimum spanning tree ; matching ; maximum flow ; linear programming ; knapsack ; scheduling ; traveling salesman ; dynamic programming ; branch and bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02186483
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    On greedy algorithms for series parallel graphs (1988)
    Springer
    Mathematical programming 40 (1988), S. 197-204 
    Details
    ISSN: 1436-4646
    Keywords: Greedy algorithms ; series parallel graphs ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel graph to be found by a greedy algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580730
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value (1988)
    Springer
    Mathematical programming 40 (1988), S. 183-195 
    Details
    ISSN: 1436-4646
    Keywords: Karmarkar's method ; linear programming ; inexact projections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez *. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz * using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580729
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    A dual approach to primal degeneracy (1988)
    Springer
    Mathematical programming 42 (1988), S. 135-145 
    Details
    ISSN: 1436-4646
    Keywords: Degeneracy ; dual infeasibility ; linear programming ; primal degeneracy ; simplex algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach. The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589398
    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...