Exact and memetic algorithms for two network design problems / Ivana Ljubić
ger: This thesis focuses on two NP-hard network design problems:<br />the first one, vertex biconnectivity augmentation (V2AUG), appears in the design of survivable communication or electricity networks. In this problem we search for the set of connections of minimal total cost which, when add...
Saved in:
VerfasserIn: | |
---|---|
Place / Publishing House: | 2004 |
Year of Publication: | 2004 |
Language: | English |
Subjects: | |
Classification: | 54.62 - Datenstrukturen 54.80 - Angewandte Informatik 54.72 - Künstliche Intelligenz 54.51 - Programmiermethodik |
Online Access: | |
Physical Description: | V, 177 S.; Ill., graph. Darst. |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
990000945800504498 |
---|---|
ctrlnum |
AC04351739 (AT-OBV)AC04351739 (Aleph)004338543ACC01 (DE-599)OBVAC04351739 (EXLNZ-43ACC_NETWORK)990043385430203331 |
collection |
bib_alma |
institution |
YWOAW |
building |
MAG1-3 |
record_format |
marc |
spelling |
Ljubić, Ivana aut Exact and memetic algorithms for two network design problems Ivana Ljubić 2004 V, 177 S. Ill., graph. Darst. Wien, Techn. Univ., Diss., 2004 ger: This thesis focuses on two NP-hard network design problems:<br />the first one, vertex biconnectivity augmentation (V2AUG), appears in the design of survivable communication or electricity networks. In this problem we search for the set of connections of minimal total cost which, when added to the existing network, makes it survivable against failures of any single node. The second problem, the prize-collecting Steiner tree problem (PCST), describes a natural trade-off between maximizing the sum of profits over all selected customers and minimizing the implementation costs, e.g.<br />when designing a fiber optic or a district heating network.<br />We provide exact algorithms based on the branch-and-cut technique that can solve given network design problems of respectable size to provable optimality. For fairly large instances, we propose heuristic tools that obtain suboptimal, high quality solutions of practical relevance. Fractional bounds obtained by means of exact methods are therefore used as a measure of quality of obtained heuristic solution.<br />As a heuristic tool, we choose memetic algorithms (MAs), a symbiosis of evolutionary and neighborhood search algorithms. Our memetic algorithms comprise new representation techniques, search operators,constraint handling techniques and local-improvement strategies. Our exact algorithms are based on the state-of-the-art in polyhedral combinatorics. They rely on sophisticated separation algorithms or advanced column generation methods.<br />In this thesis, we also investigate some possibilities of combining promising variants of exact algorithms and MAs, e.g. incorporating exact algorithms that solve some special cases within MAs, or guiding column generation using MA results. In extensive computational studies our exact and memetic algorithms show their superiority compared to the previously published results. For many of V2AUG and PCST instances, we are the first to find provably optimalsolutions.<br /> eng: Abstract nicht verfügbar Kombinatorische Optimierung s (DE-588)4031826-6 NP-hartes Problem s (DE-588)4621705-8 Netzwerk s (DE-588)4171529-9 Algorithmus s (DE-588)4001183-5 AT-OBV ONBREB Steiner-Problem s (DE-588)4248342-6 Erscheint auch als Online-Ausgabe urn:nbn:at:at-ubtuw:1-13664 20.500.12708/9557 text/html http://hdl.handle.net/20.500.12708/9557 TUW kostenfrei Volltext In Copyright 0 V:AT-OBV;B:AT-TUW application/pdf http://media.obvsg.at/AC04351739-2001 TUW Volltext OBV-EDOC YWOAW MAG1-3 33255-C.Stip. 2213472760004498 |
language |
English |
format |
Thesis Book |
author |
Ljubić, Ivana |
spellingShingle |
Ljubić, Ivana Exact and memetic algorithms for two network design problems Kombinatorische Optimierung (DE-588)4031826-6 NP-hartes Problem (DE-588)4621705-8 Netzwerk (DE-588)4171529-9 Algorithmus (DE-588)4001183-5 Steiner-Problem (DE-588)4248342-6 |
author_facet |
Ljubić, Ivana |
author_variant |
i l il |
author_role |
VerfasserIn |
author_sort |
Ljubić, Ivana |
title |
Exact and memetic algorithms for two network design problems |
title_full |
Exact and memetic algorithms for two network design problems Ivana Ljubić |
title_fullStr |
Exact and memetic algorithms for two network design problems Ivana Ljubić |
title_full_unstemmed |
Exact and memetic algorithms for two network design problems Ivana Ljubić |
title_auth |
Exact and memetic algorithms for two network design problems |
title_new |
Exact and memetic algorithms for two network design problems |
title_sort |
exact and memetic algorithms for two network design problems |
publishDate |
2004 |
physical |
V, 177 S. Ill., graph. Darst. |
callnumber-raw |
33255-C.Stip. |
callnumber-search |
33255-C.Stip. |
topic |
Kombinatorische Optimierung (DE-588)4031826-6 NP-hartes Problem (DE-588)4621705-8 Netzwerk (DE-588)4171529-9 Algorithmus (DE-588)4001183-5 Steiner-Problem (DE-588)4248342-6 |
topic_facet |
Kombinatorische Optimierung NP-hartes Problem Netzwerk Algorithmus Steiner-Problem |
url |
http://hdl.handle.net/20.500.12708/9557 http://media.obvsg.at/AC04351739-2001 |
illustrated |
Illustrated |
work_keys_str_mv |
AT ljubicivana exactandmemeticalgorithmsfortwonetworkdesignproblems |
status_str |
n |
ids_txt_mv |
(AT-OBV)AC04351739 AC04351739 (Aleph)004338543ACC01 (DE-599)OBVAC04351739 (EXLNZ-43ACC_NETWORK)990043385430203331 |
hol852bOwn_txt_mv |
YWOAW |
hol852hSignatur_txt_mv |
33255-C.Stip. |
hol852cSonderstandort_txt_mv |
MAG1-3 |
itmData_txt_mv |
2005-07-18 02:00:00 Europe/Vienna |
barcode_str_mv |
+YW6006401 |
callnumbers_txt_mv |
33255-C.Stip. |
inventoryNumbers_str_mv |
33255-C.Stip. |
materialTypes_str_mv |
BOOK |
permanentLibraries_str_mv |
YWOAW |
permanentLocations_str_mv |
MAG1-3 |
inventoryDates_str_mv |
20050718 |
createdDates_str_mv |
2005-07-18 02:00:00 Europe/Vienna |
holdingIds_str_mv |
2213472760004498 |
is_hierarchy_id |
AC04351739 |
is_hierarchy_title |
Exact and memetic algorithms for two network design problems |
basiskl_str_mv |
54.62 - Datenstrukturen 54.80 - Angewandte Informatik 54.72 - Künstliche Intelligenz 54.51 - Programmiermethodik |
basiskl_txtF_mv |
54.62 - Datenstrukturen 54.80 - Angewandte Informatik 54.72 - Künstliche Intelligenz 54.51 - Programmiermethodik |
_version_ |
1806550078995824640 |
fullrecord |
<?xml version="1.0" encoding="UTF-8"?><collection xmlns="http://www.loc.gov/MARC21/slim"><record><leader>03878nam a2200529 c 4500</leader><controlfield tag="001">990000945800504498</controlfield><controlfield tag="005">20230317203157.0</controlfield><controlfield tag="007">cr#|||||||||||</controlfield><controlfield tag="007">tu</controlfield><controlfield tag="008">050103|2004 ||| m ||| | eng c</controlfield><controlfield tag="009">AC04351739</controlfield><datafield tag="015" ind1=" " ind2=" "><subfield code="a">OeBB</subfield><subfield code="2">oeb</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(AT-OBV)AC04351739</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">AC04351739</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(Aleph)004338543ACC01</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(DE-599)OBVAC04351739</subfield></datafield><datafield tag="035" ind1=" " ind2=" "><subfield code="a">(EXLNZ-43ACC_NETWORK)990043385430203331</subfield></datafield><datafield tag="040" ind1=" " ind2=" "><subfield code="a">TUW</subfield><subfield code="b">ger</subfield><subfield code="d">AT-UBTUW</subfield><subfield code="e">rakwb</subfield></datafield><datafield tag="041" ind1=" " ind2=" "><subfield code="a">eng</subfield></datafield><datafield tag="044" ind1=" " ind2=" "><subfield code="c">XA-AT</subfield></datafield><datafield tag="084" ind1=" " ind2=" "><subfield code="a">54.62</subfield><subfield code="2">bkl</subfield></datafield><datafield tag="084" ind1=" " ind2=" "><subfield code="a">54.80</subfield><subfield code="2">bkl</subfield></datafield><datafield tag="084" ind1=" " ind2=" "><subfield code="a">54.72</subfield><subfield code="2">bkl</subfield></datafield><datafield tag="084" ind1=" " ind2=" "><subfield code="a">54.51</subfield><subfield code="2">bkl</subfield></datafield><datafield tag="100" ind1="1" ind2=" "><subfield code="a">Ljubić, Ivana</subfield><subfield code="4">aut</subfield></datafield><datafield tag="245" ind1="1" ind2="0"><subfield code="a">Exact and memetic algorithms for two network design problems</subfield><subfield code="c">Ivana Ljubić</subfield></datafield><datafield tag="264" ind1=" " ind2="1"><subfield code="c">2004</subfield></datafield><datafield tag="300" ind1=" " ind2=" "><subfield code="a">V, 177 S.</subfield><subfield code="b">Ill., graph. Darst.</subfield></datafield><datafield tag="502" ind1=" " ind2=" "><subfield code="a">Wien, Techn. Univ., Diss., 2004</subfield></datafield><datafield tag="520" ind1=" " ind2=" "><subfield code="a">ger: This thesis focuses on two NP-hard network design problems:<br />the first one, vertex biconnectivity augmentation (V2AUG), appears in the design of survivable communication or electricity networks. In this problem we search for the set of connections of minimal total cost which, when added to the existing network, makes it survivable against failures of any single node. The second problem, the prize-collecting Steiner tree problem (PCST), describes a natural trade-off between maximizing the sum of profits over all selected customers and minimizing the implementation costs, e.g.<br />when designing a fiber optic or a district heating network.<br />We provide exact algorithms based on the branch-and-cut technique that can solve given network design problems of respectable size to provable optimality. For fairly large instances, we propose heuristic tools that obtain suboptimal, high quality solutions of practical relevance. Fractional bounds obtained by means of exact methods are therefore used as a measure of quality of obtained heuristic solution.<br />As a heuristic tool, we choose memetic algorithms (MAs), a symbiosis of evolutionary and neighborhood search algorithms. Our memetic algorithms comprise new representation techniques, search operators,constraint handling techniques and local-improvement strategies. Our exact algorithms are based on the state-of-the-art in polyhedral combinatorics. They rely on sophisticated separation algorithms or advanced column generation methods.<br />In this thesis, we also investigate some possibilities of combining promising variants of exact algorithms and MAs, e.g. incorporating exact algorithms that solve some special cases within MAs, or guiding column generation using MA results. In extensive computational studies our exact and memetic algorithms show their superiority compared to the previously published results. For many of V2AUG and PCST instances, we are the first to find provably optimalsolutions.<br /></subfield></datafield><datafield tag="520" ind1=" " ind2=" "><subfield code="a">eng: Abstract nicht verfügbar</subfield></datafield><datafield tag="689" ind1="0" ind2="0"><subfield code="a">Kombinatorische Optimierung</subfield><subfield code="D">s</subfield><subfield code="0">(DE-588)4031826-6</subfield></datafield><datafield tag="689" ind1="0" ind2="1"><subfield code="a">NP-hartes Problem</subfield><subfield code="D">s</subfield><subfield code="0">(DE-588)4621705-8</subfield></datafield><datafield tag="689" ind1="0" ind2="2"><subfield code="a">Netzwerk</subfield><subfield code="D">s</subfield><subfield code="0">(DE-588)4171529-9</subfield></datafield><datafield tag="689" ind1="0" ind2="3"><subfield code="a">Algorithmus</subfield><subfield code="D">s</subfield><subfield code="0">(DE-588)4001183-5</subfield></datafield><datafield tag="689" ind1="0" ind2=" "><subfield code="5">AT-OBV</subfield><subfield code="5">ONBREB</subfield></datafield><datafield tag="689" ind1="1" ind2="0"><subfield code="a">Steiner-Problem</subfield><subfield code="D">s</subfield><subfield code="0">(DE-588)4248342-6</subfield></datafield><datafield tag="689" ind1="1" ind2="1"><subfield code="a">Algorithmus</subfield><subfield code="D">s</subfield><subfield code="0">(DE-588)4001183-5</subfield></datafield><datafield tag="689" ind1="1" ind2=" "><subfield code="5">AT-OBV</subfield><subfield code="5">ONBREB</subfield></datafield><datafield tag="776" ind1="0" ind2="8"><subfield code="i">Erscheint auch als</subfield><subfield code="n">Online-Ausgabe</subfield><subfield code="o">urn:nbn:at:at-ubtuw:1-13664</subfield><subfield code="o">20.500.12708/9557</subfield></datafield><datafield tag="856" ind1="4" ind2="1"><subfield code="q">text/html</subfield><subfield code="u">http://hdl.handle.net/20.500.12708/9557</subfield><subfield code="x">TUW</subfield><subfield code="z">kostenfrei</subfield><subfield code="3">Volltext</subfield><subfield code="r">In Copyright</subfield><subfield code="7">0</subfield></datafield><datafield tag="856" ind1="4" ind2="1"><subfield code="m">V:AT-OBV;B:AT-TUW</subfield><subfield code="q">application/pdf</subfield><subfield code="u">http://media.obvsg.at/AC04351739-2001</subfield><subfield code="x">TUW</subfield><subfield code="3">Volltext</subfield><subfield code="o">OBV-EDOC</subfield></datafield><datafield tag="970" ind1="1" ind2=" "><subfield code="c">24</subfield></datafield><datafield tag="970" ind1="2" ind2=" "><subfield code="a"> TUW</subfield><subfield code="d">HS-DISS</subfield></datafield><datafield tag="970" ind1="0" ind2=" "><subfield code="a">OPUS1677</subfield></datafield><datafield tag="971" ind1="1" ind2=" "><subfield code="a">Mutzel, Petra</subfield></datafield><datafield tag="971" ind1="1" ind2=" "><subfield code="a">Pferschy, Ulrich</subfield></datafield><datafield tag="971" ind1="5" ind2=" "><subfield code="a">Technische Universität Wien</subfield><subfield code="b">Fakultät für Informatik</subfield><subfield code="c">Institut für Computergraphik und Algorithmen</subfield><subfield code="d">E186</subfield><subfield code="0">ioo:TU:IN:KEIN</subfield></datafield><datafield tag="ADM" ind1=" " ind2=" "><subfield code="b">2024-08-05 12:27:05 Europe/Vienna</subfield><subfield code="d">20</subfield><subfield code="f">System</subfield><subfield code="c">marc21</subfield><subfield code="a">2018-12-24 05:17:03 Europe/Vienna</subfield><subfield code="g">false</subfield></datafield><datafield tag="HOL" ind1="8" ind2=" "><subfield code="b">YWOAW</subfield><subfield code="h"> 33255-C.Stip. </subfield><subfield code="c">MAG1-3</subfield><subfield code="8">2213472760004498</subfield></datafield><datafield tag="852" ind1="8" ind2=" "><subfield code="b">YWOAW</subfield><subfield code="c">MAG1-3</subfield><subfield code="h"> 33255-C.Stip. </subfield><subfield code="8">2213472760004498</subfield></datafield><datafield tag="ITM" ind1=" " ind2=" "><subfield code="9">2213472760004498</subfield><subfield code="e">1</subfield><subfield code="m">BOOK</subfield><subfield code="b">+YW6006401</subfield><subfield code="i">33255-C.Stip.</subfield><subfield code="2">MAG1-3</subfield><subfield code="o">20050718</subfield><subfield code="8">2313472740004498</subfield><subfield code="f">02</subfield><subfield code="p">2005-07-18 02:00:00 Europe/Vienna</subfield><subfield code="h">33255-C.Stip.</subfield><subfield code="1">YWOAW</subfield><subfield code="q">2022-06-09 11:14:01 Europe/Vienna</subfield></datafield></record></collection> |