On inverse network problems and their generalizations [Elektronische Ressource] / Çiğdem Güler

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_kaiserslautern
• Publié le: 01 janvier 2009
• Nombre de lectures: 24
• Langue: English

Extrait

On Inverse Network Problems
and their Generalizations
˙igdem G ler
Vom Fachbereich Mathematik der Technischen Universit t Kaiserslautern
zur Verleihung des akademischen Grades
Doktor der Naturwissenschaften (Doctor rerum naturalium, Dr. rer. nat.)
genehmigte Dissertation
Gutachter: Prof. Dr. Horst W. Hamacher
Prof. Dr. Rainer E. Burkard
Datum der Disputation: 19. Juni 2009
D 386No man is an island, entire of itself; every man is a piece of the continent, a part of
the main. If a clod be washed away by the sea, Europe is the less, as well as if a
promontory were, as well as if a manor of thy friend’s or of thine own were. Any
man’s death diminishes me because I am involved in mankind; and therefore never
send to know for whom the bell tolls; it tolls for thee.
John Donne (1572-1631)Acknowledgment
I would like to acknowledge my appreciation to a number of people who helped and
supported me in the process of writing this thesis. Foremost, I would like to express
my deep gratitude to my supervisor Prof. Dr. Horst W. Hamacher not only for the
interesting topic, helpful discussions and comments but also for his excellent support
and encouraging attitude in all these years. Thank you so much for your trust in me.
I would like to thank Deutsche Forschungsgemeinschaft (DFG) for the grant HA
1737/7 "Algorithmik gro er und komplexer Netzwerke" and the state of Rhineland
Palatinate for the grants cluster of excellence "Dependable Adaptive Systems and
Mathematical Modeling (DASMOD)" and "Center for Mathematical and Computa-
tional Modelling".
I am very grateful for the support of all my colleagues in the Optimization Group
at the Department of Mathematics. I am also thankful to all my friends for the won-
derful time I spent at the University of Kaiserslautern. Particularly, I would like to
mention Donatas Elvikis for his patience during the time we shared the of ce, Akin
Tanatmis for making me laugh even when I was terribly stressed, and Dr. Stefan
Ruzika for being there whenever I needed a suggestion. Besides I am very thankful
to Prof. Dr. Sven O. Krumke for his help in Boost Graph Library and LaTeX and Nico
Behrent for his continuous assistance in software and hardware issues.
I would like to thank Prof. Dr. Rainer E. Burkard for his effort to read and evaluate
my thesis and for his inspiring research papers on related topics.
I also appreciated Christian Ruby’s helpful comments related to the English lan-
guage and Dr. Arun K. Upadhyay’s suggestions on the format of this thesis very
much. Thank you for spending your time on reading and correcting my work.
My special thanks go to my dear friends Simone Kressmann, Pelin zg rb z,
and Ezgi Ke eli for the long conversations and enjoyable activities that provided me
with some distraction and relief from the dif culties I faced in the process of writing
this thesis. Furthermore, I would like to mention my sincere thanks to Gundula and
Theodor Ruby who have become my family in Germany.
Last but not least, loving and special thanks to my family who could transmit
the most special and enduring love and support through phone lines and to Tilmann
Ruby who has always stood by me since the very rst day we met. Without his love I
would have been lost.
iContents
Acknowledgment i
Table of Contents iii
Introduction and Outline v
1 Preliminaries 1
1.1 Network Flow Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Optimality for Maximum Flows . . . . . . . . . . . . . . . . . . 3
1.1.2 for Minimum Cost Flows . . . . . . . . . . . . . . . 4
1.2 Literature on Inverse Network Flows . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Inverse Linear Programming Problem . . . . . . . . . . . . . . . 6
1.2.2 Maximum Flow and Minimum Cut Problems . . . . . . 9
1.2.3 Inverse Minimum Cost Flow Problem . . . . . . . . . . . . . . . 10
1.2.4 Some Further Results on Inverse Optimization Problems . . . . 11
2 Inverse Network Flows with Capacity Change 13
2.1 Inverse Maximum Flow Problem under ‘ Norm . . . . . . . . . . . . 131
2.1.1 Bicriteria Inverse Maximum Flow Problem . . . . . . . . . . . . 18
2.1.2 Extension to Zero Lower Bounds Case (l = 0) . . . . . . . . . . 19ij
2.2 Capacity Inverse Minimum Cost Flow Problem . . . . . . . . . . . . . . 20
2.2.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Rectilinear (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 221
2.2.3 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 271
2.2.4 Computational Experiments . . . . . . . . . . . . . . . . . . . . 30
2.2.5 Extension to Flows with Lower and Upper Bounds . . . . . . . 34
3 Inverse Tension Problems 37
3.1 Inverse Maximum Tension Problem . . . . . . . . . . . . . . . . . . . . 38
3.1.1 Rectilinear (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . . 381
3.1.2 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 421
3.2 Cost Inverse Minimum Cost Tension Problem . . . . . . . . . . . . . . . 44
3.2.1 Rectilinear (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . . 441
3.2.2 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 501
3.3 Capacity Inverse Minimum Cost Tension Problem . . . . . . . . . . . . 54
3.3.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . 54
iiiCONTENTS
3.3.2 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 561
4 Inverse Matroid Flows On Regular Matroids 61
4.1 Introduction to Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Flows on Regular Matroids . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Inverse Maximal M-Flow Problem . . . . . . . . . . . . . . . . . . . . . 65
4.3.1 Rectilinear (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . . 661
4.3.2 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 701
4.4 Cost Inverse Minimum Cost M-Flow Problem . . . . . . . . . . . . . . 72
4.4.1 Rectilinear (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . . 751
4.4.2 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 791
4.5 Capacity Inverse Minimum Cost M-Flow Problem . . . . . . . . . . . . 83
4.5.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.5.2 Chebyshev (‘ ) Norm . . . . . . . . . . . . . . . . . . . . . . . . 841
5 Cost Inverse Problems of Monotropic Programs 87
5.1 Introduction to Monotropic Optimization . . . . . . . . . . . . . . . . . 87
5.2 Inverse Primal Problem with Linear Costs under ‘ Norm . . . . . . . 901
5.3 Primal Problem with Linear Costs under ‘ Norm . . . . . . . 941
5.4 Special Case: Generalized Minimum Cost Flows . . . . . . . . . . . . . 96
6 Concluding Remarks 103
6.1 Summary of Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Bibliography 109
List of Tables 115
List of Figures 117
Index 119
Declaration 121
ivIntroduction and Outline
Introduction
In the past few decades, optimization problems with estimated problem parameters
have drawn considerable attention from researchers. For this kind of problems one
often knows a priori an optimal solution based on observations or experiments, but is
interested in nding a set of parameters, such that the known solution is optimum (i)
and the deviation from the initial estimates is minimized (ii). The problem of recalcu-
lating the parameters satisfying (i) and (ii) is known as inverse optimization problem.
Ahuja and Orlin (2001) mention, in their paper, that the major application area
for inverse optimization is geophysical sciences and it were, indeed, geophysicists to
rst study such problems. At the beginning of 90’s, a well-known study by Burton
and Toint (1992, 1994) attracted the interest of mathematicians to this topic. In their
papers, the authors study inverse shortest path problems to predict the movements of
earthquakes. Since then inverse versions of several optimization problems have been
intensely investigated in diverse areas of application such as:
Medical imaging in X-ray tomography where a CT-scan of a body part is ex-
ploited to estimate its dimensions given other information on the body
Imposing tolls in transportation networks, in order to enforce the use of system
equilibrium routes instead of user optimal ones (Dial, 1999, 2000)
High-speed Asynchronous Transfer Mode (ATM) networks to obtain reliable
and self-con guring systems (Farag et al., 2003)
Among the optimization problems studied in the context of inverse optimization,
the combinatorial problems such as network ows are the most popular ones to ana-
lyze their inverses. Especially inverse versions of maximum ow and minimum cost
ow problems have thoroughly been investigated in the literature. In these network
ow pr there are two important problem parameters: ow capacities of the
arcs of the network and costs incurred by sending a unit ow on these arcs. Capac-
ity changes for maximum ow problems and cost changes for minimum cost ow
problems have been studied under several distance measures such as rectilinear (‘ ),1
Chebyshev (‘ ), and Hamming distances. These norms are usually the most pre-1
ferred ones because of their handiness and practical relevance.
In this thesis,