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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Unified Approach for Domination Problems on Different Network Topologies Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Data Correcting Approach for Routing and Location in Networks

verfasst von : Boris Goldengorin

Erschienen in: Handbook of Combinatorial Optimization

Verlag: Springer New York

Einloggen

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

search-config
loading …

Abstract

A data-correcting (DC) algorithm is a branch-and-bound-type algorithm, in which the data of a given problem is “heuristically corrected” at the various stages in such a way that the new instance will be polynomially solvable and its optimal solution is within a prespecified deviation (called prescribed accuracy) from the optimal solution to the original problem. The DC approach is applied to determining exact and approximate global optima of NP-hard problems. DC algorithms are designed for various classes of NP-hard problems including the quadratic cost partition (QCP), simple plant location (SPL), and traveling salesman problems based on the algorithmically defined polynomially solvable special cases. Results of computational experiments on the publicly available benchmark instances as well as on random instances are presented. The striking computational result is the ability of DC algorithms to find exact solutions for many relatively difficult instances within fractions of a second. For example, an exact global optimum of the QCP problem with 80 vertices and 100 % density was found within 0.22 s on a PC with 133-Mhz processor, and for the SPL problem with 200 sites and 200 clients, within 0.2 s on a PC with 733-Mhz processor.

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 Coverage Problems in Sensor Networks
Nächstes Kapitel Dual Integrality in Combinatorial Optimization
Literatur
1.
B.F. AlBdaiwi, B. Goldengorin, G. Sierksma, Equivalent instances of the simple plant location problem. Comput. Math. Appl. 57, 812–820 (2009)MathSciNetCrossRefMATH
2.
B.F. AlBdaiwi, D. Ghosh, B. Goldengorin, Data aggregation for p-median problems. J. Comb. Optimi. 21, 348–363 (2011)MathSciNetCrossRef
3.
4.
P. Avella, A. Sassano, I. Vasil’ev, Computational study of large-scale p-median problems. Math. Program. Ser. A 109, 89–114 (2007)MathSciNetCrossRefMATH
5.
E. Balas, P. Toth, Branch and bound methods, Chapter 10 in Lawler et al. [58]
6.
J.E. Beasley, Lagrangian heuristics for location problems, Eur. J. Oper. Res. 65, 383–399 (1993)CrossRefMATH
7.
8.
A.S. Belenky (ed.), Mathematical modeling of voting systems and elections: theory and applications. Math. Comput. Model. 48(9–10), 1295–1676 (2008)
9.
C. Beltran, C. Tadonki, J.-PH. Vial, Solving the p-median problem with a semi-Lagrangian relaxation. Comput. Optim. Appl. 35, 239–260 (2006)MathSciNetCrossRefMATH
10.
S. Benati, An improved branch & bound method for the uncapacitated competitive location problem. Ann. Oper. Res. 122, 43–58 (2003)MathSciNetCrossRefMATH
11.
V.L. Beresnev, On a problem of mathematical standardization theory. Upravliajemyje Sistemy 11, 43–54 (1973) (in Russian)
12.
O. Bilde, J. Krarup, Bestemmelse af optimal beliggenhed af produktionssteder, Research report, IMSOR (1967)
13.
O. Bilde, J. Krarup, Sharp lower bounds and efficient algorithms for the simple plant location problem. Ann. Discret. Math. 1, 79–97 (1977)MathSciNetCrossRef
14.
15.
16.
M.J. Brusco, H.-F. Köhn, Optimal partitioning of a data set based on the p-median problem. Psychometrika 73(1), 89–105 (2008)MathSciNetCrossRefMATH
17.
N. Christofides, Graph Theory: An Algorithmic Approach (Academic, London, 1975)MATH
18.
19.
20.
G. Cornuejols, G. Nemhauser, L.A. Wolsey, A canonical representation of simple plant location problems and its applications. SIAM J. Matrix Anal. Appl. (SIMAX) 1(3), 261–272 (1980)MathSciNetMATH
21.
G. Cornuejols, G.L. Nemhauser, L.A. Wolsey, The uncapacitated facility location problem, in Discrete Location Theory, ed. by P.B. Mirchandani, R.L. Francis (Wiley-Interscience, New York, 1990), pp. 119–171
22.
H.A. Eiselt, V. Marianov (eds.), Foundations of Location Analysis (Springer, New York/London, 2011)
23.
24.
25.
R.D. Galvão, L.A. Raggi, A method for solving to optimality uncapacitated location problems. Ann. Oper. Res. 18, 225–244 (1989)MathSciNetCrossRefMATH
26.
M.R. Garey, D.S. Johnson, Computers and Intractability (Freeman, San Francisco, 1979)MATH
27.
D. Ghosh, B. Goldengorin, G. Sierksma,, in Handbook of Combinatorial Optimization, vol. 5, ed. by D.-Z. Du, P.M. Pardalos (Springer, Berlin, 2005), pp. 1–53CrossRef
28.
D. Ghosh, B. Goldengorin, G. Sierksma, Data correcting: a methodology for obtaining near-optimal solutions, in Operations Research with Economic and Industrial Applications: Emerging Trends, ed. by S.R. Mohan, S.K. Neogy (Anamaya Publishers, New Delhi, 2005), pp. 119–127
29.
P.C. Gilmore, E.L. Lawler, D.B. Shmoys, Well-solved special cases, Chapter 4 in Lawler et al. [58]
30.
B.L. Golden, S. Raghavan, E.A. Wasil (eds.), The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York, 2010)
31.
B.I. Goldengorin, The design of optimal assortment for the vacuum diffusion welding sets. Standarty i Kachestvo 2, pp. 19–21 (1975) (in Russian)
32.
B. Goldengorin, Methods of solving multidimensional unification problems. Upravljaemye Sistemy 16, 63–72 (1977) (in Russian)MathSciNet
33.
B. Goldengorin, A correcting algorithm for solving some discrete optimization problems. Sov. Math. Dokl. 27, 620–623 (1983)
34.
B. Goldengorin, A correcting algorithm for solving allocation type problems. Autom. Remote Control 45, 590–598 (1984)MathSciNet
35.
B. Goldengorin, Correcting algorithms for solving multivariate unification problems. Sov. J. Comput. Syst. Sci. 1, 99–103 (1985)MathSciNet
36.
B. Goldengorin, On the exact solution of problems of unification by correcting algorithms. Doklady Akademii, Nauk, SSSR 294, 803–807 (1987)MathSciNet
37.
B. Goldengorin, Requirements of Standards: Optimization Models and Algorithms (Russian Operations Research, Hoogezand, 1995)
38.
B. Goldengorin, Data Correcting Algorithms in Combinatorial Optimization, Ph.D. thesis, SOM Research Institute, University of Groningen, Groningen, The Netherlands, 2002MATH
39.
B. Goldengorin, Maximization of submodular functions: theory and enumeration algorithms. Eur. J. Oper. Res. 198, 102–112 (2009)MathSciNetCrossRefMATH
40.
B. Goldengorin, D. Ghosh, The multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. Glob. Optim. 32, 65–82 (2005)MathSciNetCrossRefMATH
41.
B. Goldengorin, D. Krushinsky, Complexity evaluation of benchmark instances for the p-median problem. Math. Comput. Model. 53, 1719–1736 (2011)MathSciNetCrossRefMATH
42.
B. Goldengorin, D. Krushinsky, A computational study of the Pseudo-Boolean approach to the p-median problem applied to cell formation, in Network Optimization. Lecture Notes in Computer Science, vol. 6701 (Springer, Berlin/Heidelberg, 2011), pp. 503–516CrossRef
43.
B. Goldengorin, D. Krushinsky, J. Slomp, Flexible PMP approach for large-size cell formation. Oper. Res. 60, 1157–1166
44.
B. Goldengorin, G. Sierksma, G.A. Tijssen, M. Tso, The data-correcting algorithm for minimization of supermodular functions. Manag. Sci. 45, 1539–1551 (1999)CrossRefMATH
45.
B. Goldengorin, D. Ghosh, G. Sierksma, Branch and peg algorithms for the simple plant location problem. Comput. Oper. Res. 30, 967–981 (2003)MathSciNetCrossRefMATH
46.
B. Goldengorin, G.A. Tijssen, D. Ghosh, G. Sierksma, Solving the simple plant location problem using a data correcting approach. J. Glob. Optim. 25, 377–406 (2003)MathSciNetCrossRefMATH
47.
G. Gutin, A.P. Punnen (eds.), The Traveling Salesman Problem and its Variations (Kluwer, Dordrecht, 2002)MATH
48.
S.L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12, 450–459 (1964)CrossRefMATH
49.
S.L. Hakimi, Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper. Res. 13, 462–475 (1965)MathSciNetCrossRefMATH
50.
P.L. Hammer, Plant location – a Pseudo-Boolean approach. Isr. J. Technol. 6, 330–332 (1968)MATH
51.
52.
V.R. Khachaturov, Some Problems of the Consecutive Calculation Method and Its Applications to Location Problems, Ph.D. thesis, Central Economics and Mathematics Institute, Russian Academy of Sciences, Moscow, 1968, (in Russian)
53.
V.R. Khachaturov, Mathematical Methods of Regional Programming (Nauka, Moscow, 1989), (in Russian)MATH
54.
B.M. Khumawala, An efficient branch and bound algorithm for the warehouse location problem. Manag. Sci. 18, B718–B731 (1975)
55.
M. Körkel, On the exact solution of large-scale simple plant location problems. Eur. J. Oper. Res. 39, 157–173 (1989)CrossRefMATH
56.
Y.A. Koskosidis, W.B. Powell, Clustering algorithms for consolidation of customer orders into vehicle shipments. Transp. Res. 26B, 365–379 (1992)CrossRef
57.
A. Krause, SFO: a toolbox for submodular function optimization. J. Mach. Learn. Res. 11, 1141–1144 (2010)MATH
58.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, D.B. Shmoys (eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley-Interscience, Chichester/ New York, 1985)MATH
59.
H. Lee, G.L. Nemhauser, Y. Wang, Maximizing a submodular function by integer programming: polyhedral results for the quadratic case. Eur. J. Oper. Res. 94, 154–166 (1996)CrossRefMATH
60.
L. Lovasz, Submodular functions and convexity, in Mathematical Programming: The State of the Art, ed. by A. Bachem, M. Grötschel, B. Korte (Springer, Berlin, 1983), pp. 235–257CrossRef
61.
M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, in Actes Congres IFIP, ed. by J. Stoer (Springer, Berlin, 1977), pp. 234–243
62.
N. Mladenovic, J. Brimberg, P. Hansen, J.A. Moreno-Peréz, The p-median problem: a survey of metaheuristic approaches. Eur. J. Oper. Res. 179, 927–939 (2007)CrossRefMATH
63.
J.M. Mulvey, M.P. Beck, Solving capacitated clustering problems. Eur. J. Oper. Res. 18, 339–348 (1984)CrossRefMATH
64.
E.D. Nering, A.W. Tucker. Linear Programs and Related Problems (Academic, San Diego, 1993)
65.
66.
H. Pirkul, Efficient algorithms for the capacitated concentrator location problem. Comput. Oper. Res. 14(3), 197–208 (1987)MathSciNetCrossRefMATH
67.
68.
69.
C.S. ReVelle, R. Swain, Central facilities location. Geogr. Anal. 2, 30–42 (1970)CrossRef
70.
C.S. ReVelle, H.A. Eiselt, M.S. Daskin, A bibliography for some fundamental problem categories in discrete location science. Eur. J. Oper. Res. 184, 817–848 (2008)MathSciNetCrossRefMATH
71.
K.E. Rosing, C.S. ReVelle, H. Rosing-Vogelaar, The p-median and its linear programming relaxation: an approach to large problems. J. Oper. Res. Soc. 30, 815–822 (1979)MATH
72.
E.L.F. Senne, L.A.N. Lorena, M.A. Pereira, A branch-and-price approach to p-median location problems. Comput. Oper. Res. 32, 1655–1664 (2005)MathSciNetCrossRef
73.
74.
L. Wolsey, Mixed integer programming, in Wiley Encyclopedia of Computer Science and Engineering, ed. by B. Wah (Wiley, Chichester, 2008)
75.
Y. Won, K.C. Lee, Modified p-median approach for efficient GT cell formation. Comput. Ind. Eng. 46, 495–510 (2004)CrossRef
Metadaten
Titel
Data Correcting Approach for Routing and Location in Networks
verfasst von
Boris Goldengorin
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Handbook of Combinatorial Optimization

Print ISBN: 978-1-4419-7996-4

Electronic ISBN: 978-1-4419-7997-1

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4419-7997-1_84

Premium Partner

    Bildnachweise