Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Jahresbericht der Deutschen Mathematiker-Vereinigung
Erschienen in: Jahresbericht der Deutschen Mathematiker-Vereinigung 4/2012

01.12.2012 | Survey Article

Foundations of Discrete Optimization: In Transition from Linear to Non-linear Models and Methods

verfasst von: Jesús A. De Loera, Raymond Hemmecke, Matthias Köppe

Erschienen in: Jahresbericht der Deutschen Mathematiker-Vereinigung | Ausgabe 4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Optimization is a vibrant growing area of Applied Mathematics. Its many successful applications depend on efficient algorithms and this has pushed the development of theory and software. In recent years there has been a resurgence of interest to use “non-standard” techniques to estimate the complexity of computation and to guide algorithm design. New interactions with fields like algebraic geometry, representation theory, number theory, combinatorial topology, algebraic combinatorics, and convex analysis have contributed non-trivially to the foundations of computational optimization. In this expository survey we give three example areas of optimization where “algebraic-geometric thinking” has been successful. One key point is that these new tools are suitable for studying models that use non-linear constraints together with combinatorial conditions.
Vorheriger Artikel Preface Issue 4-2012
Nächster Artikel In Memoriam Horst Tietz (1921–2012)

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Jahresbericht der Deutschen Mathematiker-Vereinigung

Der „Jahresbericht der Deutschen Mathematiker-Vereinigung (DMV)“ versteht sich als ein Schaufenster für Mathematik. In Übersichtsartikeln und Berichten aus der Forschung soll für möglichst viele LeserInnen verständlich und interessant über aktuelle und wichtige Entwicklungen der Mathematik berichtet werden.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Weitere Produktempfehlungen anzeigen
Literatur
1.
Adler, I., Dantzig, G.B.: Maximum diameter of abstract polytopes. Math. Program. Stud. 1, 20–40 (1974). Pivoting and extensions MathSciNetCrossRef
2.
Adler, I., Dantzig, G.B., Murty, K.: Existence of A-avoiding paths in abstract polytopes. Math. Program. Stud. 1, 41–42 (1974). Pivoting and extensions MathSciNetCrossRef
3.
Adams, W.W., Loustaunau, Ph.: An Introduction to Gröbner Bases. Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence (1994) MATH
4.
5.
Barvinok, A.I.: Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19, 769–779 (1994) MathSciNetMATHCrossRef
6.
Bachem, A., Kern, W.: Linear Programming Duality: An Introduction to Oriented Matroids (Universitext). Springer, Berlin (1992) MATH
7.
Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories. Trans. Am. Math. Soc. 314(2), 499–526 (1989) MathSciNetMATH
8.
Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories. Trans. Am. Math. Soc. 314(2), 527–581 (1989) MathSciNetMATH
9.
Billera, L., Provan, S.: Decompositions of simplicial complexes related to diameters of convex polyhedra. Math. Oper. Res. 5(4), 576–594 (1980) MathSciNetMATHCrossRef
10.
Barvinok, A.I., Pommersheim, J.E.: An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics, Berkeley, CA, 1996–97. Math. Sci. Res. Inst. Publ., vol. 38, pp. 91–147. Cambridge University Press, Cambridge (1999)
11.
Brion, M.: Points entiers dans les polyédres convexes. Ann. Sci. Éc. Norm. Super. 21(4), 653–663 (1988) MathSciNetMATH
12.
Barvinok, A.I., Woods, K.: Short rational generating functions for lattice point problems. J. Am. Math. Soc. 16(4), 957–979 (2003) (electronic) MathSciNetMATHCrossRef
13.
Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York (1992) MATH
14.
Conti, P., Traverso, C.: Buchberger algorithm and integer programming. In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, New Orleans, LA, 1991. LNCS, vol. 539, pp. 130–139. Springer, Berlin (1991) CrossRef
15.
Dyer, M., Kannan, R.: On Barvinok’s algorithm for counting lattice points in fixed dimension. Math. Oper. Res. 22(3), 545–549 (1997) MathSciNetMATHCrossRef
16.
De Loera, J.A., Hemmecke, R., Köppe, M.: Algebraic and Geometric Ideas in the Theory of Discrete Optimization. SIAM-MOS Series on Optimization, vol. 14. SIAM, Philadelphia (2012, to appear), ISBN 9781611972436
17.
De Loera, J.A., Hemmecke, R., Köppe, M., Weismantel, R.: Integer polynomial optimization in fixed dimension. Math. Oper. Res. 31(1), 147–153 (2006) MathSciNetMATHCrossRef
18.
De Loera, J.A., Klee, S.: Transportation problems and simplicial polytopes that are not weakly vertex-decomposable. Math. Oper. Res. (2012, to appear)
19.
De Loera, J.A., Sturmfels, B., Vinzant, C.: The central curve in linear programming. Found. Comput. Math. (2012, to appear)
20.
Dedieu, J.-P., Malajovich, G., Shub, M.: On the curvature of the central path of linear programming theory. Found. Comput. Math. 5(2), 145–171 (2005) MathSciNetMATHCrossRef
21.
Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), Oct. 2011, pp. 580–589 (2011) CrossRef
22.
Deza, A., Terlaky, T., Zinchenko, Y.: Polytopes and arrangements: diameter and curvature. Oper. Res. Lett. 36(2), 215–222 (2008) MathSciNetMATHCrossRef
23.
Deza, A., Terlaky, T., Zinchenko, Y.: Central path curvature and iteration-complexity for redundant Klee-Minty cubes. In: Advances in Applied Mathematics and Global Optimization. Advances in Mechanics and Mathematics, vol. 17, pp. 223–256. Springer, New York (2009) CrossRef
24.
Deza, A., Terlaky, T., Zinchenko, Y.: A continuous d-step conjecture for polytopes. Discrete Comput. Geom. 41(2), 318–327 (2009) MathSciNetMATHCrossRef
25.
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22, 425–460 (2000) MathSciNetMATHCrossRef
26.
Eisenbrand, F., Hähnle, N., Razborov, A., Rothvoß, T.: Diameter of polyhedra: limits of abstraction. Math. Oper. Res. 35(4), 786–794 (2010) MathSciNetMATHCrossRef
27.
Emelichev, V.A., Perepelitsa, V.A.: On the cardinality of the set of alternatives in discrete many-criterion problems. Discrete Math. Appl. 2, 461–471 (1992) MathSciNet
28.
Frank, A., Tardos, É.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987) MathSciNetMATHCrossRef
29.
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Berlin (1988) MATHCrossRef
30.
Hačijan, L.G.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 244(5), 1093–1096 (1979) MathSciNet
31.
32.
Hildebrand, R., Köppe, M.: A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity 2 O(nlogn). Discrete Optim. (2012, to appear). arXiv:​1006.​4661 [math.OC]
33.
Hemmecke, R., Köppe, M., Weismantel, R.: A polynomial-time algorithm for optimizing over n-fold 4-block decomposable integer programs. In: Proceedings of 15th Integer Programming and Combinatorial Optimization (IPCO 2010). LNCS, vol. 6080, pp. 219–229. Springer, Berlin (2010) CrossRef
34.
Hemmecke, R., Onn, S., Weismantel, R.: A polynomial oracle-time algorithm for convex integer minimization. Math. Program. 126(1, Ser. A), 97–117 (2011) MathSciNetMATHCrossRef
35.
Hoşten, S., Sullivant, S.: A finiteness theorem for Markov bases of hierarchical models. J. Comb. Theory, Ser. A 114(2), 311–321 (2007) MATHCrossRef
36.
Hoşten, S., Thomas, R.R.: Gröbner bases and integer programming. In: Gröbner Bases and Applications, Linz, 1998. London Mathematical Society Lecture Note Series, vol. 251, pp. 144–158. Cambridge University Press, Cambridge (1998)
37.
38.
Jünger, M., Liebling, Th.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.): 50 Years of Integer Programming 1958–2008. From the Early Years to the State-of-the-Art. Springer, Berlin (2010) MATH
39.
Kalai, G.: Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput. Geom. 8(4), 363–372 (1992) MathSciNetMATHCrossRef
40.
Khachiyan, L.G.: Convexity and complexity in polynomial programming. In: Ciesielski, Z., Olech, C. (eds.) Proceedings of the International Congress of Mathematicians, Warszawa, 16–24 August 1983, pp. 1569–1577. North-Holland, New York (1984)
41.
Khinchin, A.: A quantitative formulation of Kronecker’s theory of approximation. Izv. Akad. Nauk SSSR, Math 12, 113–122 (1948) (in Russian) MathSciNetMATH
42.
43.
Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull., New Ser., Am. Math. Soc. 26(2), 315–316 (1992) MathSciNetMATHCrossRef
44.
Khachiyan, L., Porkolab, L.: Integer optimization on convex semialgebraic sets. Discrete Comput. Geom. 23(2), 207–224 (2000) MathSciNetMATHCrossRef
45.
46.
47.
48.
Lee, J., Leyffer, S. (eds.): Non Linear Mixed Integer Optimization. The IMA Volumes in Mathematics and Its Applications, vol. 154. Springer, Berlin (2012)
49.
Lenstra, A.K., Lenstra, H.W., Jr., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982) MathSciNetMATHCrossRef
50.
Monteiro, R.D.C., Tsuchiya, T.: A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms. Math. Program. 115(1, Ser. A), 105–149 (2008) MathSciNetMATHCrossRef
51.
52.
Onn, S.: Nonlinear discrete optimization. In: An Algorithmic Theory. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zurich (2010)
53.
54.
Roos, C., Terlaky, T., Vial, J.-P.: Interior Point Methods for Linear Optimization. Springer, New York (2006). Second Edition of ıt Theory and Algorithms for Linear Optimization. Wiley, Chichester (1997). MR1450094 MATH
55.
Santos, F.: On a counterexample to the Hirsch conjecture. Preprint (2010, to appear) Ann. Math. 27 p. Available as arXiv:​1006.​2814
56.
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986) MATH
57.
Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Vol. A: Paths, Flows, Matchings. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003). Chaps. 1–38
58.
Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003). Chaps. 39–69
59.
Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Vol. C: Disjoint Paths, Hypergraphs. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003). Chaps. 70–83
60.
Sergienko, I.V., Perepelitsa, V.A.: Finding the set of alternatives in discrete multi-criterion problems. Cybernetics 3, 673–683 (1991)
61.
62.
Sonnevend, G., Stoer, J., Zhao, G.: On the complexity of following the central path of linear programs by linear extrapolation. II. Math. Program. 52(3, Ser. B), 527–553 (1992). 1991. Interior point methods for linear programming: theory and practice (Scheveningen, 1990) MathSciNetCrossRef
63.
Stanley, R.P.: Enumerative Combinatorics, Vol. 1. Cambridge University Press, Cambridge (1997) MATHCrossRef
64.
65.
Vanderbei, R.J.: Linear Programming: Foundations and Extensions, 3rd edn. International Series in Operations Research & Management Science, vol. 114. Springer, New York (2008) MATH
66.
Vavasis, S.A., Ye, Y.: A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Program. 74(1, Ser. A), 79–120 (1996) MathSciNetMATHCrossRef
67.
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995) MATHCrossRef
68.
Zhao, G., Stoer, J.: Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals. Appl. Math. Optim. 27(1), 85–103 (1993) MathSciNetMATHCrossRef
Metadaten
Titel
Foundations of Discrete Optimization: In Transition from Linear to Non-linear Models and Methods
verfasst von
Jesús A. De Loera
Raymond Hemmecke
Matthias Köppe
Publikationsdatum
01.12.2012
Verlag
Springer-Verlag
Erschienen in
Jahresbericht der Deutschen Mathematiker-Vereinigung / Ausgabe 4/2012
Print ISSN: 0012-0456
Elektronische ISSN: 1869-7135
DOI
https://doi.org/10.1365/s13291-012-0055-x

Weitere Artikel der Ausgabe 4/2012

Jahresbericht der Deutschen Mathematiker-Vereinigung 4/2012 Zur Ausgabe

Preface

Preface Issue 4-2012

Historical Article

In Memoriam Horst Tietz (1921–2012)

Book Review

Peter Schneider: “p-Adic Lie Groups”

Book Review

Matilde Marcolli: Feynman Motives

Book Review

Jeffrey Strom: “Modern Classical Homotopy Theory”

Premium Partner

    Bildnachweise