I am wondering if anybody can provide any handy resources (for a theoretical computer scientist) in relation to the convex cost flow problem? I have found texts (mostly my combinatorial optimization texts on my shelf), but they sparingly discuss the problem and its algorithmic properties, and the ones I've found so far take a very deep dive into it without explaining a whole lot or providing any examples. I get the formulation of the problem, but a bit more would be helpful.
I'm new to the problem, and wondering if anybody can suggest some good texts, or papers that do a good job of covering the problem, and some of the major algorithmic results for this problem (computational complexity, and algorithms primarily), or maybe applications of it being used to see how researchers have applied it to solve other problems in theoretical computer science, combinatorial optimization, or operations research.
If you have resources or suggestions, that would be helpful! Thank you so much, and have a beautiful day :).
So are you meaning problems with linear constraints (i.e. network flow constraints) and general convex objective function? If yes, then general interior point methods is the best you can get from a theoretical point of view.
The Parallel Optimization Center at the University of Wisconsin-Madison CS Dept. did some nice research back in the nineties on convex cost network flow problems. See paper and reference inside:
De Leone, R., Meyer, R.R., Zakarian, A. (1999) A partitioned epsilon-relaxation algorithm for separable convex network flow problems. Computational Optimization and Applications, 12(1-3):107-126.
Of course, I would also highly recommend the "Convex Analysis" book by Rockafellar, and the book by Ahuja.
I second the opinion that the book by Ahuja, Magnati and Orlin on network flows is a good one; although slightly old, all the text is useful. Here is a link to a pre-published internal report with the main content already there:
dspace.mit.edu/bitstream/handle/1721.1/.../networkflows00ahuj.pdf
The book proper is found here:
http://www.amazon.com/Network-Flows-Theory-Algorithms-Applications/dp/013617549X
While being there, you may browse others that you like even more! :-)
Thank you so much for all of these suggestions and pointers. These will definitely help me out a ton from even just giving a quick look at them.
Have a beautiful day everybody :)!
One paper - if I may plug my own work - is based on the keen interest in solving such problems from a Lagrangian dual formulation. The following link is to a paper in which we show how to very simply generate primal feasible flows from any dual iteration point, and how a sequence of such flows is optimal in the limit. (This means that we can utilize any convergent dual method, and get the primal optimum "for free".)
http://www.sciencedirect.com/science/article/pii/S037722170700553X
Ah yes, I forgot earlier. Dimitri Bertsekas has made available his network flows book for free. It has god stuff on single-commodity network flows - dual methods in particular. Here is a link to download the book from:
http://web.mit.edu/dimitrib/www/netbook_Full_Book.pdf
Again - good luck!
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs