ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
Filter
  • Articles  (43)
  • linear programming  (22)
  • Linear programming  (21)
  • Springer  (43)
  • American Chemical Society
  • American Institute of Physics (AIP)
  • Blackwell Publishing Ltd
  • Cambridge University Press
  • 2020-2024
  • 1990-1994  (39)
  • 1985-1989  (4)
  • 1975-1979
  • 1965-1969
  • 1940-1944
  • 1930-1934
  • 2020
  • 1993  (39)
  • 1985  (4)
  • Mathematics  (41)
  • Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition  (2)
  • Education
  • Geography
  • Energy, Environment Protection, Nuclear Power Engineering
Collection
  • Articles  (43)
Keywords
Publisher
  • Springer  (43)
  • American Chemical Society
  • American Institute of Physics (AIP)
  • Blackwell Publishing Ltd
  • Cambridge University Press
Years
  • 2020-2024
  • 1990-1994  (39)
  • 1985-1989  (4)
  • 1975-1979
  • 1965-1969
  • +
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 58 (1993), S. 243-255 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 133-150 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 151-162 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 413-420 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 60 (1993), S. 1-19 
    ISSN: 1436-4646
    Keywords: Convex programming ; linear programming ; multiplier method ; exponential penalty ; Augmented Lagrangian
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy “proximal” term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 1-14 
    ISSN: 1436-4646
    Keywords: Greedy algorithm ; Monge arrays ; series parallel graphs ; linear programming ; network flow ; transportation problem ; integrality ; convexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the concept of series and parallel composition of linear programming problems and show that greedy properties are inherited by such compositions. Our results are inspired by earlier work on compositions of flow problems. We make use of certain Monge properties as well as convexity properties which support the greedy method in other contexts.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 517-535 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    European journal of nutrition 32 (1993), S. 79-92 
    ISSN: 1436-6215
    Keywords: Lineare Programmierung ; Ernährungsoptimierung ; Privathaushalt ; Optimierungsmodelle ; Linear programming ; nutrition optimization ; private households ; optimization models
    Source: Springer Online Journal Archives 1860-2000
    Topics: Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition , Medicine
    Description / Table of Contents: Summary Members of private households have different nutrient requirements. In general, they eat the same dishes in different quantities. The menu plan is admissible if it corresponds to the recommended dietary allowances. It is acceptable if it meets the eating habits. It is optimal if it meets the constraints mentioned and best reaches an objective. It is the aim of this paper to describe models for the determination of optimal nutrition and to evaluate them with respect to their suitability for solving decision problems in private, multi-person-households. The fewer the model-intern restrictions in the variability of quantities of food stuffs, kind and/or quantities of dishes, the better are the “optimal” solutions that are found with the model. A simultaneous determination of kind and quantity of dishes reaches the model purpose better than a stepwise determination. This is shown in an example problem.
    Notes: Zusammenfassung In privaten Haushalten haben die Mitglieder unterschiedliche Nährstoffbedarfe. Sie verzehren im allgemeinen gleiche Speisen in unterschiedlichen Mengen. Der Speisenplan ist bedarfsgerecht, wenn er den Empfehlungen für die Nährstoffzufuhr der einzelnen Personen entspricht. Er ist akzeptabel, wenn er den Verzehrgewohnheiten der Personen entspricht. Er ist optimal, wenn er die genannten Bedingungen einhält und zusätzlich ein gegebenes Ziel bestmöglich erreicht. Die Bestimmung eines optimalen Speisenplans erfolgt anhand von Modellen. Es ist das Ziel des Beitrags, verschiedene Modelle zur Bestimmung einer optimalen Ernährung darzustellen und im Hinblick auf ihre Eignung zur Anwendung auf Entscheidungsprobleme im privaten Mehrpersonenhaushalt zu beurteilen. Je geringer die modellinterne Einschränkung in der Variabilität von Lebensmittelmengen, Speisenarten und/oder Speisenmengen, desto bessere ‚optimale‘ Lösungen können mit dem Modell gefunden werden. Eine simultane Bestimmung von Speisenart und -menge erfüllt den Modellzweck besser als eine sukzessive Bestimmung. Dies konnte anhand eines Beispielproblems gezeigt werden.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 23-31 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 60 (1993), S. 215-228 
    ISSN: 1436-4646
    Keywords: Primary 90C05 ; 90C33 ; Strict complementarity ; maximal complementarity ; interior point algorithms ; linear programming ; monotone complementarity problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that most interior-point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 11
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 58 (1993), S. 1-32 
    ISSN: 1436-4646
    Keywords: Interior point method ; linear programming ; quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is $$\left[ {\begin{array}{*{20}c} { - D^{ - 2} } & {A^T } \\ A & 0 \\ \end{array} } \right]$$ instead of reducing to obtain the usualAD 2 A T system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the productAD 2 A T whenA has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only thatD be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 12
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 45 (1993), S. 349-372 
    ISSN: 1572-9338
    Keywords: Incomplete market ; trading constraints ; linear programming ; optimal portfolio ; duality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We study a consistent treatment for both the multi-period portfolio selection problem and the option attainability problem by a dual approach. We assume that time is discrete, the horizon is finite, the sample space is finite and the number of securities is less than that of the possible securities price transitions, i.e. an incomplete security market. The investor is prohibited from investing stocks more than given linear investment amount constraints at any time and he maximizes an expected additive utility function for the consumption process. First we give a set of budget feasibility conditions so that a consumption process is attainable by an admissible portfolio process. To establish this relation, we used an algorithmic approach which has a close connection with the linear programming duality. Then we prove the unique existence of a primal optimal solution from the budget feasibility conditions. Finally, we formulate a dual control problem and establish the duality between primal and dual control problems.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 13
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 249-269 
    ISSN: 1572-9338
    Keywords: Convex polytopes ; degeneracy ; linear programming ; simplex method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 14
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 409-430 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 15
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 497-508 
    ISSN: 1572-9338
    Keywords: Simplex method ; linear programming ; pivoting ; degeneracy ; exterior point algorithms ; cycling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present an exterior point simplex type algorithm that possesses a new monotonic property. A dual feasible basic solution is required to start with. Intermediate solutions are neither primal nor dual feasible. Cycling-free pivoting rules and an exponentional example are presented.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 16
    ISSN: 1572-9338
    Keywords: Degeneracy/cycling ; non-Archimedean data envelopment analysis ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A non-Archimedean effective anti-degeneracy/cycling method for linear programming models, especially Data Envelopment Analysis (DEA), processing networks and advertising media mix models is herein developed. It has given a tenfold speed increase plus elimination of cycling difficulties over conventional Marsden or Kennington/Ali LP software modules in a 1000 LP DEA application.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 17
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 393-408 
    ISSN: 1572-9338
    Keywords: Degeneracy ; linear programming ; degeneracy graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Degenerate optima in linear programming problems lead in a canonical way to so-called o-degeneracy graphs as subgraphs of degeneracy graphs induced by the set of optimal bases. Fundamental questions about the structure of o-degeneracy graphs suggest the closer inspection of some properties of these graphs, such as, for example, the connectivity and the complexity. Finally, some open questions are pointed out.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 18
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 107-138 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 19
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 235-248 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 20
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 203-233 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 21
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 431-442 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 22
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 43 (1993), S. 427-441 
    ISSN: 1572-9338
    Keywords: Petroleum production ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The purpose of this paper is to describe a planning model for the management of approximately 130 petroleum-producing wells in the North Sea. The objective is to form a better basis for the decisions about which wells to produce from and which to shut down during a period. Every well is dealt with individually as the production potential and chemical composition are different. The total flow consists of six saleable components: gas, four NGL products, and oil. The production may be curtailed due to the capacities of the platforms, gathering centre, pipelines and refinery plants. The total gas production is available for fulfilling the gas contracts, injecting the gas into the reservoirs or using the gas as fuel. There exist contracts for some of the NGL products, while the rest of the NGL products and oil are sold on the free market. The well-management model is solved by means of a standard mathematical programming code, and computational results are given for a planning problem with four different data sets.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 23
    Electronic Resource
    Electronic Resource
    Springer
    Decisions in economics and finance 16 (1993), S. 73-86 
    ISSN: 1129-6569
    Keywords: project analysis ; linear programming ; internal financial law (IFL) ; financial leverage ; discounted cash-flows (DCF) decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Riassunto Si definisce un modello generale (PAULA) per la valutazione, selezione e gestione ottimale di progetti certi alternativi. Sfruttando i risvolti formali e finanziari dei problemi lineari associati (diretto e duale), si formulano poi due proposte per definire una legge finanziaria interna (IFL) ottimale, utili sia per abbattere la molteplicità intrinseca delleIFL, sia per evitare risultati economicamente arbitrari nel loro uso.
    Notes: Abstract We define a general model (called PAULA) for the valuation, optimal management and selection among mutually exclusive safe projects. By exploiting the formal and financial features of the associated linear problems (primal and dual), we put forward two proposals to define an optimal internal financial law (IFL). They may be used to reduce the multiplicity of the IFLs and to avoid economically arbitrary outcomes.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 24
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 15 (1993), S. 43-55 
    ISSN: 1436-6304
    Keywords: Modeling ; linear programming ; compiler ; MPS ; Modellierung ; lineare Programmierung ; Compiler ; MPS
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Dieser Artikel beschreibt die neue Version der Modellierungssprache LPL (Linear Programming Language), die sich dazu eignet, mathematische Modelle aufzubauen, zu warten und zu dokumentieren. Die LPL-Sprache wurde zum Erstellen von MPS-InputDateien und Resultate-Tabellen größerer LP-Modelle erfolgreich eingesetzt. Der LPL-Compiler übersetzt ein LPL-Programm, das ein vollständiges Modell repräsentiert, in den Eingabecode eines LP/MIP-Lösungsprogramms, ruft den Lösungsalgorithmus auf, liest die Lösung, und ein integrierter Tabellengenerator gibt vom Benutzer definierte Resultate-Tabellen aus. Außerdem erlaubt ein Dateneingabe-Generator, die Daten in verschiedenen Formaten zu lesen.
    Notes: Summary This paper describes the new version of the modeling language, named LPL (Linear Programming Language). It may be used to build, modify and document mathematical models. The LPL language has been successfully applied to generate automatically MPS input files and reports of large LP models. The available LPL compiler translates LPL programs to the input code of any LP/MIP solver, calls the solver automatically, reads the solution back to its internal representation, and the integrated Report Generator produces the user defined reports of the model. Furthermore, an Input Generator can read the data from many formats.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 25
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 163-213 
    ISSN: 1436-4646
    Keywords: 90C30 ; 68Q15 ; 52A25 ; 90C05 ; 90C20 ; 90C25 ; 11J72 ; 11J81 ; Computational convexity ; computational complexity ; polynomial-time algorithms ; NP-hardness ; mathematical programming ; computational geometry ; ellipsoid method ; linear programming ; sensitivity analysis ; quadratic programming ; robotics ; convex body ; polarity ; polytope ; convex hull ; breadth ; width ; diameter ; radius ; insphere ; circumsphere
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of ann-dimensional convex polytope in the space ∝ n equipped with an ℓ p norm or a polytopal norm. The polytopeP is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (ℋ-presented). The innerj-radius ofP is the radius of a largestj-ball contained inP; it isP's inradius whenj = n and half ofP's diameter whenj = 1. The outerj-radius measures how wellP can be approximated, in a minimax sense, by an (n — j)-flat; it isP's circumradius whenj = n and half ofP's width whenj = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in whichP is centrally symmetric. When the dimensionn is permitted to vary, the situation is roughly as follows: (a) for general ℋ-presented polytopes in ℓ p spaces with 1〈p〈∞, all outer radius computations are NP-hard; (b) in the remaining cases (including symmetric ℋ-presented polytopes), some radius computations can be accomplished in polynomial time and others are NP-hard. These results are obtained by using a variety of tools from the geometry of convex bodies, from linear and nonlinear programming, and from the theory of computational complexity. Applications of the results to various problems in mathematical programming, computer science and other fields are included.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 26
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 345-360 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 27
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 153-197 
    ISSN: 1436-4646
    Keywords: Complexity analysis ; interior point methods ; Karmarkar's algorithm ; linear programming ; semi-infinite programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a “potential function” by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 28
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 29
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 41-67 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 30
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 15-39 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 31
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 119-131 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 32
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 497-515 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 33
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 9 (1993), S. 64-83 
    ISSN: 1432-0541
    Keywords: Linear programming ; Interior-point methods ; Projective methods ; Combined phase 1-phase 2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 34
    ISSN: 1432-0541
    Keywords: Linear programming ; Karmarkar's algorithm ; Potential function ; Primal-dual, Modified method ; Rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider partial updating in Kojima, Mizuno, and Yoshise's primal-dual potential reduction algorithm for linear programming. We use a simple safeguard condition to control the number of updates incurred on combined primal-dual steps. Our analysis allows for unequal steplengths in the primal and dual variables, which appears to be a computationally significant factor for primal-dual methods. The safeguard we use is a primal-dual Goldstein-Armijo condition, modified to deal with the unequal primal and dual steplengths.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 35
    Electronic Resource
    Electronic Resource
    Springer
    Agroforestry systems 21 (1993), S. 169-175 
    ISSN: 1572-9680
    Keywords: Costa Rica ; cropping systems ; economics ; linear programming ; mathematical programming ; mean-variance analysis ; MOTAD ; porfolio theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract We used fluctuations in net income from alternative cropping systems to assess the financial risk associated with an agroforestry system. Mean-variance analysis was used to derive a set of minimum-risk farm plans for a 15-hectare farm in Costa Rica. Monocultural coffee production provided the highest expected net income, but also had the greatest economic risk. As risk was reduced, the optimal agroforestry system diversified to include other cropping systems in addition to the coffee monoculture. Risk aversion was, however, accompanied by significant reductions in expected net income for the cropping systems studied. The inclusion of additional cropping systems whose net incomes are negatively correlated with the systems considered here could help reduce the economic risk facing rural agriculturalists in this region.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 36
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 78 (1993), S. 127-142 
    ISSN: 1573-2878
    Keywords: Karmarkar's algorithm ; lower bounds ; linear programming ; interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We give two results related to Gonzaga's recent paper showing that lower bounds derived from the Todd-Burrell update can be obtained by solving a one-variable linear programming problem involving the centering direction and the affine direction. We show how these results may be used to update the primal solution when using the dual affine variant of Karmarkar's algorithm. This leads to a dual projective algorithm.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 37
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 78 (1993), S. 247-266 
    ISSN: 1573-2878
    Keywords: Projection methods ; Fejér contraction ; linear complementarity problems ; linear programming ; network programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear speed of convergence. The algorithms are used to solve transportation and network problems with up to 10,000 variables. Our experiments indicate that the algorithms are simple, easy to parallelize, and more efficient for some large practical problems.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 38
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 76 (1993), S. 165-182 
    ISSN: 1573-2878
    Keywords: Dynamic programming ; linear programming ; difference equations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, the general solutions to the optimal policy and the limit theorem forn-stage,m-reusableness rate production planning are obtained for the problem with free terminal point. In addition, general solutions to the problem with fixed terminal point are obtained. The links between the solutions to these problems are discussed.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 39
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 78 (1993), S. 523-539 
    ISSN: 1573-2878
    Keywords: Constrained control ; robust control ; periodic systems ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The problem is considered of finding a control strategy for a linear discrete-time periodic system with state and control bounds in the presence of unknown disturbances that are only known to belong to a given compact set. This kind of problem arises in practice in resource distribution systems where the demand has typically a periodic behavior, but cannot be estimated a priori without an uncertainty margin. An infinite-horizon keeping problem is formulated, which consists in confining the state within its constraint set using the allowable control, whatever the allowed disturbances may be. To face this problem, the concepts of periodically invariant set and sequence are introduced. They are used to formulate a solution strategy that solves the keeping problem. For the case of polyhedral state, control, and disturbance constraints, a computationally feasible procedure is proposed. In particular, it is shown that periodically invariant sequences may be computed off-line, and then they may be used to synthesize on-line a control strategy. Finally, an optimization criterion for the control law is discussed.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 40
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 5 (1985), S. 599-612 
    ISSN: 1572-9338
    Keywords: Microcomputers ; spreadsheets ; linear programming ; optimization ; software
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper discusses the advantages of using spreadsheets for problem specification and report generation in optimization projects. It summarizes some of the mathematical programming software which is compatible with popular spreadsheets. A small production planning problem is used to illustrate the steps in input and processing of the results. Two programs are compared in detail.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 41
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 46 (1985), S. 55-66 
    ISSN: 1573-2878
    Keywords: Optimal value function ; linear programming ; sensitivity analysis ; parametric programming ; multiple-objective linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Often, the coefficients of a linear programming problem represent estimates of true values of data or are subject to systematic variations. In such cases, it is useful to perturb the original data and to either compute, estimate, or otherwise describe the values of the functionf which gives the optimal value of the linear program for each perturbation. If the right-hand derivative off at a chosen point exists and is calculated, then the values off in a neighborhood of that point can be estimated. However, if the optimal solution set of either the primal problem or the dual problem is unbounded, then this derivative may not exist. In this note, we show that, frequently, even if the primal problem or the dual problem has an unbounded optimal solution set, the nature of the values off at points near a given point can be investigated. To illustrate the potential utility of our results, their application to two types of problems is also explained.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 42
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 45 (1985), S. 33-39 
    ISSN: 1573-2878
    Keywords: Linear programming ; simplex method ; unrestricted variables ; simplex multipliers ; LU-factorization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 43
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 47 (1985), S. 349-368 
    ISSN: 1573-2878
    Keywords: Respiratory physiology ; underdetermined linear systems ; least squares ; linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In recent literature, grossly underdetermined linear models have been developed for certain experimental techniques in respiratory physiology. Because physiologically sensible solutions of the models are reasonably assumed to be smooth, it is possible to recover such solutions using smoothed least-squares techniques. Bounds on the variability of smooth solutions satisfying the model can be generated using linear programming.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...