LNOS

The classical linear programming/network flow problems: shortest path, maximum flow, assignment, minimum cost flow

The LNOS (Linear Network Optimization Software) package contains the following codes:

GRIDGEN --- Generates minimum cost flow problems with a grid structure.

NGCONVERT --- Converts problems from the NETGEN format to a standard format.

PAPE_ALL_DEST --- Pape's method for shortest paths from one origin to all destinations.

HEAP_ALL_DEST --- Binary heap method for shortest paths from one origin to all destinations.

HEAP_SELECT_DEST --- Binary heap method for shortest paths from one origin to selected destinations.

AUCTION_SELECT_DEST --- Auction algorithm for shortest paths from one origin to selected destinations.

RELAX --- Relaxation method for minimum cost flow problems.

AUCTION --- Forward auction algorithm for symmetric assignment problems.

AUCTION\_FLP --- Same as AUCTION but uses floating-point arithmetic to deal with problems with large cost range and/or dimension.

AUCTION\_AS --- Auction algorithm for asymmetric assignment problems.

AUCTION\_FR --- Forward/reverse auction algorithm for symmetric assignment problems.

NAUCTION\_SP --- Combined naive auction and sequential shortest-path method for assignment.

FORD\_FULKERSON --- Ford-Fulkerson algorithm for maximum flow.

E_RELAX_MF --- E-relaxation algorithm for maximum flow.

E_RELAX --- E-relaxation algorithm for minimum cost flow.

E_RELAX_N --- E-relaxation algorithm for minimum cost flow; iterates from both positive and negative surplus nodes.

All codes are written in Fortran and, with the exception of AUCTION_FLP, use integer arithmetic. All codes can be compiled with the popular Absoft compiler on all Macintosh computers. By changing a few input and output statements, the codes can be easily adapted for other computers and Fortran compilers.

Need more info?

Listings of all codes except RELAX, AUCTION_FLP, and E_RELAX_N appear in the book cited below. For an IBM-PC or Macintosh-readable diskette with the listings of all the codes, send $25.00 to:

Prof. Dimitri P. Bertsekas
Massachusetts Institute of Technology
Room 35-210
Cambridge, MA 02139

Reference:

D. P. Bertsekas, Linear Network Optimization: Algorithms and Codes, MIT Press, 1991.

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]