Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Large-Scale Networks in Engineering and Life SciencesCombinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow

Large-Scale Networks in Engineering and Life Sciences: Combinatorial Optimization: The Interplay... [Combinatorial optimization is one of the fields in mathematics with an impressive development in recent years, driven by demands from applications where discrete models play a role. Here, we intend to give a comprehensive overview of basic methods and paradigms, in particular the beautiful interplay of methods from graph theory, geometry, and linear and integer programming related to combinatorial optimization problems. To understand the underlying framework and the interrelationships more clearly, we illustrate the theoretical results and methods with the help of flows in networks as running example. This includes, on the one hand, a combinatorial algorithm for finding a maximum flow in a network, combinatorial duality and the max-flow min-cut theorem as one of the fundamental combinatorial min–max relations. On the other hand, we discuss solving the network flow problem as a linear program with the help of the simplex method, linear programming duality and the dual program for network flow. Finally, we address the problem of integer network flows, ideal formulations for integer linear programs and consequences for the network flow problem.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Large-Scale Networks in Engineering and Life SciencesCombinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow

Part of the Modeling and Simulation in Science, Engineering and Technology Book Series
Editors: Benner, Peter; Findeisen, Rolf; Flockerzi, Dietrich; Reichl, Udo; Sundmacher, Kai
Wagler, Annegret K.
Large-Scale Networks in Engineering and Life Sciences — Jul 30, 2014
Download PDF
37 pages

Loading next page...
 
/lp/springer-journals/large-scale-networks-in-engineering-and-life-sciences-combinatorial-ItnZ3ah00Y
Publisher
Springer International Publishing
Copyright
© Springer International Publishing Switzerland 2014
ISBN
978-3-319-08436-7
Pages
225 –262
DOI
10.1007/978-3-319-08437-4_4
Publisher site
See Chapter on Publisher Site

Abstract

[Combinatorial optimization is one of the fields in mathematics with an impressive development in recent years, driven by demands from applications where discrete models play a role. Here, we intend to give a comprehensive overview of basic methods and paradigms, in particular the beautiful interplay of methods from graph theory, geometry, and linear and integer programming related to combinatorial optimization problems. To understand the underlying framework and the interrelationships more clearly, we illustrate the theoretical results and methods with the help of flows in networks as running example. This includes, on the one hand, a combinatorial algorithm for finding a maximum flow in a network, combinatorial duality and the max-flow min-cut theorem as one of the fundamental combinatorial min–max relations. On the other hand, we discuss solving the network flow problem as a linear program with the help of the simplex method, linear programming duality and the dual program for network flow. Finally, we address the problem of integer network flows, ideal formulations for integer linear programs and consequences for the network flow problem.]

Published: Jul 30, 2014

Keywords: Network flow; Max-flow min-cut theorem; Linear programming; Duality; Integer linear programming; Unimodularity

There are no references for this article.