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
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

5. Integer Programming

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

In this chapter, we consider linear programs with integrality constraints:

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

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

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
Vorheriges Kapitel Linear Programming Algorithms
Nächstes Kapitel Spanning Trees and Arborescences
Literatur
Bertsimas, D., and Weismantel, R. [2005]: Optimization Over Integers. Dynamic Ideas, Belmont 2005
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., and Schrijver, A. [1998]: Combinatorial Optimization. Wiley, New York 1998, Chapter 6
Jünger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G. and Wolsey, L. (Eds.) [2010]: 50 Years of Integer Programming 1958–2008. Springer, Berlin 2010
Nemhauser, G.L., and Wolsey, L.A. [1988]: Integer and Combinatorial Optimization. Wiley, New York 1988
Schrijver, A. [1986]: Theory of Linear and Integer Programming. Wiley, Chichester 1986
Wolsey, L.A. [1998]: Integer Programming. Wiley, New York 1998
Anstreicher, K.M., and Wolsey, L.A. [2009]: Two “well-known" properties of subgradient optimization. Mathematical Programming B 120 (2009), 213–220
Boyd, E.A. [1997]: A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball. Operations Research Letters 20 (1997), 59–63
Bruns, W., Gubeladze, J., Henk, M., Martin, A., and Weismantel, R. [1999]: A counterexample to an integral analogue of Carathéodory’s theorem. Journal für die Reine und Angewandte Mathematik 510 (1999), 179–185
Carr, R., and Vempala, S. [2004]: On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Mathematical Programming A 100 (2004), 569–587
Chvátal, V. [1973]: Edmonds’ polytopes and a hierarchy of combinatorial problems. Discrete Mathematics 4 (1973), 305–337
Cook, W. [1983]: Operations that preserve total dual integrality. Operations Research Letters 2 (1983), 31–35
Cook, W., Fonlupt, J., and Schrijver, A. [1986]: An integer analogue of Carathéodory’s theorem. Journal of Combinatorial Theory B 40 (1986), 63–70
Cook, W., Gerards, A.M.H., Schrijver, A., and Tardos, É. [1986]: Sensitivity theorems in integer linear programming. Mathematical Programming 34 (1986), 251–264
Cook, W., Kannan, R., and Schrijver, A. [1990]: Chvátal closures for mixed integer programming problems. Mathematical Programming 47 (1990), 155–174
Cornuéjols, G. and Li, Y. [2016]: Deciding emptiness of the Gomory-Chvátal closure is NP-complete, even for a rational polyhedron containing no integer point. In: Integer Programming and Combinatorial Optimization; Proceedings of the 18th International IPCO Conference; LNCS 9682 (Q. Louveaux, M. Skutella, eds.), Springer, Switzerland 2016, pp. 387–397
Dadush, D., Dey, S.S., and Vielma, J.P. [2014]: On the Chvátal-Gomory closure of a compact convex set. Mathematical Programming A 145 (2014), 327–348
Dantzig, G., Fulkerson, R., and Johnson, S. [1954]: Solution of a large-scale traveling-salesman problem. Operations Research 2 (1954), 393–410
Edmonds, J., and Giles, R. [1977]: A min-max relation for submodular functions on graphs. In: Studies in Integer Programming; Annals of Discrete Mathematics 1 (P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), North-Holland, Amsterdam 1977, pp. 185–204
Eisenbrand, F. [1999]: On the membership problem for the elementary closure of a polyhedron. Combinatorica 19 (1999), 297–300
Eisenbrand, F., and Schulz, A.S. [2003]: Bounds on the Chvátal rank of polytopes in the 0/1-cube. Combinatorica 23 (2003), 245–261
Fulkerson, D.R. [1971]: Blocking and anti-blocking pairs of polyhedra. Mathematical Programming 1 (1971), 168–194
Geoffrion, A.M. [1974]: Lagrangean relaxation for integer programming. Mathematical Programming Study 2 (1974), 82–114
Giles, F.R., and Pulleyblank, W.R. [1979]: Total dual integrality and integer polyhedra. Linear Algebra and Its Applications 25 (1979), 191–196
Ghouila-Houri, A. [1962]: Caractérisation des matrices totalement unimodulaires. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences (Paris) 254 (1962), 1192–1194
Goemans, M.X. [1995]: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming 69 (1995), 335–349
Goemans, M.X., and Skutella, M. [2004]: Cooperative facility location games. Journal of Algorithms 50 (2004), 194–214
Goffin, J.L. [1977]: On convergence rates of subgradient optimization methods. Mathematical Programming 13 (1977), 329–347
Gomory, R.E. [1958]: Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64 (1958), 275–278
Gomory, R.E. [1963]: An algorithm for integer solutions of linear programs. In: Recent Advances in Mathematical Programming (R.L. Graves, P. Wolfe, eds.), McGraw-Hill, New York, 1963, pp. 269–302
Graver, J.E. [1975]: On the foundations of linear and integer programming I. Mathematical Programming 9 (1975), 207–226
Harvey, W. [1999]: Computing two-dimensional integer hulls. SIAM Journal on Computing 28 (1999), 2285–2299
Hochbaum, D.S., and Levin, A. [2006]: Optimizing over consecutive 1’s and circular 1’s constraints. SIAM Journal on Optimization 17 (2006), 311–330
Hoffman, A.J. [1974]: A generalization of max flow-min cut. Mathematical Programming 6 (1974), 352–359
Hoffman, A.J., and Kruskal, J.B. [1956]: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems; Annals of Mathematical Study 38 (H.W. Kuhn, A.W. Tucker, eds.), Princeton University Press, Princeton 1956, 223–246
Lasserre, J.B. [2004]: The integer hull of a convex rational polytope. Discrete & Computational Geometry 32 (2004), 129–139
Meyer, R.R. [1974]: On the existence of optimal solutions to integer and mixed-integer programming problems. Mathematical Programming 7 (1974), 223–235
Pokutta, S., and Schulz, A.S. [2010]: On the rank of cutting-plane proof systems. In: Integer Programming and Combinatorial Optimization; Proceedings of the 14th International IPCO Conference; LNCS 6080 (F. Eisenbrand, F.B. Shepherd, eds.), Springer, Berlin 2010, pp. 450–463
Polyak, B.T. [1967]: A general method for solving extremal problems. Doklady Akademii Nauk SSSR 174 (1967), 33–36 [in Russian]. English translation: Soviet Mathematics Doklady 8 (1967), 593–597
Rothvoß, T., and Sanità, L. [2017]: 0/1 polytopes with quadratic Chvátal rank. Operations Research 65 (2017), 212–220
Schrijver, A. [1980]: On cutting planes. In: Combinatorics 79; Part II; Annals of Discrete Mathematics 9 (M. Deza, I.G. Rosenberg, eds.), North-Holland, Amsterdam 1980, pp. 291–296
Schrijver, A. [1981]: On total dual integrality. Linear Algebra and its Applications 38 (1981), 27–32
Schrijver, A. [1983]: Packing and covering of crossing families of cuts. Journal of Combinatorial Theory B 35 (1983), 104–128
Sebő, A. [1990]: Hilbert bases, Carathéodory’s theorem and combinatorial optimization. In: Integer Programming and Combinatorial Optimization (R. Kannan and W.R. Pulleyblank, eds.), University of Waterloo Press, 1990
Seymour, P.D. [1980]: Decomposition of regular matroids. Journal of Combinatorial Theory B 28 (1980), 305–359
Veinott, A.F., Jr., and Dantzig, G.B. [1968]: Integral extreme points. SIAM Review 10 (1968), 371–372
Wolsey, L.A. [1981]: The b-hull of an integer program. Discrete Applied Mathematics 3 (1981), 193–201
Metadaten
Titel
Integer Programming
verfasst von
Bernhard Korte
Jens Vygen
Copyright-Jahr
2018
Verlag
Springer Berlin Heidelberg
Buch
Combinatorial Optimization

Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-662-56039-6_5