zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
The finite criss-cross method for hyperbolic programming. (English) Zbl 0953.90055
Summary: The finite criss-cross method is generalized to solve hyperbolic (fractional linear) programming problems. Just as in the case of linear or quadratic programming the criss-cross method can be initialized with any, not necessarily feasible basic solution. It is known that if the feasible region of the problem is unbounded then some of the known algorithms fall to solve the problem. Our criss-cross algorithm does not have such drawback. Finiteness of the procedure is proved under the usual mild assumptions. Some small numerical examples illustrate the main features of the algorithm and show that our method generates different iterates than other earlier published methods.

90C32Fractional programming
90C49Extreme-point and pivoting methods
Full Text: DOI
[1] K.M. Anstreicher, Analysis of Karmarkar’s algorithm for fractional linear programming, Technical Report, (1985), November, Yale School of Management, Yale University, New Haven, CT 06520, USA
[2] Anstreicher, K. M.: A monotonic projective algorithm for fractional linear programming. Algorithmica 1, No. 4, 483-498 (1986) · Zbl 0625.90088
[3] Barros, A. I.; Dekker, R.; Frenk, J. B. G.; Van Weeren, S.: Optimizing a general replacement model by fractional programming techniques. Journal of global optimization 6, 1-19 (1997) · Zbl 0881.90112
[4] Bitran, G. R.; Novaes, A. G.: Linear programming with a fractional objective function. Operations research 21, 22-29 (1973) · Zbl 0259.90046
[5] Cambini, A.; Schaible, S.; Sodini, C.: Parametric linear fractional programming for an unbounded feasible region. Journal of global optimization 3, 157-169 (1993) · Zbl 0778.90071
[6] Charnes, A.; Cooper, W. W.: Programming with linear fractionals. Naval research quarterly 9, 181-186 (1962) · Zbl 0127.36901
[7] Craven, B. D.; Mond, B.: The dual of a fractional linear program. Journal of mathematical analysis and applications 42, 507-512 (1973) · Zbl 0259.90048
[8] B.D. Craven, Mathematical Programming and Control Theory, Chapman & Hall, London, 1978 · Zbl 0431.90039
[9] B.D. Craven, Fractional Programming, Sigma Series in Applied Mathematics, vol. 4, Heldermann Verlag, Berlin, 1988
[10] R.W. Freund, F. Jarre, An interior-point method for convex fractional programming, AT&T Numerical Analysis Manuscript No. 93-03, Bell Laboratories, Murray Hill, NJ, 1993
[11] Fukuda, K.; Terlaky, T.: Linear complementarity and oriented matroids. Journal of the operational research society of Japan 35, No. 1, 45-61 (1992) · Zbl 0773.90077
[12] Fukuda, K.; Terlaky, T.: Criss-cross method: A fresh view on pivot algorithms. Mathematical programming B 79, 369-395 (1997) · Zbl 0887.90113
[13] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting stock problem, part II, Operations Research (1963) 863--888 · Zbl 0124.36307
[14] Den Hertog, D.; Roos, C.; Terlaky, T.: The linear complementarity problem, sufficient matrices and the criss-cross method. Linear algebra and its applications 187, 1-14 (1993) · Zbl 0778.65044
[15] Klafszky, E.; Terlaky, T.: The role of pivoting in proving some fundamental theorems of linear algebra. Linear algebra and its applications 151, 97-118 (1991) · Zbl 0724.15005
[16] Klafszky, E.; Terlaky, T.: Some generalization of the criss-cross method for quadratic programming. Math. oper. U. statist. Ser. optim. 24, No. 2, 127-139 (1992) · Zbl 0814.49029
[17] Nemirovskii, A. S.: On polynomiality of the method of analytic centers for fractional problems. Mathematical programming 73, 175-198 (1996) · Zbl 0853.90107
[18] Nesterov, Yu.E.; Nemirovskii, A. S.: An interior-point method for generalized linear-fractional programming. Mathematical programming 69, 177-204 (1995) · Zbl 0857.90124
[19] B. Martos, Hiperbolikus programozás, Az MTA Matematikai Kutató Intézetének Közleményei 5 (1960) 383--406 (Published in Hungarian. English title: Hyperbolic programming)
[20] Martos, B.: Hyperbolic programming, naval research logistic quarterly. 11, 135-155 (1964) · Zbl 0131.18504
[21] B. Martos, Nem-lineáris programozási módszerek hatóköre, Az MTA Közgazdaságtudományi Intézetének Közleményei 20 (1966) (Published in Hungarian. English title: The spectrum of nonlinear programming)
[22] B. Martos, Nonlinear Programming: Theory and Methods, Akadémiai Kiadó, Budapest, 1975 · Zbl 0357.90027
[23] Mond, B.: On algorithmic equivalence in linear fractional programming. Mathematics of computation 37, 185-187 (1981) · Zbl 0472.90065
[24] Schaible, S.: Fractional programming applications and algorithms. European journal of operations research 7, 111-120 (1981) · Zbl 0452.90079
[25] S. Schaible, Fractional Programming, in: P. Pardalos, R. Horst (Eds.), Handbook of Global Optimization, Kluwer Academic Publisher, Dordrecht, 1995
[26] T. Terlaky, Egy új, véges criss-cross módszer lineáris programozási feladatok megoldására, Alkalmazott Matematikai Lapok, 10 (1984) 289--296 (Published in Hungarian. English title: A new, finite criss-cross method to solve linear programming problems)
[27] Terlaky, T.: A convergent criss-cross method. Math. oper. U. statist. Ser. optim. 16, No. 5, 683-690 (1985) · Zbl 0581.90052
[28] Terlaky, T.: A finite criss-cross method for oriented matroids. Journal of combinatorial theory B 42, 319-327 (1987) · Zbl 0588.05010
[29] Wagner, H. M.; Yuan, J. S. C.: Algorithmic equivalence in linear fractional programming. Management science 14, 301-306 (1968) · Zbl 0153.49101
[30] Wang, Zh.: A conformal elimination free algorithm for oriented matroid programming. Chinese annals of mathematics 8, B1 (1987) · Zbl 0627.90066
[31] Zionts, S.: Programming with linear fractional functionals. Naval research logistic quarterly 15, 449-451 (1968) · Zbl 0169.51301