Changeset 755:134852d7fb0a in lemon1.2 for doc
 Timestamp:
 10/10/09 08:18:46 (10 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 doc
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r742 r755 317 317 318 318 This group contains the common graph search algorithms, namely 319 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS). 319 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS) 320 \ref clrs01algorithms. 320 321 */ 321 322 … … 325 326 \brief Algorithms for finding shortest paths. 326 327 327 This group contains the algorithms for finding shortest paths in digraphs. 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 328 330 329 331  \ref Dijkstra algorithm for finding shortest paths from a source node … … 347 349 348 350 This group contains the algorithms for finding minimum cost spanning 349 trees and arborescences .351 trees and arborescences \ref clrs01algorithms. 350 352 */ 351 353 … … 356 358 357 359 This group contains the algorithms for finding maximum flows and 358 feasible circulations .360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 359 361 360 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 371 373 372 374 LEMON contains several algorithms for solving maximum flow problems: 373  \ref EdmondsKarp EdmondsKarp algorithm. 374  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm. 375  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 376  \ref GoldbergTarjan Preflow pushrelabel algorithm with dynamic trees. 377 378 In most cases the \ref Preflow "Preflow" algorithm provides the 375  \ref EdmondsKarp EdmondsKarp algorithm 376 \ref edmondskarp72theoretical. 377  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm 378 \ref goldberg88newapproach. 379  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381  \ref GoldbergTarjan !Preflow pushrelabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 379 385 fastest method for computing a maximum flow. All implementations 380 386 also provide functions to query the minimum cut, which is the dual … … 394 400 395 401 This group contains the algorithms for finding minimum cost flows and 396 circulations. For more information about this problem and its dual 397 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 402 circulations \ref amo93networkflows. For more information about this 403 problem and its dual solution, see \ref min_cost_flow 404 "Minimum Cost Flow Problem". 398 405 399 406 LEMON contains several algorithms for this problem. 400 407  \ref NetworkSimplex Primal Network Simplex algorithm with various 401 pivot strategies .408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 402 409  \ref CostScaling PushRelabel and AugmentRelabel algorithms based on 403 cost scaling. 410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 404 412  \ref CapacityScaling Successive Shortest %Path algorithm with optional 405 capacity scaling. 406  \ref CancelAndTighten The Cancel and Tighten algorithm. 407  \ref CycleCanceling CycleCanceling algorithms. 413 capacity scaling \ref edmondskarp72theoretical. 414  \ref CancelAndTighten The Cancel and Tighten algorithm 415 \ref goldberg89cyclecanceling. 416  \ref CycleCanceling CycleCanceling algorithms 417 \ref klein67primal, \ref goldberg89cyclecanceling. 408 418 409 419 In general NetworkSimplex is the most efficient implementation, … … 535 545 536 546 /** 537 @defgroup lp_group L p and MipSolvers547 @defgroup lp_group LP and MIP Solvers 538 548 @ingroup gen_opt_group 539 \brief Lp and Mip solver interfaces for LEMON. 540 541 This group contains Lp and Mip solver interfaces for LEMON. The 542 various LP solvers could be used in the same manner with this 543 interface. 549 \brief LP and MIP solver interfaces for LEMON. 550 551 This group contains LP and MIP solver interfaces for LEMON. 552 Various LP solvers could be used in the same manner with this 553 highlevel interface. 554 555 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 556 \ref cplex, \ref soplex. 544 557 */ 545 558 
doc/mainpage.dox
r658 r755 22 22 \section intro Introduction 23 23 24 \subsection whatis What is LEMON 25 26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 27 and <b>O</b>ptimization in <b>N</b>etworks. 28 It is a C++ template 29 library aimed at combinatorial optimization tasks which 30 often involve in working 31 with graphs. 24 <b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 25 and <b>O</b>ptimization in <b>N</b>etworks</i>. 26 It is a C++ template library providing efficient implementation of common 27 data structures and algorithms with focus on combinatorial optimization 28 problems in graphs and networks. 32 29 33 30 <b> … … 39 36 </b> 40 37 41 \subsection howtoread How to read the documentation 38 The project is maintained by the 39 <a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on 40 Combinatorial Optimization</a> \ref egres 41 at the Operations Research Department of the 42 <a href="http://www.elte.hu/">Eötvös Loránd University, 43 Budapest</a>, Hungary. 44 LEMON is also a member of the <a href="http://www.coinor.org/">COINOR</a> 45 initiative \ref coinor. 46 47 \section howtoread How to Read the Documentation 42 48 43 49 If you would like to get to know the library, see 
doc/min_cost_flow.dox
r663 r755 27 27 minimum total cost from a set of supply nodes to a set of demand nodes 28 28 in a network with capacity constraints (lower and upper bounds) 29 and arc costs .29 and arc costs \ref amo93networkflows. 30 30 31 31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, 
doc/references.bib
r754 r755 151 151 %%%%% Maximum flow algorithms %%%%% 152 152 153 @inproceedings{goldberg86newapproach, 153 @article{edmondskarp72theoretical, 154 author = {Jack Edmonds and Richard M. Karp}, 155 title = {Theoretical improvements in algorithmic efficiency 156 for network flow problems}, 157 journal = {Journal of the ACM}, 158 year = 1972, 159 volume = 19, 160 number = 2, 161 pages = {248264} 162 } 163 164 @article{goldberg88newapproach, 154 165 author = {Andrew V. Goldberg and Robert E. Tarjan}, 155 166 title = {A new approach to the maximum flow problem}, 156 booktitle = {STOC '86: Proceedings of the Eighteenth Annual ACM 157 Symposium on Theory of Computing}, 158 year = 1986, 159 publisher = {ACM Press}, 160 address = {New York, NY}, 161 pages = {136146} 167 journal = {Journal of the ACM}, 168 year = 1988, 169 volume = 35, 170 number = 4, 171 pages = {921940} 162 172 } 163 173 … … 230 240 } 231 241 232 @ inproceedings{goldberg88cyclecanceling,242 @article{goldberg89cyclecanceling, 233 243 author = {Andrew V. Goldberg and Robert E. Tarjan}, 234 244 title = {Finding minimumcost circulations by canceling 235 245 negative cycles}, 236 booktitle = {STOC '88: Proceedings of the Twentieth Annual ACM237 Symposium on Theory of Computing},238 year = 1988,239 publisher = {ACM Press},240 address = {New York, NY},241 pages = {388397}242 }243 244 @article{edmondskarp72theoretical,245 author = {Jack Edmonds and Richard M. Karp},246 title = {Theoretical improvements in algorithmic efficiency247 for network flow problems},248 246 journal = {Journal of the ACM}, 249 year = 1972, 250 volume = 19, 251 number = 2, 252 pages = {248264} 253 } 254 255 @inproceedings{goldberg87approximation, 256 author = {Andrew V. Goldberg and Robert E. Tarjan}, 257 title = {Solving minimumcost flow problems by successive 258 approximation}, 259 booktitle = {STOC '87: Proceedings of the Nineteenth Annual ACM 260 Symposium on Theory of Computing}, 261 year = 1987, 262 publisher = {ACM Press}, 263 address = {New York, NY}, 264 pages = {718} 265 } 266 267 @article{goldberg90finding, 247 year = 1989, 248 volume = 36, 249 number = 4, 250 pages = {873886} 251 } 252 253 @article{goldberg90approximation, 268 254 author = {Andrew V. Goldberg and Robert E. Tarjan}, 269 255 title = {Finding MinimumCost Circulations by Successive … … 298 284 } 299 285 286 @book{dantzig63linearprog, 287 author = {George B. Dantzig}, 288 title = {Linear Programming and Extensions}, 289 publisher = {Princeton University Press}, 290 year = 1963 291 } 292 300 293 @mastersthesis{kellyoneill91netsimplex, 301 294 author = {Damian J. Kelly and Garrett M. O'Neill}, … … 307 300 month = sep, 308 301 } 309 310 @techreport{lobel96networksimplex,311 author = {Andreas L{\"o}bel},312 title = {Solving largescale realworld minimumcost flow313 problems by a network simplex method},314 institution = {KonradZuseZentrum fur Informationstechnik Berlin315 ({ZIB})},316 address = {Berlin, Germany},317 year = 1996,318 number = {SC 967}319 }320 321 @article{frangioni06computational,322 author = {Antonio Frangioni and Antonio Manca},323 title = {A Computational Study of Cost Reoptimization for324 MinCost Flow Problems},325 journal = {INFORMS Journal On Computing},326 year = 2006,327 volume = 18,328 number = 1,329 pages = {6170}330 }
Note: See TracChangeset
for help on using the changeset viewer.