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  (13)
  • Linear programming  (13)
  • 2000-2004
  • 1995-1999  (13)
  • 1980-1984
  • 1975-1979
  • 2002
  • 1996  (13)
  • 1982
  • 1978
  • 1977
  • Economics  (13)
Collection
  • Articles  (13)
Source
Keywords
Publisher
Years
  • 2000-2004
  • 1995-1999  (13)
  • 1980-1984
  • 1975-1979
Year
Topic
  • 1
    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
  • 2
    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
  • 3
    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
  • 4
    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
  • 5
    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
  • 6
    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
  • 7
    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
  • 8
    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
  • 9
    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
  • 10
    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
  • 11
    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
  • 12
    Electronic Resource
    Electronic Resource
    Sensitivity and stability of efficiency classifications in Data Envelopment Analysis (1996)
    Springer
    Journal of productivity analysis 7 (1996), S. 5-18 
    Details
    ISSN: 1573-0441
    Keywords: Linear programming ; data envelopment analysis ; sensitivity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Economics
    Notes: Abstract A new technique for assessing the sensitivity and stability of efficiency classifications in Data Envelopment Analysis (DEA) is presented. Here developed for the ratio (CCR) model, this technique extends easily to other DEA variants. An organization's input-outut vector serves as the center for a cell within which the organization's classification remains unchanged under perturbations of the data. For the l 1, l ∞ and generalized l ∞ norms, the radius of the maximal cell can be computed using linear programming formulations. This radius can be interpreted as a measure of the classification's stability, especially with respect to errors in the data.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00158473
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...