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  (156)
  • Linear programming  (156)
  • Mathematics  (153)
  • Energy, Environment Protection, Nuclear Power Engineering  (3)
  • Electrical Engineering, Measurement and Control Technology  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Farm level trade-offs of intensifying tropical milk production
    Amsterdam : Elsevier
    Ecological Economics 9 (1994), S. 121-133 
    Details
    ISSN: 0921-8009
    Keywords: Costa Rica ; Land intensification ; Linear programming ; Milk
    Source: Elsevier Journal Backfiles on ScienceDirect 1907 - 2002
    Topics: Energy, Environment Protection, Nuclear Power Engineering , Economics
    Type of Medium: Electronic Resource
    URL: http://linkinghub.elsevier.com/retrieve/pii/0921-8009(94)90094-9
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
  • 3
    Electronic Resource
    Electronic Resource
    Feasibility issues in a primal-dual interior-point method for linear programming (1990)
    Springer
    Mathematical programming 49 (1990), S. 145-162 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; primal—dual algorithms ; feasibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a “big-M”, and is shown to work well on a standard set of test problems. Conditions are developed for obtaining a near-optimal solution that is feasible for an associated problem, and details of the computational testing are presented. Other issues related to obtaining and maintaining accurate feasible solutions to linear programs with an interior-point method are discussed. These issues are important to consider when solving problems that have no primal or dual interior-point feasible solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588785
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Near boundary behavior of primal—dual potential reduction algorithms for linear programming (1993)
    Springer
    Mathematical programming 58 (1993), S. 243-255 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; primal—dual potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper is concerned with selection of theρ-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + $$\sqrt n $$ , ∞), the level ofρ determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant,ρ must be set close ton + $$\sqrt n $$ . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate thatρ can be sometimes chosen in a wide range [n + $$\sqrt n $$ , ∞) while still guaranteeing the currently best convergence rate of O( $$\sqrt n $$ L) iterations. This finding is encouraging since in practice large values ofρ have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581269
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Combining phase I and phase II in a potential reduction algorithm for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 133-150 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; combined phase I—phase II
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes an affine potential reduction algorithm for linear programming that simultaneously seeks feasibility and optimality. The algorithm is closely related to a similar method of Anstreicher. The new features are that we use a two-dimensional programming problem to derive better lower bounds than Anstreicher, that our direction-finding subproblem treats phase I and phase II more symmetrically, and that we do not need an initial lower bound. Our method also allows for the generation of a feasible solution (so that phase I is terminated) during the course of the iterations, and we describe two ways to encourage this behavior.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581241
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A quadratically convergent O( $$\sqrt n $$ L)-iteration algorithm for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 151-162 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; superlinear and quadratic convergence ; polynomiality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( $$\sqrt n $$ L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581242
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A note on the prize collecting traveling salesman problem (1993)
    Springer
    Mathematical programming 59 (1993), S. 413-420 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; prize collecting ; rounding fractional solutions ; traveling salesman problem ; worst-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581256
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Polynomiality of infeasible-interior-point algorithms for linear programming (1994)
    Springer
    Mathematical programming 67 (1994), S. 109-119 
    Details
    ISSN: 1436-4646
    Keywords: Polynomial-time ; Linear programming ; Primal-dual ; Interior-point algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm “solves” the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582216
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Comparative analysis of affine scaling algorithms based on simplifying assumptions (1991)
    Springer
    Mathematical programming 52 (1991), S. 405-414 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; potential reduction algorithm ; affine scaling algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We analyze several affine potential reduction algorithms for linear programming based on simplifying assumptions. We show that, under a strong probabilistic assumption regarding the distribution of the data in an iteration, the decrease in the primal potential function will be $$\Omega (\rho /\sqrt {log(n)} )$$ with high probability, compared to the guaranteedΩ(1). (ρ ⩾2n is a parameter in the potential function andn is the number of variables.) Under the same assumption, we further show that the objective reduction rate of Dikin's affine scaling algorithm is $$(1 - 1/\sqrt {log(n)} )$$ with high probability, compared to no guaranteed convergence rate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582897
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Global convergence of the affine scaling methods for degenerate linear programming problems (1991)
    Springer
    Mathematical programming 52 (1991), S. 377-404 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point methods ; affine scaling methods ; global analysis ; degenerate problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582896
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    A combined phase I—phase II scaled potential algorithm for linear programming (1991)
    Springer
    Mathematical programming 52 (1991), S. 429-439 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; potential function ; phase I ; phase II ; artificial variable
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We develop an extension of the affinely scaled potential reduction algorithm which simultaneously obtains feasibility and optimality in a standard form linear program, without the addition of any “M” terms. The method, and its lower-bounding procedure, are particularly simple compared with previous interior algorithms not requiring feasibility.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582899
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    An O(n 3 L) adaptive path following algorithm for a linear complementarity problem (1991)
    Springer
    Mathematical programming 52 (1991), S. 587-595 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; linear complementarity problem ; interior point algorithms ; path following algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose an O(n 3 L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n 3 L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n 3 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582906
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    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
  • 14
    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
  • 15
    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
  • 16
    Electronic Resource
    Electronic Resource
    Long steps in an O(n 3 L) algorithm for linear programming (1992)
    Springer
    Mathematical programming 54 (1992), S. 251-265 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; potential function ; standard form ; modified method ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n 3 L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous “primal-only” initialization actually reduces the complexity to less than O(m 1.5 n 1.5 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586053
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    On Anstreicher's combined phase I—phase II projective algorithm for linear programming (1992)
    Springer
    Mathematical programming 55 (1992), S. 1-15 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point method ; projective algorithm ; combining phase I–phase II
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581187
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 517-535 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; Projective algorithm ; Standard form
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve $$O\left( {\sqrt {nL} } \right)$$ step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    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
  • 20
    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
  • 21
    Electronic Resource
    Electronic Resource
    Zur Modellierung logischer Aussagen ergänzend zu Linearen Programmen (1992)
    Springer
    OR spectrum 14 (1992), S. 149-160 
    Details
    ISSN: 1436-6304
    Keywords: Lineare Programmierung ; logische Aussagen ; Binärvariablen ; Modellgenerator ; Linear programming ; predicates ; binary variables ; model generator
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Summary We introduce in the field of formulating logical predicates in addition to linear programs. The error prone process of developing linear constraints including binary variables (“auxilliary formulations”) to accomplish this leads us to discuss the possibilities and capabilities of model generation. Based on Williams [12] we develop the formulae apparatus and discuss formulation and design problems for the development of our model generator now being implemented.
    Notes: Zusammenfassung Wir geben eine Einführung in das Gebiet der Formulierung logischer Aussagen ergänzend zu Linearen Programmen. Der dazu notwendige, fehlerträchtige Prozeß der Aufstellung linearer Restriktionen unter der Verwendung von Binärvariablen („Ersatzformulierungen“) führt uns dazu, die Möglichkeiten und Fähigkeiten eines Modellgenerators für diesen Zweck zu diskutieren. Auf der Grundlage von Williams [12] entwickeln wir den Formelapparat und erörtern Formulierungs- und Entwurfsprobleme für die Entwicklung unseres sich jetzt in der Implementationsphase befindlichen Modellgenerators.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01783518
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    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
  • 23
    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
  • 24
    Electronic Resource
    Electronic Resource
    A “build-down” scheme for linear programming (1990)
    Springer
    Mathematical programming 46 (1990), S. 61-72 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex method ; ellipsoid method ; Karmarkar's algorithm ; primal and dual
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a “build-down” scheme for Karmarkar's algorithm and the simplex method for linear programming. The scheme starts with an optimal basis “candidate” setΞ including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated fromΞ. As these methods iterate,Ξ is eventually built-down to a set that contains only the optimal basic columns.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585727
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    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
  • 26
    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
  • 27
    Electronic Resource
    Electronic Resource
    Polynomial affine algorithms for linear programming (1990)
    Springer
    Mathematical programming 49 (1990), S. 7-21 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; affine algorithms ; Karmarkar's algorithm ; interior methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The method of steepest descent with scaling (affine scaling) applied to the potential functionq logc′x — ∑ i=1 n logx i solves the linear programming problem in polynomial time forq ⩾ n. Ifq = n, then the algorithm terminates in no more than O(n 2 L) iterations; if q ⩾ n + $$\sqrt n $$ withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n 4 L) and O(n 3.5 L) arithmetic computions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588776
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    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
  • 29
    Electronic Resource
    Electronic Resource
    Determination of optimal vertices from feasible solutions in unimodular linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 23-31 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; duality theorem ; unimodular ; totally unimodular ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581235
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Linear programming with spheres and hemispheres of objective vectors (1991)
    Springer
    Mathematical programming 51 (1991), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; parametric ; homeomorphisms ; spheres ; hemispheres
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a linear program with a boundedp-dimensional feasible region let the objective vector range over ans-sphere, that is, ans-dimensional sphere centered at the origin wheres does not exceedp−1. If the feasible region and the sphere are in general position with respect to each other, then the corresponding set of all optimal solutions is a topologicals-sphere. Similar results are developed for unbounded feasible regions and hemispheres of objective vectors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586923
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Random walks, totally unimodular matrices, and a randomised dual simplex algorithm (1994)
    Springer
    Mathematical programming 64 (1994), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Random walks ; Totally unimodular matrices ; Uniform generation ; Linear programming ; Diameter of polytopes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We discuss the application of random walks to generating a random basis of a totally unimodular matrix and to solving a linear program with such a constraint matrix. We also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582563
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    Dynamic factorization in large-scale optimization (1994)
    Springer
    Mathematical programming 64 (1994), S. 17-51 
    Details
    ISSN: 1436-4646
    Keywords: Factorization ; Linear programming ; Generalized upper bounds ; Pure networks ; Generalized networks
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows, and generalized network rows. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582564
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Interior-point algorithms for semi-infinite programming (1994)
    Springer
    Mathematical programming 65 (1994), S. 217-245 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Semi-infinite programming ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581697
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    The maximum entropy method on the mean: Applications to linear programming and superresolution (1994)
    Springer
    Mathematical programming 66 (1994), S. 103-122 
    Details
    ISSN: 1436-4646
    Keywords: 42B05 ; 62A99 ; Maximum entropy ; Linear programming ; Inverse problems ; Superresolution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we give two different results. We propose new methods to solve classical optimization problems in linear programming. We also obtain precise quantitative results for the superresolution phenomenon, as observed earlier by practical searchers on specific algorithms. The common background of our work is the generalized moment problem, which is known to be connected with linear programming and superresolution. We describe the Maximum Entropy Method on the Mean that provides solution to the problem and leads to computational criteria to decide the existence of solutions or not.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581139
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Superlinear convergence of infeasible-interior-point methods for linear programming (1994)
    Springer
    Mathematical programming 66 (1994), S. 361-377 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Infeasible-interior-point methods ; Superlinear convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 +τ whereτ can be arbitrarily close to one.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581155
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    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
  • 37
    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
  • 38
    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
  • 39
    Electronic Resource
    Electronic Resource
    Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices (1992)
    Springer
    Mathematical programming 57 (1992), S. 121-143 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; polynomial-time algorithms ; strongly polynomial-time algorithms ; circulant matrices ; algebraic numbers
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581077
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Limiting behavior of weighted central paths in linear programming (1994)
    Springer
    Mathematical programming 65 (1994), S. 347-363 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; (Weighted) central paths ; Limiting behavior on central paths ; Local convergence rates of interior point algorithms ; Primary: 90C05 ; Secondary: 90C33
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the limiting behavior of the weighted central paths{(x(μ), s(μ))} μ 〉 0 in linear programming at bothμ = 0 andμ = ∞. We establish the existence of a partition (B ∞,N ∞) of the index set { 1, ⋯,n } such thatx i(μ) → ∞ ands j (μ) → ∞ asμ → ∞ fori ∈ B ∞, andj ∈ N ∞, andx N∞ (μ),s B∞ (μ) converge to weighted analytic centers of certain polytopes. For allk ⩾ 1, we show that thekth order derivativesx (k) (μ) ands (k) (μ) converge whenμ → 0 andμ → ∞. Consequently, the derivatives of each order are bounded in the interval (0, ∞). We calculate the limiting derivatives explicitly, and establish the surprising result that all higher order derivatives (k ⩾ 2) converge to zero whenμ → ∞.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581702
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Asymptotic analysis of the exponential penalty trajectory in linear programming (1994)
    Springer
    Mathematical programming 67 (1994), S. 169-187 
    Details
    ISSN: 1436-4646
    Keywords: 90C05 ; 90C25 ; 90C31 ; 49M30 ; Linear programming ; Exponential penalty ; Optimal trajectory ; Asymptotic expansion ; Interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the linear program min{c′x: Ax⩽b} and the associated exponential penalty functionf r(x) = c′x + rΣexp[(A ix − bi)/r]. Forr close to 0, the unconstrained minimizerx(r) off r admits an asymptotic expansion of the formx(r) = x * + rd* + η(r) wherex * is a particular optimal solution of the linear program and the error termη(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectoryλ(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to ∞: the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582220
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    On the improvement per iteration in Karmarkar's algorithm for linear programming (1990)
    Springer
    Mathematical programming 46 (1990), S. 299-320 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar ; projective ; potential
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate the decrease in potential at an iteration of Karmarkar's projective method for linear programming. For a fixed step length parameterα (so that we must have 0 〈α ≤ 1) the best possible guaranteeδ n (α) inn dimensional space is essentially ln 2 ≃ 0.69; and to achieve this we must takeα about 1. Indeed we show the precise result thatδ n (α) equals ln(1 +α)-ln(1 −α/(n − 1)) forn sufficiently large. If we choose an optimal step length at each iteration then this guarantee increases only to aboutδ * ≃ 0.72. We also shed some light on the remarkable empirical observation that the number of iterations required seems scarcely to grow with the size of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585747
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    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
  • 44
    Electronic Resource
    Electronic Resource
    Optimal capacity in fisheries; A case where randomness is of minor importance (1984)
    Springer
    Annals of operations research 1 (1984), S. 79-83 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; stochastic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Linear programming is applied to assess the optimal capacity of the Norwegian industrial fishing fleet when quotas are random. A great potential for profit is identified and the significance of resource uncertainty for practical management is de-emphasized.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01874454
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    A strictly improving linear programming Phase I algorithm (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 409-430 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; Phase I ; nonlinear programming ; least squares ; quadratic programming ; strict improvement ; degeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called “basic”) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs. When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023107
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    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
  • 47
    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
  • 48
    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
  • 49
    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
  • 50
    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
  • 51
    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
  • 52
    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
  • 53
    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
  • 54
    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
  • 55
    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
  • 56
    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
  • 57
    Electronic Resource
    Electronic Resource
    Degeneracy in interior point methods for linear programming: a survey (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 107-138 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; interior point methods ; degeneracy ; polynomial algorithms ; global and local convergence ; basis recovery ; numerical performance ; sensitivity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02096259
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Studies of lexicography in the generalized network simplex method (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 235-248 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; generalized networks ; simplex method ; degeneracy ; lexicography ; cycling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained can help us to understand and to extend the existing theory. First, it is verified that all nonzero elements have the same sign in each row vector of a basis inverse for a generalized network (GN) problem with positive multipliers. However, this property does not necessarily hold when there exist negative multipliers. Second, we developed a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive andnegative multipliers. This strategy is also based on lexicography and requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step isO(n) in the worst case. This worst case effort is the same as that required by the strongly convergent rules for selecting the dropping arc in the method of strong convergence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023097
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    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
  • 60
    Electronic Resource
    Electronic Resource
    MODLER: Modeling by object-driven linear elemental relations (1992)
    Springer
    Annals of operations research 38 (1992), S. 239-280 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; large-scale systems ; modeling ; language design
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper describes a system to represent linear programming models and their instances. In addition to a modeling language, MODLER has an extensive query capability which includes a multi-view architecture. Further, randomization options provide rapid prototyping. The MODLER system is part of a workbench for building and managing decision support systems that are based on linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283655
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    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
  • 62
    Electronic Resource
    Electronic Resource
    Pivot rules for linear programming: A survey on recent theoretical developments (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 203-233 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; simplex method ; pivot rules ; cycling ; recursion ; minimal index rule ; parametric programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed. In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02096264
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    A practical anti-degeneracy row selection technique in network linear programming (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 431-442 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; degeneracy ; network simplex algorithm ; pivoting ; minimal cost network flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023108
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    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
  • 65
    Electronic Resource
    Electronic Resource
    A procedure for parameterizing a constraint in linear programming (1973)
    Springer
    BIT 13 (1973), S. 355-369 
    Details
    ISSN: 1572-9125
    Keywords: Linear programming ; parametric linear programming ; pivotal operation ; Jordan elimination
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A post-optimal procedure for parameterizing a constraint in linear programming is proposed. In the derivation of the procedure, the technique of pivotal operations (Jordan eliminations) is applied. The procedure is compared to another by Orchard-Hays [2], and a numerical example of the procedure is provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01951946
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    A procedure for one-parametric linear programming (1979)
    Springer
    BIT 19 (1979), S. 256-269 
    Details
    ISSN: 1572-9125
    Keywords: Linear programming ; parametric linear programming ; pivotal operation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linear programming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01930856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Productive efficiency in a regulated industry
    Amsterdam : Elsevier
    Energy Economics 13 (1991), S. 116-122 
    Details
    ISSN: 0140-9883
    Keywords: Electricity distribution ; Linear programming ; Technical efficiency
    Source: Elsevier Journal Backfiles on ScienceDirect 1907 - 2002
    Topics: Energy, Environment Protection, Nuclear Power Engineering , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1016/0140-9883(91)90043-Y
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Productive efficiency in a regulated industry - The area electricity boards of England and Wales
    Amsterdam : Elsevier
    Energy Economics 13 (1991), S. 116-122 
    Details
    ISSN: 0140-9883
    Keywords: Electricity distribution ; Linear programming ; Technical efficiency
    Source: Elsevier Journal Backfiles on ScienceDirect 1907 - 2002
    Topics: Energy, Environment Protection, Nuclear Power Engineering , Economics
    Type of Medium: Electronic Resource
    URL: http://linkinghub.elsevier.com/retrieve/pii/0140-9883(91)90043-Y
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    The alternating basis algorithm for assignment problems (1977)
    Springer
    Mathematical programming 13 (1977), S. 1-13 
    Details
    ISSN: 1436-4646
    Keywords: Assignment problems ; Linear programming ; Manpower planning ; Networks ; Personnel assignment ; Transportation problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (“simplex”) methods for assignment problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584319
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    On the Bartels—Golub decomposition for linear programming bases (1977)
    Springer
    Mathematical programming 13 (1977), S. 272-279 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Basis matrix ; LU factorization ; Pricing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many implementations of the simplex method require the row of the inverse of the basis matrixB corresponding to the pivot row at each iteration for updating either a pricing vector or the nonbasic reduced costs. In this note we show that if the Bartels—Golub algorithm [1, 2] or one of its variants is used to update theLU factorization ofB, then less computing is needed if one works with the factors of the updatedB than with those ofB. These results are discussed as they apply to the column selection algorithms recently proposed by Goldfarb and Reid [4, 5] and Harris [6].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584343
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results (1977)
    Springer
    Mathematical programming 13 (1977), S. 280-322 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Integer programming ; Mixed integer programming ; Large scale programming ; Branch and bound ; Triangular factorization ; etc. Sparse matrix methods ; Degeneracy ; Numerical stability ; Computational results ; Mathematical programming language
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract First, this paper presents the results of experiments with algorithmic techniques for efficiently solving medium and large scale linear and mixed integer programming problems. The techniques presented here are either original or recent. The solution of a great number of problems has shown that efficient problem solving requires automatic adaptation of algorithmic techniques upon problem characteristics. We show when a given technique should be used for a particular problem. The last part of this paper describes an attempt to provide a powerful mathematical programming language, allowing an easy programming of specific studies on medium-size models such as the recursive use of LP or the build-up of algorithms based on the simplex method. All these features have been implemented in the IBM Mathematical Programming System, MPSX/370, and its feature MIP/370. Extensive numerical results and comparisons on real-life problems are provided and commented upon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584344
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    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
  • 73
    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
  • 74
    Electronic Resource
    Electronic Resource
    An exponential example for Terlaky's pivoting rule for the criss-cross simplex method (1990)
    Springer
    Mathematical programming 46 (1990), S. 79-84 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; pivoting rule ; Gray code
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently T. Terlaky has proposed a new pivoting rule for the criss-cross simplex method for linear programming and he proved that his rule is convergent. In this note we show that the required number of iterations may be exponential in the number of variables and constraints of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585729
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    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
  • 76
    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
  • 77
    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
  • 78
    Electronic Resource
    Electronic Resource
    Karmarkar's algorithm with improved steps (1990)
    Springer
    Mathematical programming 46 (1990), S. 73-78 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. We use this function to obtain data-dependent steps for Karmarkar's algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. We analyze the general step and consider its potential practical advantages.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585728
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Containing and shrinking ellipsoids in the path-following algorithm (1990)
    Springer
    Mathematical programming 47 (1990), S. 1-9 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; convex quadratic programming ; path-following algorithm ; Karmarkar's algorithm ; ellipsoid method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio $$2^{ - \Omega (\sqrt n )} $$ , in comparison to 2−Ω(1) in Karmarkar's algorithm and 2−Ω(1/n) in the ellipsoid method. We also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580848
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm (1990)
    Springer
    Mathematical programming 47 (1990), S. 337-351 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; projective algorithm ; modified method ; standard form ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In his original analysis of the projective algorithm for linear programming, Karmarkar proposed a “modified method” which improved the worst-case arithmetic complexity of the original algorithm by a factor of $$\sqrt n $$ . Karmarkar's analysis of the $$\sqrt n $$ improvement is based on a primal-dual formulation, and requires that small steps be taken on each iteration. However, in practice the original algorithm can be easily applied to standard form problems, and is considerably improved by performing a linesearch on each iteration, generally leading to much larger steps. We show here that by incorporating a simple safeguard, a linesearch may be performed in the modified algorithm while retaining the $$\sqrt n $$ complexity improvement over the original algorithm. We then show that the modified algorithm, with safeguarded linesearch, can be applied directly to a standard form linear program with unknown optimal objective value. The resulting algorithm enjoys a $$\sqrt n $$ complexity advantage over standard form variants of the original algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580868
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    An active-set strategy in an interior point method for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 345-360 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point method ; active set strategy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed “active constraints”—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( $$\sqrt n $$ L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581252
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    An O(n 3 L) potential reduction algorithm for linear programming (1991)
    Springer
    Mathematical programming 50 (1991), S. 239-258 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; interior algorithms ; potential functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe a primal-dual potential function for linear programming: $$\phi (x,s) = \rho \ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j s_j )} $$ whereρ⩾ n, x is the primal variable, ands is the dual-slack variable. As a result, we develop an interior point algorithm seeking reductions in the potential function with $$\rho = n + \sqrt n $$ . Neither tracing the central path nor using the projective transformation, the algorithm converges to the optimal solution set in $$O(\sqrt n L)$$ iterations and uses O(n 3 L) total arithmetic operations. We also suggest a practical approach to implementing the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01594937
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    A quadratically convergent predictor—corrector method for solving linear programs from infeasible starting points (1994)
    Springer
    Mathematical programming 67 (1994), S. 383-406 
    Details
    ISSN: 1436-4646
    Keywords: 90C05 ; Linear programming ; Primal—dual ; Polynomial complexity ; Infeasible ; Interior-point ; Exterior-point
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A predictor—corrector method for solving linear programs from infeasible starting points is analyzed. The method is quadratically convergent and can be combined with Ye's finite termination scheme under very general assumptions. If the starting points are large enough then the algorithm hasO(nL) iteration complexity. If the ratio between feasibility and optimality at the starting points is small enough then the algorithm has O( $$\sqrt {n L} $$ ) iteration complexity. For feasible starting points the algorithm reduces to the Mizuno—Todd—Ye predictor—corrector method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582228
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Improving the rate of convergence of interior point methods for linear programming (1991)
    Springer
    Mathematical programming 52 (1991), S. 467-479 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; polynomial methods ; interior point methods ; rate of convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( $$\bar x^k$$ ). Under the suitable assumptions it is shown that the sequence ( $$\bar x^k$$ ) converges superlinearly faster to the solution than (x k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582901
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    A simplex algorithm for piecewise-linear programming III: Computational analysis and applications (1992)
    Springer
    Mathematical programming 53 (1992), S. 213-235 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex methods ; piecewise-linear programming ; nondifferentiable optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewiselinear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustarate these arguments; the piecewise-linear simplex algorithm is observed to run 2–6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585703
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    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
  • 87
    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
  • 88
    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
  • 89
    Electronic Resource
    Electronic Resource
    A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio (1993)
    Springer
    Mathematical programming 61 (1993), S. 39-52 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; quadratic programming ; convex programming ; randomized algorithms ; fixed dimension optimization problems ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = Ω(d 2), the expected total number of major Karmarkar's iterations is O(d 2(logn)L), compared to the best known deterministic bound of O( $$\sqrt n$$ L). We also present several other results which follow from the general scheme.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582137
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Load balancing in the parallel optimization of block-angular linear programs (1993)
    Springer
    Mathematical programming 62 (1993), S. 41-67 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Dantzig—Wolfe decomposition ; large-scale systems ; parallel processing ; hypercube architecture
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Decomposition algorithms for block-angular linear programs give rise to a natural, coarse-grained parallelism that can be exploited by processing the subproblems concurrently within a distributed-memory environment. The parallel efficiency of the distributed approach, however, is critically dependent on the duration of the inherently serial master phase relative to that of the bottleneck subproblem. This paper investigates strategies for improving efficiency in distributed Dantzig—Wolfe decomposition by better balancing the load between the master and subproblem processors. We report computational experience on an Intel iPSC/2 hypercube multiprocessor with test problems having dimensions up to about 30 000 rows, 87 000 columns, and 200 coupling constraints.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585159
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Solving symmetric indefinite systems in an interior-point method for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 15-39 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; symmetric indefinite systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite “augmented” systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite “normal equations” that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585158
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    A primal—dual affine-scaling potential-reduction algorithm for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 119-131 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; complexity ; potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585163
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    Finding an interior point in the optimal face of linear programs (1993)
    Springer
    Mathematical programming 62 (1993), S. 497-515 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal—dual methods ; optimal face ; strict complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n 3 L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Constant potential primal—dual algorithms: A framework (1994)
    Springer
    Mathematical programming 66 (1994), S. 145-159 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Interior point methods ; Primal—dual algorithms ; Potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We start with a study of the primal—dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al., Mizuno and Nagasawa, and new potential functions we establish a framework for primal—dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. Our algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581142
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    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
  • 96
    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
  • 97
    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
  • 98
    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
  • 99
    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
  • 100
    Electronic Resource
    Electronic Resource
    Thek-server dual and loose competitiveness for paging (1994)
    Springer
    Algorithmica 11 (1994), S. 525-541 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; k-Server problem ; Linear programming ; Approximation algorithms ; Paging ; Caching ; Competitive analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Weighted caching is a generalization ofpaging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-knownk-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled. We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holdingk items, incurs a cost within a factor ofk/(k−h+1) of the minimum cost possible given a cache holdingh items. The strategy generalizes “least recently used,” one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of thek-server problem. We introduceloose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. Ak-server strategy isloosely c(k)-competitive if, for any sequence, foralmost all k, the cost incurred by the strategy withk serverseither is no more thanc(k) times the minimum costor is insignificant. We show that certain paging strategies (including “least recently used,” and “first in first out”) that arek-competitive in the standard model are looselyc(k)-competitive providedc(k)/Ink→∞ and bothk/c(k) andc(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is Θ(Ink)-competitive in the standard model, is looselyc(k)-competitive providedk−2 In Ink→∞ and both 2 Ink−c(k) andc(k) are nondecreasing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189992
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...