ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (66)
  • Other Sources
  • Linear programming  (66)
  • Springer  (66)
  • Berkeley Electronic Press (now: De Gruyter)
  • 1995-1999  (35)
  • 1985-1989  (31)
  • Mathematics  (66)
Collection
  • Articles  (66)
  • Other Sources
Source
Keywords
Publisher
  • Springer  (66)
  • Berkeley Electronic Press (now: De Gruyter)
Years
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Decomposition of linear programs using parallel computation (1988)
    Springer
    Mathematical programming 42 (1988), S. 391-405 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; large-scale-systems ; decomposition ; parallel computing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes DECOMPAR: an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular linear programs using parallel processing of the subproblems. The software is based on a robust experimental code for LP decomposition and runs on the CRYSTAL multicomputer at the University of Wisconsin-Madison. Initial computational experience is reported. Promising directions in future development of this approach are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589413
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
  • 3
    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
  • 4
    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
  • 5
    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
  • 6
    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
  • 7
    Electronic Resource
    Electronic Resource
    An implementation of Karmarkar's algorithm for linear programming (1989)
    Springer
    Mathematical programming 44 (1989), S. 297-335 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01587095
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    A polynomial-time algorithm, based on Newton's method, for linear programming (1988)
    Springer
    Mathematical programming 40 (1988), S. 59-93 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior method ; computational complexity ; Newton's method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580724
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Computing Karmarkar projections quickly (1988)
    Springer
    Mathematical programming 41 (1988), S. 61-71 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's method ; Cholesky factorization ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The paper presents a numerical method for computing the projections for Karmarkar's new algorithm for linear programming. The method is simple to implement, fully exploits sparsity, and appears in limited experimentation to have good stability properties. Preliminary numerical experience indicates that the method promises advantages over methods that refactor a matrix at every iteration.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580753
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    On the solution of highly degenerate linear programmes (1988)
    Springer
    Mathematical programming 41 (1988), S. 385-392 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex method ; degeneracy ; scheduling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The solution of scheduling problems often gives rise to highly degenerate linear programmes which cause significant computational difficulties for the revised simplex method. Wolfe's highly effective “ad hoc” method for overcoming the cycling or stalling problems associated with degeneracy is described. Here it is given a geometric interpretation in terms of finding a direction of recession for a reduced problem which is fundamental to a full understanding of the procedure. An example of an aircrew scheduling problem is used to illustrate the effectiveness of the method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580776
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    Linear programming and the newton barrier flow (1988)
    Springer
    Mathematical programming 41 (1988), S. 367-373 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior algorithm ; central trajectory ; barrier function ; Newton's method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this note we report a simple characteristic of linear programming central trajectories which has a surprising consequence. Specifically, we show that given a bounded polyhedral setP with nonempty interior, the logarithmic barrier function (with no objective component) induces a vector field of negative Newton directions which flows from the center ofP, along central trajectories, to solutions of every possible linear program onP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580774
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    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
  • 13
    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
  • 14
    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
  • 15
    Electronic Resource
    Electronic Resource
    Exploiting special structure in Karmarkar's linear programming algorithm (1988)
    Springer
    Mathematical programming 41 (1988), S. 97-113 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; special structure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580755
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    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
  • 17
    Electronic Resource
    Electronic Resource
    Planning under uncertainty using parallel computing (1988)
    Springer
    Annals of operations research 14 (1988), S. 1-16 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; planning under uncertainty ; large-scale systems ; parallel processors ; stochastic programming ; decomposition principle
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Industry and government routinely solve deterministic mathematical programs for planning and schelduling purposes, some involving thousands of variables with a linear or non-linear objective and inequality constraints. The solutions obtained are often ignored because they do not properly hedge against future contingencies. It is relatively easy to reformulate models to include uncertainty. The bottleneck has been (and is) our capability to solve them. The time is now ripe for finding a way to do so. To this end, we describe in this paper how large-scale system methods for solving multi-staged systems, such as Bender's Decomposition, high-speed sampling or Monte Carlo simulation, and parallel processors can be combined to solve some important planning problems involving uncertainty. For example, parallel processors may make it possible to come to better grips with the fundamental problems of planning, scheduling, design, and control of complex systems such as the economy, an industrial enterprise, an energy system, a water-resource system, military models for planning-and-control, decisions about investment, innovation, employment, and health-delivery systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02186471
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Modifying the forrest-tomlin and saunders updates for linear programming problems with variable upper bounds (1986)
    Springer
    Annals of operations research 5 (1986), S. 501-515 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; variable upper bounds ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Forrest-Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02022088
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    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
  • 20
    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
  • 21
    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
  • 22
    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
  • 23
    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
  • 24
    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
  • 25
    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
  • 26
    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
  • 27
    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
  • 28
    Electronic Resource
    Electronic Resource
    Advanced basis construction in linear programming (1986)
    Springer
    Annals of operations research 5 (1986), S. 413-424 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; basis construction ; matrix rearrangement
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper considers basis construction in a linear program when the number of activities with basic status is not equal to the number of rows in the particular scenario. This arises when starting with an ‘advanced basis’, obtained from a solution to another scenario. The goal here is to provide a triangular-seeking algorithm that takes advantage of structural properties during the construction of a basis agenda. For completeness, some facts, which are known but have not been published, are given about choosing an advanced basis and about spikes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02022083
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    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
  • 30
    Electronic Resource
    Electronic Resource
    A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy (1988)
    Springer
    Mathematical programming 41 (1988), S. 281-315 
    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 simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegeneracy of all such solutions. Part II now shows how these assumptions can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580769
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    A relaxed version of Karmarkar's method (1988)
    Springer
    Mathematical programming 40 (1988), S. 289-315 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's method ; inexact projections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A relaxed version of Karmarkar's method is developed. This method is proved to have the same polynomial time complexity as Karmarkar's method and its efficient implementation using inexact projections is discussed. Computational results obtained using a preliminary implementation of the method are presented which indicate that the method is practicable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580737
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    A combined phase I-phase II projective algorithm for linear programming (1989)
    Springer
    Mathematical programming 43 (1989), S. 209-223 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; projective algorithm ; artificial variable ; phase I
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasible) standard form linear program, without the addition of any “bigM“ terms or conversion to a primal-dual problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582290
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    A randomized algorithm for fixed-dimensional linear programming (1989)
    Springer
    Mathematical programming 44 (1989), S. 203-212 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; randomized algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is $$O(d^{(3 + \varepsilon _d )d} n)$$ , where lim d→∞ ε d = 0. This improves the corresponding worst-case complexity, $$O(3^{d^2 } n)$$ . The method is based on a recent idea of Clarkson. Two variations on the algorithm are examined briefly.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01587088
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    A practical anti-cycling procedure for linearly constrained optimization (1989)
    Springer
    Mathematical programming 45 (1989), S. 437-474 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex method ; active-set methods ; degeneracy ; cycling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A procedure is described for preventing cycling in active-set methods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a “working” feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and “stalling” cannot occur with exact arithmetic. The method appears to be reliable, based on computational results for the first 53 linear programming problems in theNetlib set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589114
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    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
  • 36
    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
  • 37
    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
  • 38
    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
  • 39
    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
  • 40
    Electronic Resource
    Electronic Resource
    A projective method for linear programming with box-type constraints (1986)
    Springer
    Algorithmica 1 (1986), S. 517-527 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Projective method ; Box constraints
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840460
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Homotopy techniques in linear programming (1986)
    Springer
    Algorithmica 1 (1986), S. 529-535 
    Details
    ISSN: 1432-0541
    Keywords: Homotopy ; Linear programming ; Interior point methods ; Nonlinear programming ; Karmarkar's method ; Quadratic regularization ; Path-following
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this note, we consider the solution of a linear program, using suitably adapted homotopy techniques of nonlinear programming and equation solving that move through the interior of the polytope of feasible solutions. The homotopy is defined by means of a quadratic regularizing term in an appropriate metric. We also briefly discuss algorithmic implications and connections with the affine variant of Karmarkar's method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840461
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    The iterative step in the linear programming algorithm of N. Karmarkar (1986)
    Springer
    Algorithmica 1 (1986), S. 537-539 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Karmarkar's algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We simplify and strengthen the analysis of the improvement obtained in one step of Karmarkar's algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840462
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Global wire routing in two-dimensional arrays (1987)
    Springer
    Algorithmica 2 (1987), S. 113-129 
    Details
    ISSN: 1432-0541
    Keywords: Global routing ; Gate arrays ; Integer programming ; Linear programming ; Computer-aided design for integrated circuits
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We examine the problem of routing wires of a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case “channel-width” needed to route ann×n array, and develop provably good heuristics for the general case. Single-turn routings are proved to be near-optimal in the worst-case. A central result of our paper is a “rounding algorithm” for obtaining integral approximations to solutions of linear equations. Given a matrix A and a real vector x, then we can find an integral x such that for alli, ¦x i -x i ¦ 〈1 and (Ax) i -(Ax) i 〈Δ. Our error bound Δ is defined in terms of sign-segregated column sums of A: $$\Delta = \mathop {\max }\limits_j \left( {\max \left\{ {\sum\limits_{i:a_{ij} 〉 0} {a_{ij} ,} \sum\limits_{i:a_{ij}〈 0} { - a_{ij} } } \right\}} \right).$$
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840353
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    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
  • 45
    Electronic Resource
    Electronic Resource
    A modification of karmarkar's linear programming algorithm (1986)
    Springer
    Algorithmica 1 (1986), S. 395-407 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Karmarkar's algorithm ; Projected gradient methods ; Least squares
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviatinga priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840454
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    An extension of Karmarkar's algorithm for linear programming using dual variables (1986)
    Springer
    Algorithmica 1 (1986), S. 409-424 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Karmarkar's algorithm ; Duality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840455
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    A polynomial newton method for linear programming (1986)
    Springer
    Algorithmica 1 (1986), S. 425-453 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Polynomial complexity ; Newton method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n 2 m 2 L) operations that there is no solution or, else, computes an exact solution in at mostO(n 3 m 2 L) operations. The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n 3 m 2 L) operations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840456
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    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
  • 49
    Electronic Resource
    Electronic Resource
    A multiplicative barrier function method for linear programming (1986)
    Springer
    Algorithmica 1 (1986), S. 455-482 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Interior method ; Barrier function ; Newton method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A simple Newton-like descent algorithm for linear programming is proposed together with results of preliminary computational experiments on small- and medium-size problems. The proposed algorithm gives local superlinear convergence to the optimum and, experimentally, shows global linear convergence. It is similar to Karmarkar's algorithm in that it is an interior feasible direction method and self-correcting, while it is quite different from Karmarkar's in that it gives superlinear convergence and that no artificial extra constraint is introduced nor is protective geometry needed, but only affine geometry suffices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840457
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    A monotonic projective algorithm for fractional linear programming (1986)
    Springer
    Algorithmica 1 (1986), S. 483-498 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Fractional linear programming ; Karmarkar's algorithm ; Projective algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840458
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    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
  • 52
    Electronic Resource
    Electronic Resource
    Evolution, games theory and polyhedra (1987)
    Springer
    Journal of mathematical biology 25 (1987), S. 393-409 
    Details
    ISSN: 1432-1416
    Keywords: Evolution ; Evolutionary stable states ; Games theory ; Linear programming ; Convex polyhedra ; Linear complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Mathematics
    Notes: Abstract The problem of finding an Evolutionary Stable Strategy (ESS) for an animal species is defined. It is shown how such strategies are a subset of the equilibrium solutions for a particular non-zero sum game. These equilibrium solutions are then shown to arise from the vertices of a particular convex polyhedron. A method of finding these equilibrium solutions through the vertices and then the ESS solutions is given. This is illustrated by a number of numerical examples taken from the literature. Finally an alternative approach based on solving a Linear Complementarity Problem is discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00277164
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Harvesting under density-dependent mortality and fecundity (1988)
    Springer
    Journal of mathematical biology 26 (1988), S. 193-197 
    Details
    ISSN: 1432-1416
    Keywords: Optimisation ; Leslie matrix ; Equilibrium ; Linear programming ; Nonlinear
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Mathematics
    Notes: Abstract The problem of optimal harvesting in equilibrium is considered in a Leslie matrix model in which both mortality and fecundity in all age-classes may be density-dependent. The conclusion is that the optimal strategy is of the two-age-class type, in common with results obtained previously for simpler models.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00277732
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    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
  • 55
    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
  • 56
    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
  • 57
    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
  • 58
    Electronic Resource
    Electronic Resource
    The simplex method and unrestricted variables (1985)
    Springer
    Journal of optimization theory and applications 45 (1985), S. 33-39 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; simplex method ; unrestricted variables ; simplex multipliers ; LU-factorization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940811
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    A new result in the theory and computation of the least-norm solution of a linear program (1987)
    Springer
    Journal of optimization theory and applications 55 (1987), S. 103-117 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; quadratic programming ; large-scale systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract By perturbing properly a linear program to a separable quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overrelaxation) algorithms. The main result of this paper gives an effective computational criterion to check whether the solutions of the perturbed quadratic programs provide the least-norm solution of the original linear program.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00939047
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    Generalization of Murty's direct algorithm to linear and convex quadratic programming (1989)
    Springer
    Journal of optimization theory and applications 62 (1989), S. 63-76 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; convex quadratic programming ; complementarity ; Murty's algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Murty's algorithm for the linear complementarity problem is generalized to solve the optimality conditions for linear and convex quadratic programming problems with both equality and inequality constraints. An implementation is suggested which provides both efficiency and tight error control. Numerical experiments as well as field tests in various applications show favorable results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00939630
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Eliminating columns in the simplex method for linear programming (1989)
    Springer
    Journal of optimization theory and applications 63 (1989), S. 69-77 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; simplex method ; primal and dual methods ; nonbasic variables ; column elimination
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We propose a column-eliminating technique for the simplex method of linear programming. A pricing criterion is developed for checking whether a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from further computation during the course of the simplex method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00940732
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    New trajectory-following polynomial-time algorithm for linear programming problems (1989)
    Springer
    Journal of optimization theory and applications 63 (1989), S. 433-458 
    Details
    ISSN: 1573-2878
    Keywords: Linear programming ; interior point methods ; pathfollowing methods ; polynomial-time algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00939806
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    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
  • 64
    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
  • 65
    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
  • 66
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...