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
  • 1
    Electronic Resource
    Electronic Resource
    Pivoting in an Outcome Polyhedron (2000)
    Springer
    Journal of global optimization 16 (2000), S. 301-323 
    Details
    ISSN: 1573-2916
    Keywords: Outcome polyhedron ; Linear programming ; Pivoting ; Nonlinear programming ; Global optimization ; Extreme point mathematical programming ; Neighborhood problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In many types of linear, convex and nonconvex optimization problems over polyhedra, a global optimal solution can be found by searching the extreme points of the outcome polyhedron Y instead of the extreme points of the decision set polyhedron Z. Since the dimension of Y is often significantly smaller than the dimension of Z, and since the structure of Y is often much simpler than the structure of Z, such an approach has the potential to often yield significant computational savings. This article seeks to motivate these potential savings through both general theory and concrete examples. The article then develops two new procedures. The first procedure is linear-programming based and finds an initial extreme point of an outcome polyhedron Y. The second procedure provides a mechanism for moving from a given extreme point y of Y along any chosen edge of Y emanating from y until a neighboring extreme point to y is reached. As a by-product of the second procedure, as in the pivoting process of the simplex method, a complete algebraic description of the chosen edge can also be easily obtained.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008364005245
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    The Dual of a Logical Linear Programme (2000)
    Springer
    Journal of global optimization 18 (2000), S. 129-141 
    Details
    ISSN: 1573-2916
    Keywords: Logic ; Linear programming ; Boolean algebra ; Duality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A Linear Programme (LP) involves a conjunction of linear constraints and has a well defined dual. It is shown that if we allow the full set of Boolean connectives {∧, ∨, ∼} applied to a set of linear constraints we get a model which we define as a Logical Linear Programme (LLP). This also has a well defined dual preserving most of the properties of LP duality. Generalisations of the connectives are also considered together with the relationship with Integer Programming formulation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008328500933
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Partitioning mathematical programs for parallel solution (1998)
    Springer
    Mathematical programming 80 (1998), S. 35-61 
    Details
    ISSN: 1436-4646
    Keywords: Graph partitioning ; Linear programming ; Bundle method ; Parallel optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes heuristics for partitioning a generalM × N matrix into arrowhead form. Such heuristics are useful for decomposing large, constrained, optimization problems into forms that are amenable to parallel processing. The heuristics presented can be easily implemented using publicly available graph partitioning algorithms. The application of such techniques for solving large linear programs is described. Extensive computational results on the effectiveness of our partitioning procedures and their usefulness for parallel optimization are presented. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Minimizing average completion time in the presence of release dates (1998)
    Springer
    Mathematical programming 82 (1998), S. 199-223 
    Details
    ISSN: 1436-4646
    Keywords: Scheduling ; Preemptive scheduling ; Average weighted completion time ; Approximation algorithms ; Relaxations ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of schedulingn jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations in polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both. Many of the algorithms generalize to the minimization of averageweighted completion time as well. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585872
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming (1998)
    Springer
    Mathematical programming 81 (1998), S. 1-21 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Farkas lemma ; Infeasible-interior-point methods ; Stopping rules
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain “certificates” that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584841
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Balinski—Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces (1998)
    Springer
    Mathematical programming 81 (1998), S. 349-372 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Degeneracy ; Multiple solutions ; Optimal faces
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski—Tucker (B—T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B—T Simplex Tableau when a solution in the relative interior of the optimal face is known. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580088
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A modified layered-step interior-point algorithm for linear programming (1998)
    Springer
    Mathematical programming 82 (1998), S. 339-355 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Layered-step interior-point method ; Path of centers ; Crossover events
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrixA. The main drawback of the algorithm is the use of an unknown big constant $$\bar \chi _A $$ in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal—dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580074
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    An interior point method, based on rank-1 updates, for linear programming (1998)
    Springer
    Mathematical programming 81 (1998), S. 77-87 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Interior point method ; Potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd k andv k rather than a primal—dual interior point (x k ,s k ), where $$d_i^k = \sqrt {{{x_i^k } \mathord{\left/ {\vphantom {{x_i^k } {s_i^k }}} \right. \kern-\nulldelimiterspace} {s_i^k }}} $$ and $$v_i^k = \sqrt {x_i^k s_i^k }$$ fori = 1, 2,⋯,n. Only one element ofd k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx k ands k are not needed explicitly in the algorithm, whereasd k andv k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x k, sk) and (d k, vk) with improving primal—dual potential function values. Moreover, no approximation ofd k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584845
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Markov games with incomplete information (1997)
    Springer
    Mathematical methods of operations research 46 (1997), S. 263-279 
    Details
    ISSN: 1432-5217
    Keywords: Markov games with incomplete information ; Repeated games ; Optimal strategies ; Algorithms ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We consider zero-sum Markov games with incomplete information. Here, the second player is never informed about the current state of the underlying Markov chain. The existence of a value and of optimal strategies for both players is shown. In particular, we present finite algorithms for computing optimal strategies for the informed and uninformed player. The algorithms are based on linear programming results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01217695
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    A simplified homogeneous and self-dual linear programming algorithm and its implementation (1996)
    Springer
    Annals of operations research 62 (1996), S. 151-171 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; homogeneous and self-dual linear feasibility model ; predictor-corrector algorithm ; implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves $$O(\sqrt {nL} )$$ -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206815
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    An infeasible-interior-point algorithm using projections onto a convex set (1996)
    Springer
    Annals of operations research 62 (1996), S. 59-80 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; infeasible-interior-point method ; polynomiality ; projection ; 90C05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present a new class of primal-dual infeasible-interior-point methods for solving linear programs. Unlike other infeasible-interior-point algorithms, the iterates generated by our methods lie in general position in the positive orthant of ℝ2 and are not restricted to some linear manifold. Our methods comprise the following features: At each step, a projection is used to “recenter” the variables to the domainx i s i ≥μ. The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are seasy to implement. The use of orthogonal projections allows that a full Newton step can be taken at each iteration, even if the result violates the nonnegativity condition. We prove that a short step version of our method converges in polynomial time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206811
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    A relaxed primal-dual path-following algorithm for linear programming (1996)
    Springer
    Annals of operations research 62 (1996), S. 173-196 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; primal-dual method ; interior path-following algorithm ; relaxation method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206816
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption (1996)
    Springer
    Annals of operations research 62 (1996), S. 325-355 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; infeasible-interior-point methods ; affine scaling algorithm ; global convergence analysis ; nondegeneracy assumption ; AMS(MOS) 90C05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we propose an infeasible-interior-point algorithm for linear programning based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in [17] is also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206822
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    Large step volumetric potential reduction algorithms for linear programming (1996)
    Springer
    Annals of operations research 62 (1996), S. 521-538 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; interior algorithm ; potential reduction ; volumetric barrier
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We consider the construction of potential reduction algorithms using volumetric, and mixed volumetric — logarithmic, barriers. These are true “large step” methods, where dual updates produce constant-factor reductions in the primal-dual gap. Using a mixed volumetric — logarithmic barrier we obtain an $$O(\sqrt {nmL} )$$ iteration algorithm, improving on the best previously known complexity for a large step method. Our results complement those of Vaidya and Atkinson on small step volumetric, and mixed volumetric — logarithmic, barrier function algorithms. We also obtain simplified proofs of fundamental properties of the volumetric barrier, originally due to Vaidya.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206828
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    The primal power affine scaling method (1996)
    Springer
    Annals of operations research 62 (1996), S. 375-417 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; affine scaling methods ; interior point methods ; power barrier method ; power center ; merit function ; superlinear convergence ; three-step quadratic convergence ; efficient acceleration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we present a variant of the primal affine scaling method, which we call the primal power affine scaling method. This method is defined by choosing a realr〉0.5, and is similar to the power barrier variant of the primal-dual homotopy methods considered by den Hertog, Roos and Terlaky and Sheu and Fang. Here, we analyze the methods forr〉1. The analysis for 0.50〈r〈1 is similar, and can be readily carried out with minor modifications. Under the non-degeneracy assumption, we show that the method converges for any choice of the step size α. To analyze the convergence without the non-degeneracy assumption, we define a power center of a polytope. We use the connection of the computation of the power center by Newton's method and the steps of the method to generalize the 2/3rd result of Tsuchiya and Muramatsu. We show that with a constant step size α such that α/(1-α)2r 〉 2/(2r-1) and with a variable asymptotic step size αk uniformly bounded away from 2/(2r+1), the primal sequence converges to the relative interior of the optimal primal face, and the dual sequence converges to the power center of the optimal dual face. We also present an accelerated version of the method. We show that the two-step superlieear convergence rate of the method is 1+r/(r+1), while the three-step convergence rate is 1+ 3r/(r+2). Using the measure of Ostrowski, we note thet the three-step method forr=4 is more efficient than the two-step quadratically convergent method, which is the limit of the two-step method asr approaches infinity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206824
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    New complexity results for the Iri-Imai method (1996)
    Springer
    Annals of operations research 62 (1996), S. 539-564 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; Iri-Imai method ; primal-dual potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we show that the number of main iterations required by the Iri-Imai algorithm to solve a linear programming problem isO(nL). Moreover, we show that a modification of this algorithm requires only $$\mathcal{O}(\sqrt {nL} )$$ main iterations. In this modification, we measure progress by means of a primal-dual potential function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    The ANALYZE rulebase for supporting LP analysis (1996)
    Springer
    Annals of operations research 65 (1996), S. 91-126 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; large-scale systems ; computer-assisted analysis ; computational economics ; sensitivity analysis ; model management
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper describes how to design rules to support linear programming analysis in three functional categories: postoptimal sensitivity, debugging, and model management. The ANALYZE system is used to illustrate the behavior of the rules with a variety of examples. Postoptimal sensitivity analysis answers not only the paradigmWhat if …? question, but also the more frequently askedWhy …? question. The latter is static, asking why some solution value is what it is, or why it is not something else. The former is dynamic, asking how the solution changes if some element is changed. Debugging can mean a variety of things; here the focus is on diagnosing an infeasible instance. Model management includes documentation, verification, and validation. Rules are illustrated to provide support in each of these related functions, including some that require reasoning about the linear program's structure. Another model management function is to conduct a periodic review, with one of the goals being to simplify the model, if possible. The last illustration is how to test new rule files, where there is a variety of ways to communicate a result to someone who is not expert in linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187328
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    A recursive linear programming analysis of the future of the pulp and paper industry in the United States: Changes in supplies and demands, and the effects of recycling (1996)
    Springer
    Annals of operations research 68 (1996), S. 109-139 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; economic model ; pulp and paper ; recycling ; capacity ; demand and supply ; international trade
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The impacts of increased paper recycling on the U.S. pulp and paper sector are investigated, using the North American Pulp And Paper (NAPAP) model. This dynamic spatial equilibrium model forecasts the amount of pulp, paper and paperboard exchanged in a multi-region market, and the corresponding prices. The core of the model is a recursive price-endogenous linear programming system that simulates the behavior of a competitive industry. The model has been used to make forecasts of key variables describing the sector from 1986 to 2012, demand for paper would have the greatest impact on the amount of wood used. But the minimum recycled content policies envisaged currently would have no more effect than what will come about due to unregulated market forces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02205451
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    A simple proof of a primal affine scaling method (1996)
    Springer
    Annals of operations research 62 (1996), S. 303-324 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; affine scaling methods ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q−1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206821
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    A lower bound on the number of iterations of long-step primal-dual linear programming algorithms (1996)
    Springer
    Annals of operations research 62 (1996), S. 233-252 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; primal-dual interior-point algorithms ; lower bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn 1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206818
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    The implementation of linear programming algorithms based on homotopies (1996)
    Springer
    Algorithmica 15 (1996), S. 332-350 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Interior-point methods ; Homotopy methods ; Predictor-corrector ; Infeasible-interior methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A fundamental homotopy-based linear programming algorithm, which utilizes Euler-predictor and Newton-corrector steps with restarts, is formulated and investigated numerically on problems representative of linear programs that arise in practice. A rich array of refinements of this basic algorithm are possible within the homotopy framework. Such refinements are needed in any practical implementation and are discussed in detail. Implications for the design of integrated large-scale mathematical programming software are also briefly considered.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01961543
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    A subexponential bound for linear programming (1996)
    Springer
    Algorithmica 16 (1996), S. 498-516 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Combinatorial optimization ; Linear programming ; Smallest enclosing ball ; Smallest enclosing ellipsoid ; Randomized incremental algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a simple randomized algorithm which solves linear programs withn constraints andd variables in expected $$\min \{ O(d^2 2^d n),e^{2\sqrt {dIn({n \mathord{\left/ {\vphantom {n {\sqrt d }}} \right. \kern-\nulldelimiterspace} {\sqrt d }})} + O(\sqrt d + Inn)} \}$$ time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfyingn given linear inequalities ind variables. The expectation is over the internal randomizations performed by the algorithm, and holds for any input. In conjunction with Clarkson's linear programming algorithm, this gives an expected bound of $$O(d^2 n + e^{O(\sqrt {dInd} )} ).$$ The algorithm is presented in an abstract framework, which facilitates its application to several other related problems like computing the smallest enclosing ball (smallest volume enclosing ellipsoid) ofn points ind-space, computing the distance of twon-vertex (orn-facet) polytopes ind-space, and others. The subexponential running time can also be established for some of these problems (this relies on some recent results due to Gärtner).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940877
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems (1996)
    Springer
    Applied mathematics & optimization 33 (1996), S. 315-341 
    Details
    ISSN: 1432-0606
    Keywords: Linear programming ; Quadratic programming ; Linear complementarity problem ; Infeasible-interior-point algorithm ; Polynomial time ; 90C33 ; 65F05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract There are many interior-point algorithms for LP (linear programming), QP (quadratic programming), and LCPs (linear complementarity problems). While the algebraic definitions of these problems are different from each other, we show that they are all of the same general form when we define the problems geometrically. We derive some basic properties related to such geometrical (monotone) LCPs and based on these properties, we propose and analyze a simple infeasible-interior-point algorithm for solving geometrical LCPs. The algorithm can solve any instance of the above classes without making any assumptions on the problem. It features global convergence, polynomial-time convergence if there is a solution that is “smaller” than the initial point, and quadratic convergence if there is a strictly complementary solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01204707
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm (1996)
    Springer
    Mathematical methods of operations research 44 (1996), S. 147-170 
    Details
    ISSN: 1432-5217
    Keywords: Linear programming ; simplex algorithm ; probabilistic analysis ; asymptotic expansion ; convex hull ; stochastic geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Leta 1 ...,a m be i.i.d. points uniformly on the unit sphere in ℝ n ,m ≥n ≥ 3, and letX:= {xε ℝ n |a i T x≤1} be the random polyhedron generated bya 1, ...,a m . Furthermore, for linearly independent vectorsu, ū in ℝ n , letS u ,ū (X) be the number of shadow vertices ofX inspan(u,ū). The paper provides an asymptotic expansion of the expectation value¯S n,m := in4 1 E(S u,ū ) for fixedn andm→ ∞.¯S n,m equals the expected number of pivot steps that the shadow vertex algorithm — a parametric variant of the simplex algorithm — requires in order to solve linear programming problems of type max u T ,xεX, if the algorithm will be started with anX-vertex solving the problem max ū T ,x ε X. Our analysis is closely related to Borgwardt's probabilistic analysis of the simplex algorithm. We obtain a refined asymptotic analysis of the expected number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01194327
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    On the entropic perturbation and exponential penalty methods for linear programming (1996)
    Springer
    Journal of optimization theory and applications 89 (1996), S. 461-466 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; penalty function method ; barrier function method ; path-following method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This note points out that the recently proposed exponential penalty approach to linear programming is identical to the well-known entropic perturbation approach. The primal and dual trajectories provided by these two approaches are shown to be equivalent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02192539
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    An exterior-point method for linear programming problems (1996)
    Springer
    Journal of optimization theory and applications 91 (1996), S. 561-583 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; polynomial time algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper proves the convergence of an algorithm for solving linear programming problems inO(mn 2) arithmetic operations. The method is called an exterior-point procedure, because it obtains a sequence of approximations falling outside the setU of feasible solutions. Each iteration consists of a single step within some constraining hyperplane, followed by one or more projections which force the new approximation to fall within some envelope aboutU. The paper also discusses several numerical applications. In some types of problems, the method is considerably faster than a standard simplex method program when the size of the problem is sufficiently large.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02190122
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Primal—dual methods for linear programming (1995)
    Springer
    Mathematical programming 70 (1995), S. 251-277 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Barrier methods ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method. In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility. Finally, a new method for treating free variables is proposed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585940
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    The fleet assignment problem: Solving a large-scale integer program (1995)
    Springer
    Mathematical programming 70 (1995), S. 211-232 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Mixed-integer programming ; Large-scale optimization ; Airline fleet assignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585938
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Linear programming, complexity theory and elementary functional analysis (1995)
    Springer
    Mathematical programming 70 (1995), S. 279-351 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Complexity theory ; Interior-point methods ; Semi-definite programming ; Condition numbers ; Convex programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix. The notions pertain to linear programming quite generally; the underlying vector spaces are not required to be finite-dimensional and, more importantly, the cones defining nonnegativity are not required to be polyhedral. Thus, for example, the notions are appropriate in the context of semi-definite programming. We prove various theorems to demonstrate how the notions can be used in analyzing interior-point methods. These theorems assume little more than that the interiors of the cones (defining nonnegativity) are the domains of self-concordant barrier functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585941
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Presolving in linear programming (1995)
    Springer
    Mathematical programming 71 (1995), S. 221-245 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Presolving ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible. In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve. Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586000
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    On the choice of parameters for power-series interior point algorithms in linear programming (1995)
    Springer
    Mathematical programming 68 (1995), S. 49-71 
    Details
    ISSN: 1436-4646
    Keywords: Power-series interior point algorithms: Parameter transformations ; Best parameter ; k-parameter ; Truncated power-series approximation ; Higher-order derivatives ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study higher-order interior point algorithms, especially power-series algorithms, for solving linear programming problems. Since higher-order differentials are not parameter-invariant, it is important to choose a suitable parameter for a power-series algorithm. We propose a parameter transformation to obtain a good choice of parameter, called ak-parameter, for general truncated powerseries approximations. We give a method to find ak-parameter. This method is applied to two powerseries interior point algorithms, which are built on a primal—dual algorithm and a dual algorithm, respectively. Computational results indicate that these higher-order power-series algorithms accelerate convergence compared to first-order algorithms by reducing the number of iterations. Also they demonstrate the efficiency of thek-parameter transformation to amend an unsuitable parameter in power-series algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585757
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    Superlinear primal-dual affine scaling algorithms for LCP (1995)
    Springer
    Mathematical programming 69 (1995), S. 311-333 
    Details
    ISSN: 1436-4646
    Keywords: Interior-point methods ; Primal-dual affine scaling ; Linear programming ; Linear complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585562
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    On the convergence of the iteration sequence in primal-dual interior-point methods (1995)
    Springer
    Mathematical programming 68 (1995), S. 141-154 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Primal-dual interior-point algorithms ; Convergence of iteration sequence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently, numerous research efforts, most of them concerned with superlinear convergence of the duality gap sequence to zero in the Kojima—Mizuno—Yoshise primal-dual interior-point method for linear programming, have as a primary assumption the convergence of the iteration sequence. Yet, except for the case of nondegeneracy (uniqueness of solution), the convergence of the iteration sequence has been an important open question now for some time. In this work we demonstrate that for general problems, under slightly stronger assumptions than those needed for superlinear convergence of the duality gap sequence (except of course the assumption that the iteration sequence converges), the iteration sequence converges. Hence, we have not only established convergence of the iteration sequence for an important class of problems, but have demonstrated that the assumption that the iteration sequence converges is redundant in many of the above mentioned works.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585761
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables (1995)
    Springer
    Journal of optimization theory and applications 84 (1995), S. 675-679 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; Karmarkar's algorithm ; free variables
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this note, we first observe that the Morshedi-Tapia interpretation of the Karmarkar algorithm naturally offers an extension of the Karmarkar subproblem scaling to problems with free variables. We then note that this extended scaling is precisely the scaling suggested by Mitchell and Todd for problems with free variables. Mitchell and Todd gave no motivation for or justification of this extended scaling.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02191992
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Some variants of the todd low-complexity algorithm (1995)
    Springer
    Journal of optimization theory and applications 86 (1995), S. 173-190 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior-point algorithm ; potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Todd (Ref. 1) describes an interior-point algorithm for linear programming that is almost as simple as the affine-scaling method and yet achieves the currently best complexity of $$O\left( {\sqrt n t} \right)$$ iterations to attain precisiont based on the primal-only potential function ψ(x). In this paper, we propose some variants of the Todd algorithm by considering two local models: the ψ-model, trying to reduce the potential function ψ(x) as much as possible; and thec-model, trying to reduce the objective functionc T x as much as possible, with polynomiality retained. Some preliminary numerical results are presented to illustrate the behavior of these algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02193465
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    A primal-dual interior-point method for linear programming based on a weighted barrier function (1995)
    Springer
    Journal of optimization theory and applications 87 (1995), S. 301-321 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior-point methods ; polynomial covnergence ; quadratic convergence ; superlinear convergence ; least-squares problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02192566
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems (1995)
    Springer
    Journal of optimization theory and applications 87 (1995), S. 703-726 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior-point methods ; Iri-Imai algorithm ; local analysis ; degenerate problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A local analysis of the Iri-Imai algorithm for linear programming is given to demonstrate quadratic convergence under degeneracy. Specifically, we show that the algorithm with an exact line search either terminates after a finite number of iterations yielding a point on the set of optimal solutions or converges quadratically to one of the relative analytic centers of the faces of the set of optimal solutions including vertices. Mostly, the sequence generated falls into one of the optimal vertices, and it is rare that the sequence converges to the relative analytic center of a face whose dimension is greater than or equal to one.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02192140
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Polynomiality of infeasible-interior-point algorithms for linear programming (1994)
    Springer
    Mathematical programming 67 (1994), S. 109-119 
    Details
    ISSN: 1436-4646
    Keywords: Polynomial-time ; Linear programming ; Primal-dual ; Interior-point algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm “solves” the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582216
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Random walks, totally unimodular matrices, and a randomised dual simplex algorithm (1994)
    Springer
    Mathematical programming 64 (1994), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Random walks ; Totally unimodular matrices ; Uniform generation ; Linear programming ; Diameter of polytopes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We discuss the application of random walks to generating a random basis of a totally unimodular matrix and to solving a linear program with such a constraint matrix. We also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582563
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Dynamic factorization in large-scale optimization (1994)
    Springer
    Mathematical programming 64 (1994), S. 17-51 
    Details
    ISSN: 1436-4646
    Keywords: Factorization ; Linear programming ; Generalized upper bounds ; Pure networks ; Generalized networks
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows, and generalized network rows. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582564
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Interior-point algorithms for semi-infinite programming (1994)
    Springer
    Mathematical programming 65 (1994), S. 217-245 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Semi-infinite programming ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581697
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    The maximum entropy method on the mean: Applications to linear programming and superresolution (1994)
    Springer
    Mathematical programming 66 (1994), S. 103-122 
    Details
    ISSN: 1436-4646
    Keywords: 42B05 ; 62A99 ; Maximum entropy ; Linear programming ; Inverse problems ; Superresolution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we give two different results. We propose new methods to solve classical optimization problems in linear programming. We also obtain precise quantitative results for the superresolution phenomenon, as observed earlier by practical searchers on specific algorithms. The common background of our work is the generalized moment problem, which is known to be connected with linear programming and superresolution. We describe the Maximum Entropy Method on the Mean that provides solution to the problem and leads to computational criteria to decide the existence of solutions or not.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581139
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Superlinear convergence of infeasible-interior-point methods for linear programming (1994)
    Springer
    Mathematical programming 66 (1994), S. 361-377 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Infeasible-interior-point methods ; Superlinear convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 +τ whereτ can be arbitrarily close to one.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581155
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Limiting behavior of weighted central paths in linear programming (1994)
    Springer
    Mathematical programming 65 (1994), S. 347-363 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; (Weighted) central paths ; Limiting behavior on central paths ; Local convergence rates of interior point algorithms ; Primary: 90C05 ; Secondary: 90C33
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the limiting behavior of the weighted central paths{(x(μ), s(μ))} μ 〉 0 in linear programming at bothμ = 0 andμ = ∞. We establish the existence of a partition (B ∞,N ∞) of the index set { 1, ⋯,n } such thatx i(μ) → ∞ ands j (μ) → ∞ asμ → ∞ fori ∈ B ∞, andj ∈ N ∞, andx N∞ (μ),s B∞ (μ) converge to weighted analytic centers of certain polytopes. For allk ⩾ 1, we show that thekth order derivativesx (k) (μ) ands (k) (μ) converge whenμ → 0 andμ → ∞. Consequently, the derivatives of each order are bounded in the interval (0, ∞). We calculate the limiting derivatives explicitly, and establish the surprising result that all higher order derivatives (k ⩾ 2) converge to zero whenμ → ∞.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581702
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    Asymptotic analysis of the exponential penalty trajectory in linear programming (1994)
    Springer
    Mathematical programming 67 (1994), S. 169-187 
    Details
    ISSN: 1436-4646
    Keywords: 90C05 ; 90C25 ; 90C31 ; 49M30 ; Linear programming ; Exponential penalty ; Optimal trajectory ; Asymptotic expansion ; Interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the linear program min{c′x: Ax⩽b} and the associated exponential penalty functionf r(x) = c′x + rΣexp[(A ix − bi)/r]. Forr close to 0, the unconstrained minimizerx(r) off r admits an asymptotic expansion of the formx(r) = x * + rd* + η(r) wherex * is a particular optimal solution of the linear program and the error termη(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectoryλ(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to ∞: the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582220
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    A quadratically convergent predictor—corrector method for solving linear programs from infeasible starting points (1994)
    Springer
    Mathematical programming 67 (1994), S. 383-406 
    Details
    ISSN: 1436-4646
    Keywords: 90C05 ; Linear programming ; Primal—dual ; Polynomial complexity ; Infeasible ; Interior-point ; Exterior-point
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A predictor—corrector method for solving linear programs from infeasible starting points is analyzed. The method is quadratically convergent and can be combined with Ye's finite termination scheme under very general assumptions. If the starting points are large enough then the algorithm hasO(nL) iteration complexity. If the ratio between feasibility and optimality at the starting points is small enough then the algorithm has O( $$\sqrt {n L} $$ ) iteration complexity. For feasible starting points the algorithm reduces to the Mizuno—Todd—Ye predictor—corrector method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582228
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Constant potential primal—dual algorithms: A framework (1994)
    Springer
    Mathematical programming 66 (1994), S. 145-159 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Interior point methods ; Primal—dual algorithms ; Potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We start with a study of the primal—dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al., Mizuno and Nagasawa, and new potential functions we establish a framework for primal—dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. Our algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581142
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Thek-server dual and loose competitiveness for paging (1994)
    Springer
    Algorithmica 11 (1994), S. 525-541 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; k-Server problem ; Linear programming ; Approximation algorithms ; Paging ; Caching ; Competitive analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Weighted caching is a generalization ofpaging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-knownk-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled. We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holdingk items, incurs a cost within a factor ofk/(k−h+1) of the minimum cost possible given a cache holdingh items. The strategy generalizes “least recently used,” one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of thek-server problem. We introduceloose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. Ak-server strategy isloosely c(k)-competitive if, for any sequence, foralmost all k, the cost incurred by the strategy withk serverseither is no more thanc(k) times the minimum costor is insignificant. We show that certain paging strategies (including “least recently used,” and “first in first out”) that arek-competitive in the standard model are looselyc(k)-competitive providedc(k)/Ink→∞ and bothk/c(k) andc(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is Θ(Ink)-competitive in the standard model, is looselyc(k)-competitive providedk−2 In Ink→∞ and both 2 Ink−c(k) andc(k) are nondecreasing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189992
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    Polynomial algorithms for linear programming over the algebraic numbers (1994)
    Springer
    Algorithmica 12 (1994), S. 436-457 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Algebraic numbers ; Computational complexity ; Ellipsoid method ; Polynomial-time algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a rational-number problem. We also view the coefficients of a linear program as members of a finite algebraic extension of the rational numbers. The degree of this extension is an upper bound on the degree of any algebraic number that can occur during the course of the algorithm, and in this sense can be viewed as a supplementary measure of problem dimension. Working under an arithmetic model of computation, and making use of a tool for obtaining upper and lower bounds on polynomial functions of algebraic numbers, we derive an algorithm based on the ellipsoid method that runs in time bounded by a polynomial in the dimension, degree, and size of the linear program. Similar results hold under a rational number model of computation, given a suitable binary encoding of the problem input.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188714
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Linear programming formulation of MDPs in countable state space: The multichain case (1994)
    Springer
    Mathematical methods of operations research 40 (1994), S. 91-108 
    Details
    ISSN: 1432-5217
    Keywords: Markov decision processes ; countable state space ; Linear programming ; duality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present an Linear Programming formulation of MDPs with countable state and action spaces and no unichain assumption. This is an extension of the Hordijk and Kallenberg (1979) formulation in finite state and action spaces. We provide sufficient conditions for both existence of optimal solutions to the primal LP program and absence of duality gap. Then, existence of a (possibly randomized) average optimal policy is also guaranteed. Existence of a stationary average optimal deterministic policy is also investigated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01414031
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Geometry of optimal value functions with applications to redundancy in linear programming (1994)
    Springer
    Journal of optimization theory and applications 81 (1994), S. 35-52 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; optimal value functions ; redundancy in linear programming ; convex hull problem ; data envelopment analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02190312
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    The simplex method as a global optimizer: A c-programming perspective (1994)
    Springer
    Journal of global optimization 4 (1994), S. 89-109 
    Details
    ISSN: 1573-2916
    Keywords: Linear programming ; simplex method ; c-programming ; composite functions ; global optimization ; dc problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we give a brief account of the important role that the conventional simplex method of linear programming can play in global optimization, focusing on its collaboration with composite concave programming techniques. In particular, we demonstrate how rich and powerful the c-programming format is in cases where its parametric problem is a standard linear programming problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096536
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    On solution-containing ellipsoids in linear programming (1994)
    Springer
    Journal of optimization theory and applications 80 (1994), S. 161-173 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior point methods ; containing ellipsoids ; optimal basic and nonbasic variables
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Ellipsoids that contain all optimal dual slack solutions and those that contain all optimal primal solutions and that are independent of the algorithm used are derived. Based upon these ellipsoids, two criteria each for detecting optimal basic and nonbasic variables prior to optimality in interior-point methods are obtained. Using these results, we then derive a sufficient condition for a linear program to be feasible.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02196599
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Rank-one techniques in log-barrier function methods for linear programming (1994)
    Springer
    Journal of optimization theory and applications 82 (1994), S. 405-413 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior-point methods ; Karmarkar's method ; log-barrier function ; rank-one techniques ; computational complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This short paper presents a primal interior-point method for linear programming. The method can be viewed as a modification of the methods developed in Refs. 1–6. In each iteration, it computes an approximately projected Newton direction and needsO(n 2.5) arithmetic operations to make the log-barrier function significantly decrease. It requires $$O(\sqrt {nL} )$$ iterations, so that the total complexity isO(n 3 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02191863
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Primal-dual algorithms for linear programming based on the logarithmic barrier method (1994)
    Springer
    Journal of optimization theory and applications 83 (1994), S. 1-26 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; primal-dual interior point methods ; logarithmic barrier function ; polynomial algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely $$O(\sqrt n L)$$ iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02191759
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Near boundary behavior of primal—dual potential reduction algorithms for linear programming (1993)
    Springer
    Mathematical programming 58 (1993), S. 243-255 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; primal—dual potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper is concerned with selection of theρ-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + $$\sqrt n $$ , ∞), the level ofρ determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant,ρ must be set close ton + $$\sqrt n $$ . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate thatρ can be sometimes chosen in a wide range [n + $$\sqrt n $$ , ∞) while still guaranteeing the currently best convergence rate of O( $$\sqrt n $$ L) iterations. This finding is encouraging since in practice large values ofρ have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581269
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Combining phase I and phase II in a potential reduction algorithm for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 133-150 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; combined phase I—phase II
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes an affine potential reduction algorithm for linear programming that simultaneously seeks feasibility and optimality. The algorithm is closely related to a similar method of Anstreicher. The new features are that we use a two-dimensional programming problem to derive better lower bounds than Anstreicher, that our direction-finding subproblem treats phase I and phase II more symmetrically, and that we do not need an initial lower bound. Our method also allows for the generation of a feasible solution (so that phase I is terminated) during the course of the iterations, and we describe two ways to encourage this behavior.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581241
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    A quadratically convergent O( $$\sqrt n $$ L)-iteration algorithm for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 151-162 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; superlinear and quadratic convergence ; polynomiality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( $$\sqrt n $$ L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581242
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    A note on the prize collecting traveling salesman problem (1993)
    Springer
    Mathematical programming 59 (1993), S. 413-420 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; prize collecting ; rounding fractional solutions ; traveling salesman problem ; worst-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581256
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 517-535 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; Projective algorithm ; Standard form
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve $$O\left( {\sqrt {nL} } \right)$$ step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Determination of optimal vertices from feasible solutions in unimodular linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 23-31 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; duality theorem ; unimodular ; totally unimodular ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581235
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    A strictly improving linear programming Phase I algorithm (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 409-430 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; Phase I ; nonlinear programming ; least squares ; quadratic programming ; strict improvement ; degeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called “basic”) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs. When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023107
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Degeneracy in interior point methods for linear programming: a survey (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 107-138 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; interior point methods ; degeneracy ; polynomial algorithms ; global and local convergence ; basis recovery ; numerical performance ; sensitivity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02096259
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Studies of lexicography in the generalized network simplex method (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 235-248 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; generalized networks ; simplex method ; degeneracy ; lexicography ; cycling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained can help us to understand and to extend the existing theory. First, it is verified that all nonzero elements have the same sign in each row vector of a basis inverse for a generalized network (GN) problem with positive multipliers. However, this property does not necessarily hold when there exist negative multipliers. Second, we developed a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive andnegative multipliers. This strategy is also based on lexicography and requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step isO(n) in the worst case. This worst case effort is the same as that required by the strongly convergent rules for selecting the dropping arc in the method of strong convergence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023097
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Pivot rules for linear programming: A survey on recent theoretical developments (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 203-233 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; simplex method ; pivot rules ; cycling ; recursion ; minimal index rule ; parametric programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed. In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02096264
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    A practical anti-degeneracy row selection technique in network linear programming (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 431-442 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; degeneracy ; network simplex algorithm ; pivoting ; minimal cost network flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023108
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    An active-set strategy in an interior point method for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 345-360 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point method ; active set strategy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed “active constraints”—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( $$\sqrt n $$ L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581252
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio (1993)
    Springer
    Mathematical programming 61 (1993), S. 39-52 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; quadratic programming ; convex programming ; randomized algorithms ; fixed dimension optimization problems ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = Ω(d 2), the expected total number of major Karmarkar's iterations is O(d 2(logn)L), compared to the best known deterministic bound of O( $$\sqrt n$$ L). We also present several other results which follow from the general scheme.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582137
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    Load balancing in the parallel optimization of block-angular linear programs (1993)
    Springer
    Mathematical programming 62 (1993), S. 41-67 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Dantzig—Wolfe decomposition ; large-scale systems ; parallel processing ; hypercube architecture
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Decomposition algorithms for block-angular linear programs give rise to a natural, coarse-grained parallelism that can be exploited by processing the subproblems concurrently within a distributed-memory environment. The parallel efficiency of the distributed approach, however, is critically dependent on the duration of the inherently serial master phase relative to that of the bottleneck subproblem. This paper investigates strategies for improving efficiency in distributed Dantzig—Wolfe decomposition by better balancing the load between the master and subproblem processors. We report computational experience on an Intel iPSC/2 hypercube multiprocessor with test problems having dimensions up to about 30 000 rows, 87 000 columns, and 200 coupling constraints.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585159
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Solving symmetric indefinite systems in an interior-point method for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 15-39 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; symmetric indefinite systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite “augmented” systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite “normal equations” that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585158
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    A primal—dual affine-scaling potential-reduction algorithm for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 119-131 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; complexity ; potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585163
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Finding an interior point in the optimal face of linear programs (1993)
    Springer
    Mathematical programming 62 (1993), S. 497-515 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal—dual methods ; optimal face ; strict complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n 3 L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    On combined phase 1-phase 2 projective methods for linear programming (1993)
    Springer
    Algorithmica 9 (1993), S. 64-83 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Interior-point methods ; Projective methods ; Combined phase 1-phase 2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185339
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise (1993)
    Springer
    Algorithmica 9 (1993), S. 184-197 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Karmarkar's algorithm ; Potential function ; Primal-dual, Modified method ; Rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider partial updating in Kojima, Mizuno, and Yoshise's primal-dual potential reduction algorithm for linear programming. We use a simple safeguard condition to control the number of updates incurred on combined primal-dual steps. Our analysis allows for unequal steplengths in the primal and dual variables, which appears to be a computationally significant factor for primal-dual methods. The safeguard we use is a primal-dual Goldstein-Armijo condition, modified to deal with the unequal primal and dual steplengths.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188712
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Long steps in an O(n 3 L) algorithm for linear programming (1992)
    Springer
    Mathematical programming 54 (1992), S. 251-265 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; potential function ; standard form ; modified method ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n 3 L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous “primal-only” initialization actually reduces the complexity to less than O(m 1.5 n 1.5 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586053
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    On Anstreicher's combined phase I—phase II projective algorithm for linear programming (1992)
    Springer
    Mathematical programming 55 (1992), S. 1-15 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point method ; projective algorithm ; combining phase I–phase II
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581187
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    Zur Modellierung logischer Aussagen ergänzend zu Linearen Programmen (1992)
    Springer
    OR spectrum 14 (1992), S. 149-160 
    Details
    ISSN: 1436-6304
    Keywords: Lineare Programmierung ; logische Aussagen ; Binärvariablen ; Modellgenerator ; Linear programming ; predicates ; binary variables ; model generator
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Summary We introduce in the field of formulating logical predicates in addition to linear programs. The error prone process of developing linear constraints including binary variables (“auxilliary formulations”) to accomplish this leads us to discuss the possibilities and capabilities of model generation. Based on Williams [12] we develop the formulae apparatus and discuss formulation and design problems for the development of our model generator now being implemented.
    Notes: Zusammenfassung Wir geben eine Einführung in das Gebiet der Formulierung logischer Aussagen ergänzend zu Linearen Programmen. Der dazu notwendige, fehlerträchtige Prozeß der Aufstellung linearer Restriktionen unter der Verwendung von Binärvariablen („Ersatzformulierungen“) führt uns dazu, die Möglichkeiten und Fähigkeiten eines Modellgenerators für diesen Zweck zu diskutieren. Auf der Grundlage von Williams [12] entwickeln wir den Formelapparat und erörtern Formulierungs- und Entwurfsprobleme für die Entwicklung unseres sich jetzt in der Implementationsphase befindlichen Modellgenerators.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01783518
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices (1992)
    Springer
    Mathematical programming 57 (1992), S. 121-143 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; polynomial-time algorithms ; strongly polynomial-time algorithms ; circulant matrices ; algebraic numbers
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581077
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    MODLER: Modeling by object-driven linear elemental relations (1992)
    Springer
    Annals of operations research 38 (1992), S. 239-280 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; large-scale systems ; modeling ; language design
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper describes a system to represent linear programming models and their instances. In addition to a modeling language, MODLER has an extensive query capability which includes a multi-view architecture. Further, randomization options provide rapid prototyping. The MODLER system is part of a workbench for building and managing decision support systems that are based on linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283655
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    A simplex algorithm for piecewise-linear programming III: Computational analysis and applications (1992)
    Springer
    Mathematical programming 53 (1992), S. 213-235 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex methods ; piecewise-linear programming ; nondifferentiable optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewiselinear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustarate these arguments; the piecewise-linear simplex algorithm is observed to run 2–6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585703
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Finding effective “force targets” for two-dimensional, multifinger frictional grips (1992)
    Springer
    Algorithmica 8 (1992), S. 1-20 
    Details
    ISSN: 1432-0541
    Keywords: Robotics ; Grasp planning ; Robot control ; Computational Geometry ; Linear programming ; Parametric searching ; Davenport-Schinzel sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we apply techniques from computational geometry to solve several problems in grasp planning and control in robotics. We consider the problem of calculating “force targets ” for a collection ofn fingers which grasp a two-dimensional object at known positions, at which the normals to the surface are also assumed to be known at least approximately. If the points at which the fingers touch the body do not allow apositive grip to be exerted (i.e., a grip in which the fingers hold the body in equilibrium by exerting friction-free forces in the directions of the corresponding inward-directed normals), it is appropriate to find the smallest coefficient of friction for which it is possible to assign a set of forces to be exerted by the fingers (so-calledfinger-force targets) which hold the object at equilibrium and such that each individual force lies within the corresponding cone of friction. We present an algorithm for this problem which runs in time0(n log2 n log logn). We also present another algorithm for preprocessing the given data so as to allow fast computation of the desired coefficient of friction for the case in which one needs to balance any given “query” external force and torque. Finally, we discuss simpler variants of our techniques which are likely to be more efficient when the problem is solved for a small number of fingers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758833
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    A geometric view of parametric linear programming (1992)
    Springer
    Algorithmica 8 (1992), S. 161-176 
    Details
    ISSN: 1432-0541
    Keywords: Parametric linear programming ; Sensitivity analysis ; Postoptimality analysis ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem ϑ(λ) = min{c t x¦Ax =b + λ¯b,x ≥ 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function ϑ(λ). As a consequence, the optimality intervals form a partition of the closed interval {λ; ¦ϑ(λ)¦ 〈 ∞}. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of ϑ(λ) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758841
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming (1992)
    Springer
    Applied mathematics & optimization 25 (1992), S. 247-262 
    Details
    ISSN: 1432-0606
    Keywords: Projection ; Féjer-contraction ; Linear complementarity problem ; Linear programming ; Convex quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we propose a new iterative method for solving a class of linear complementarity problems:u ≥ 0,Mu + q ≥ 0, uT(Mu + q)=0, where M is a givenl ×l positive semidefinite matrix (not necessarily symmetric) andq is a givenl-vector. The method makes two matrix-vector multiplications and a trivial projection onto the nonnegative orthant at each iteration, and the Euclidean distance of the iterates to the solution set monotonously converges to zero. The main advantages of the method presented are its simplicity, robustness, and ability to handle large problems with any start point. It is pointed out that the method may be used to solve general convex quadratic programming problems. Preliminary numerical experiments indicate that this method may be very efficient for large sparse problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182323
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    L 1 Sensitivity minimization for plants with commensurate delays (1992)
    Springer
    Mathematics of control, signals, and systems 5 (1992), S. 281-293 
    Details
    ISSN: 1435-568X
    Keywords: L 1 optimal control ; Delay and infinite-dimensional linear systems ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Electrical Engineering, Measurement and Control Technology , Mathematics , Technology
    Notes: Abstract In this paper we consider the problem ofL 1 sensitivity minimization for linear plants with commensurate input delays. We describe a procedure for computing the minimum performance, and we characterize optimal solutions. The computations involve solving a one-parameter family of finite-dimensional linear programs. Explicit solutions are presented for important special cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211562
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited (1992)
    Springer
    Journal of optimization theory and applications 73 (1992), S. 229-242 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; primal-dual interior-point algorithms ; superlinear convergence ; quadratic convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940179
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Sensitivity method for basis inverse representation in multistage stochastic linear programming problems (1992)
    Springer
    Journal of optimization theory and applications 74 (1992), S. 221-242 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; stochastic programming ; simplex method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940892
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    An unconstrained convex programming view of linear programming (1992)
    Springer
    Mathematical methods of operations research 36 (1992), S. 149-161 
    Details
    ISSN: 1432-5217
    Keywords: Linear programming ; Barrier Function ; Entropy Function ; Geometric Programming ; Convex programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The major interest of this paper is to show that, at least in theory, a pair of primal and dual “ɛ-optimal solutions” to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01417214
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Interior proximal point algorithm for linear programs (1992)
    Springer
    Journal of optimization theory and applications 74 (1992), S. 425-444 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior point method ; proximal point method ; Newton method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An interior proximal point algorithm for finding a solution of a linear program is presented. The distinguishing feature of this algorithm is the addition of a quadratic proximal term to the linear objective function. This perturbation has allowed us to obtain solutions with better feasibility. Implementation of this algorithm shows that the algorithms. We also establish global convergence and local linear convergence of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940319
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Deriving an unconstrained convex program for linear programming (1992)
    Springer
    Journal of optimization theory and applications 75 (1992), S. 603-612 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; convex programming ; geometric programming ; duality theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940495
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Extensions of the potential reduction algorithm for linear programming (1992)
    Springer
    Journal of optimization theory and applications 72 (1992), S. 487-498 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; primal and dual problems ; bimatrix games ; potential function ; potential reduction algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this work, we study several extensions of the potential reduction algorithm that was developed for linear programming. These extensions include choosing different potential functions, generating the analytic center of a polytope, and finding the equilibrium of a zero-sum bimatrix game.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00939838
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Comparative analysis of affine scaling algorithms based on simplifying assumptions (1991)
    Springer
    Mathematical programming 52 (1991), S. 405-414 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; potential reduction algorithm ; affine scaling algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We analyze several affine potential reduction algorithms for linear programming based on simplifying assumptions. We show that, under a strong probabilistic assumption regarding the distribution of the data in an iteration, the decrease in the primal potential function will be $$\Omega (\rho /\sqrt {log(n)} )$$ with high probability, compared to the guaranteedΩ(1). (ρ ⩾2n is a parameter in the potential function andn is the number of variables.) Under the same assumption, we further show that the objective reduction rate of Dikin's affine scaling algorithm is $$(1 - 1/\sqrt {log(n)} )$$ with high probability, compared to no guaranteed convergence rate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582897
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Global convergence of the affine scaling methods for degenerate linear programming problems (1991)
    Springer
    Mathematical programming 52 (1991), S. 377-404 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point methods ; affine scaling methods ; global analysis ; degenerate problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582896
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    A combined phase I—phase II scaled potential algorithm for linear programming (1991)
    Springer
    Mathematical programming 52 (1991), S. 429-439 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; potential function ; phase I ; phase II ; artificial variable
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We develop an extension of the affinely scaled potential reduction algorithm which simultaneously obtains feasibility and optimality in a standard form linear program, without the addition of any “M” terms. The method, and its lower-bounding procedure, are particularly simple compared with previous interior algorithms not requiring feasibility.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582899
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    An O(n 3 L) adaptive path following algorithm for a linear complementarity problem (1991)
    Springer
    Mathematical programming 52 (1991), S. 587-595 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; linear complementarity problem ; interior point algorithms ; path following algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose an O(n 3 L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n 3 L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n 3 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582906
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Linear programming with spheres and hemispheres of objective vectors (1991)
    Springer
    Mathematical programming 51 (1991), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; parametric ; homeomorphisms ; spheres ; hemispheres
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a linear program with a boundedp-dimensional feasible region let the objective vector range over ans-sphere, that is, ans-dimensional sphere centered at the origin wheres does not exceedp−1. If the feasible region and the sphere are in general position with respect to each other, then the corresponding set of all optimal solutions is a topologicals-sphere. Similar results are developed for unbounded feasible regions and hemispheres of objective vectors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586923
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    An O(n 3 L) potential reduction algorithm for linear programming (1991)
    Springer
    Mathematical programming 50 (1991), S. 239-258 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; interior algorithms ; potential functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe a primal-dual potential function for linear programming: $$\phi (x,s) = \rho \ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j s_j )} $$ whereρ⩾ n, x is the primal variable, ands is the dual-slack variable. As a result, we develop an interior point algorithm seeking reductions in the potential function with $$\rho = n + \sqrt n $$ . Neither tracing the central path nor using the projective transformation, the algorithm converges to the optimal solution set in $$O(\sqrt n L)$$ iterations and uses O(n 3 L) total arithmetic operations. We also suggest a practical approach to implementing the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01594937
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    Improving the rate of convergence of interior point methods for linear programming (1991)
    Springer
    Mathematical programming 52 (1991), S. 467-479 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; polynomial methods ; interior point methods ; rate of convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( $$\bar x^k$$ ). Under the suitable assumptions it is shown that the sequence ( $$\bar x^k$$ ) converges superlinearly faster to the solution than (x k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582901
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    Search directions for interior linear-programming methods (1991)
    Springer
    Algorithmica 6 (1991), S. 153-181 
    Details
    ISSN: 1432-0541
    Keywords: Karmarkar's algorithm ; Linear programming ; Projective algorithm ; Conical projection ; Interior methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. This paper examines several search directions in a common framework that does not need any problem transformation. These directions prove to be combinations of two problem-dependent vectors, and can all be improved by a bidirectional search procedure. We conclude that there are essentially two polynomial algorithms: Karmarkar's method and the algorithm that follows a central trajectory, and they differ only in a choice of parameters (respectively lower bound and penalty multiplier).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759039
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    Retiming synchronous circuitry (1991)
    Springer
    Algorithmica 6 (1991), S. 5-35 
    Details
    ISSN: 1432-0541
    Keywords: Digital circuitry ; Graph theory ; Linear programming ; Network flow ; Optimization ; Pipelining ; Propagation delay ; Retiming ; Synchronous circuitry ; Systolic circuits ; Timing analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph in which the vertex setV is a collection of combinational logic elements and the edge setE is the set of interconnections, each of which may pass through zero or more registers. We give anO(¦V∥E¦lg¦V¦) algorithm for determining an equivalent retimed circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a chacterization of optimal retiming based on an efficiently solvable mixed-integer linear-programming problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759032
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    Linear programming by minimizing distances (1991)
    Springer
    Mathematical methods of operations research 35 (1991), S. 299-307 
    Details
    ISSN: 1432-5217
    Keywords: Linear programming ; Newton's method ; penalty methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract To solve the linear program (LP): minimizec T l subject toA l+b≥0, for ann×d-matrixA, ann-vectorb and ad-vectorc, the positive orthantS and the planeE(t) are defined by S={(x1,x)εℝn+1 ¦(x1,x)⩾0}, E(t)={(x1,x)εℝn+1¦x1=−c c l+t, x=Al+b}. First a geometric algorithm is given to determine d(E(t),S) for fixedt, where d(·,·) denotes euclidean distance. This algorithm is used to construct a second algorithm to find the minimalt with E(t) ∩S ≠ ∅, and thus solve LP. It is shown that all algorithms are finite.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01417518
    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...