From xu@benji.Colorado.EDU Thu Apr 13 17:18:22 EDT 1995
Article: 3183 of sci.op-research
Xref: undergrad.math.uwaterloo.ca sci.op-research:3183
Path: undergrad.math.uwaterloo.ca!watserv2.uwaterloo.ca!torn!howland.reston.ans.net!math.ohio-state.edu!jussieu.fr!fdn.fr!uunet!boulder!benji.Colorado.EDU!xu
From: xu@benji.Colorado.EDU (XU JIEFENG)
Newsgroups: sci.op-research
Subject: List of OR Codes in Public Domain [Part 2]
Date: 13 Apr 95 05:23:28 GMT
Organization: University of Colorado at Boulder
Lines: 1536
Message-ID:
NNTP-Posting-Host: benji.colorado.edu
X-Newsreader: NN version 6.5.0 #12 (NOV)
List of Interesting Optimization Codes in Public Domain
***** Codes for Optimization Library *****
Name: LEDA (A Library of Efficient Data Types and Algorithms)
Site: ftp://ftp.mpi-sb.mpg.de in /pub/LEDA.
File: LEDA-3.1c.tar.Z
Platform: Almost any C++ compilers (cfront2.1, cfront3.0, g++, borland,
zortech).
Install: Use "uncompress" and "tar -xf", then see INSTALL and
INSTALL.dos.
Language: C++.
Author: Stefan Naeher (stefan@mpi-sb.mpg.de).
Version: 3.1c.
Size: 1.03 MB in ".tar.z" form.
Description: LEDA is a library of the data types and algorithms of
combinatorial computing. The main features are:
1. LEDA provides a sizable collection of data types and
algorithms in a form which allows them to be used by non-experts.
In the current version, this collection includes most of the data
types and algorithms described in the text books of the area.
2. LEDA gives a precise and readable specification for each of
the data types and algorithms mentioned above. The specifications
are short (typically, not more than a page), general (so as to
allow several implementations), and abstract (so as to hide all
details of the implementation).
3. For many efficient data structures access by position is
important. In LEDA, we use an item concept to cast positions
into an abstract form. We mention that most of the specifications
given in the LEDA manual use this concept, i.e., the concept is
adequate for the description of many data types.
4. LEDA contains efficient implementations for each of the data
types, e.g., Fibonacci heaps for priority queues, red-black
trees and dynamic perfect hashing for dictionaries, ...
5. LEDA contains a comfortable data type graph. It offers the
standard iterations such as "for all nodes v of a graph G
do" or "for all neighbors w of v do", it allows to add and
delete vertices and edges and it offers arrays and matrices
indexed by nodes and edges,... The data type graph allows to
write programs for graph problems in a form close to the typical
text book presentation.
6. LEDA is implemented by a C++ class library. It can be used
with allmost any C++ compiler.
7. LEDA is not in the public domain, but can be used freely for
research and teaching. A commercial license is available for
2000 DM.
Comments:
****** General Linear Programming Codes *****
Name: lp_solve
Site: ftp://ftp.es.ele.tue.nl (131.155.20.126) at /pub/lp_solve
File: lp_solve_1.5.tar.gz or lpdos15.zip for DOS.
Platform: Unix, Dos
Install: "gunzip" plus "tar -xf", then see INSTALL. (for Dos version,
use pkunzip).
Language: C
Author: Michel Berkelaar, email at michel@es.ele.tue.nl
Version: version 1.5.
Size: 44K in unix and 279K in Dos in compressed form.
Description: may solve models with up to 30,000 variables and 50,000
constraints.
Comments: From Linear Programming - FAQ by jwg@cray.com (John Gregory):
As an editorial opinion, I must state that difficult models will
give this code trouble. It's not as good as a commercial code.
But for someone who isn't sure just what kind of LP code is
needed, it represents a very reasonable first try, since it does
solve non-trivial-sized models, and it is free.
Name: LIPSOL -- Linear programming Interior-Point SOLvers
Site: ftp://ftp.math.umbc.edu in directory /pub/zhang/lipsol/beta-2
http://math.umbc.edu/~zhang/
File: lipsol*.tar.gz for your machine in beta-2 directory
Platform: DEC(Ultrix), SGI (IRIX 4.1 and 5.2) and Sun Sparcs (SunOS 4.1.3)
Install: "gunzip" plus "tar -xf". See README.1ST.
Language: Matlab 4.2. (distributed as executable code).
Author: Yin Zhang, yzhang@math.umbc.edu.
Version: Beta-2.2 Version.
Size: 173K ~ 285K for different platforms in tar.gz form.
Description: LIPSOL is a MATLAB toolkit that uses Matlab's sparse-matrix data
structure and MEX utilities to achieve both programming simplicity
and computational efficiency. The primary goal of this software
is to provide researchers and their students in the field of
interior-point methods a convenient and yet powerful tool for
quickly experimenting and comparing various ideas and algorithms
on nontrivial LP problems. The current release can solve a large
majority of LP problems in the Netlib collection, mostly within
seconds on a fast workstation such as SGI Indigo 2. LIPSOL is
still under active development. Some effective techniques are
still to be implemented, such as dense-column handling. Highly
expandable, LIPSOL may also be used as a teaching tool, or even
to solve real-world problems of tens of thousands of variables.
See release.beta-2
Comments:
Name: LOQO
Site: ftp://elib.zib-berlin.de in /pub/optnet/software/loqo/1.08
File: *.tar.Z for your machine.
Platform: IBM workstations (RS6000's), Silicon Graphics workstations
(IRIS's), HP workstations (7xx) and Sun workstations.
Install: "uncompress" plus "tar -xf".
Language: C.
Author: Robert J. Vanderbei, rvdb@jazz.princeton.edu.
Version: 1.08.
Size: 160K ~ 280K for differnet platform in tar.Z form.
Description: LOQO is an efficient implementation of an interior-point
method for large-scale linear and/or quadratic programming
problems. Its design is simple and straightforward making it
easy to incorporate into larger systems that are built to solve
specific types of optimization problems. The package includes
a subroutine library (libloqo.a), an executable (loqo), the source
for the main part of loqo (loqo.c), and associated documentation
(loqo.dvi and *.eps). The algorithm used is a one-phase
primal-dual-symmetric interior-point method. The code was
designed to work well on all sizes of problems ranging from very
small to very large scale. Benchmarks are also included showing
results competitive to existing popular packages such as CPlex.
THE FREE CODE FROM ELIB IS INTENDED TO BE USED FOR ACADEMIC
RESEARCH PURPOSES ONLY. If you wish to purchase a commercial
version, please contact the author for details.
Comments:
Name: minit
Site: ftp://ftp.uu.net or ftp://ftp.sterling.com,
directory /usenet/comp.sources.misc/volume7.
File: minit.Z and minit.p1.Z
Platform: C compilers.
Install: uncompress, then cut the header in minit, unpack with "/bin/sh",
then use Makefile to install.
Language: C.
Author: Badri Lokanathan, badri@ee.rochester.edu.
Version: patch 1.0, minit.p1 contains the bugs and fixes.
Size: 25 KB before unpack.
Description: This bundle contains a linear programming package based on the
dual simplex method. The original code was given in Collected
Algorithms from CACM (1968) in algol 60 by Rudolfo Salazar and
Subrata Sen. The evaluators of this algorithm suggested some
fixes that have also been incorporated.
The author translated it into C and have been using it for
sometime now without any problems. The code consists of two parts:
(1) A function called minit_space_handler to initialize arrays by
mallocing the appropriate amount of space, and minit, the actual
LP solver. These routines can be invoked directly by another
package. Both are in file minit.c
(2) A front end to use the minit routines stand alone. Usage is
documented in the man page.
Comments:
***** General Integer Programming Code *****
Name: opbdp
Site: ftp://ftp.mpi-sb.de
www: http://www.mpi-sb.mpg.de:/guide/staff/barth/barth.html
File: opbdp.tar.Z under pub/guide/staff/barth/opbdp
Platform: UNIX.
Install: uncompress,tar -xf, then use C++ compiler, see README file.
Language: C++.
Author: Peter Barth, Peter.Barth@mpi-sb.mpg.de
Version: 0.0
Size: 170 KB in tar.Z form.
Description: This is an implementation in C++ of an implicit
enumeration algorithm solving linear 0-1 optimization problems.
A linear 0-1 term can either be maximized or minimized wrt. a
set of linear constraints over 0-1 variables.
All linear 0-1 constraints are transformed to >= inequalities.
The optimization problem is solved by solving a sequence of
satisfiability problems of a set of linear 0-1 constraints.
The search tree is explored depth first.
Each time a satisfiable solution is found, the value v of the
objective function objf under this solution is calculated and the
the constraint objf >= v+1 is added. Then enumeration is continued
until unsatisfiability is detected.
The last solution then is the optimal solution.
The implicit enumeration algorithm can be seen as a generalization
of the Davis-Putnam enumeration algorithm for solving propositional
satisfiability problems in clausal form to the pseudo-Boolean case.
A Technical Report is included as Postscript-File "mpii952002.ps"
describing the techniques used in opbdp.
The package can use different heuristics for selecting of the
variable on which to enumerate next.
It should be fairly easy to write your own variable selection
heuristics.
Comments: The author claims that opbdp compares well with linear programming
based branch-and-bound (CPLEX) on a variety of standard 0-1
integer programming benchmarks. It turns out that exploiting the
logical structure of a problem, i.e. using opbdp, yields good
performance on problems where exploiting the polyhedral
structure seems to be inefficient and vice versa.
***** Network Optimization Codes *****
Name: RELAX-IV.
Site: ftp://LIDS.MIT.EDU in the directory /pub/bertsekas/RELAX.
File: RELAX4.FOR.
Platform: Unix, or make minor changes to conform to other machinese with
f77.
Install: compile with f77.
Language: Fortran 77.
Author: Dimitri Bertsekas,dimitrib@mit.edu,
Paul Tseng, tseng@math.washington.edu.
Version: version VI.
Size: 112K source code.
Description: RELAX-IV is a Fortran code for solving minimum cost flow problems
that combines the earlier RELAX-III code of Bertsekas and Tseng
with an initialization based on a recently proposed
auction/sequential shortest path algorithm. This initialization
is extremely helpful in speeding up the solution of difficult
problems, involving for example long augmenting paths, for which
the relaxation method has been known to be slow. On the other
hand, this initialization does not significantly deteriorate the
performance of the relaxation method for the types of problems
where it has been known to be very fast.
Comments:
Name: NETFLOW
Site: ftp://dimacs.rugters.edu in directory
/pub/netflow/mincost/solver-1
File: netflo_f.shell
Platform: Unix, MS DOS
Install: run netflo_f.shell file in the /bin/sh shell, then compile with
FORTARAN compilers.
Language: Fortran 77.
Author: V. Helgason and J.L. Kennington.
Version:
Size: 190 KB source codes in ".shell" form.
Description: This package contains the algorithm for solving minimum cost flow
problems. For more information see pages 244-256 in "Algorithms
for Network Programming" by Kennington and Helgason,
John Wiley, 1980.
Comments:
Name: lopnet
Site: ftp://LIDS.MIT.EDU in the directory /pub/bertsekas
File: lopnet.codes
Platform: Absoft compiler on all Macintosh computers (subject to memory
limitations). the codes can be easily adapted for other computers
and FORTRAN compilers.
Install: make a seperate file for the code, compile with fortran compilers.
Language: Fortran, distributed as the listings of the source codes.
Author: Dimitri Bertsekas, dimitrib@mit.edu.
Version: most recent as of June 1, 1994.
Size: 339K source code listings.
Description: Most of these codes are essentially those listed in the appendix
of the textbook "LINEAR NETWORK OPTIMIZATION: ALGORITHMS AND
CODES", MIT PRESS,1991 by Dimitri P. Bertsekas.
The theory of many of the codes is described in the survey
article "Auction Algorithms for Network Flow Problems: A Tutorial
Introduction", Computational Optimization and Applications,
1, 1992, 7-26.
Some of the codes may differ slighly from the ones given in the
book, to reflect improvements in implementation. The following is
a summary of the codes:
1) GRIDGEN: Generates min cost flow problems with a grid structure.
2) NGCONVERT: Converts problems from the NETGEN format to a
standard format.
3) PAPE_ALL_DEST: Pape's method for shortest paths from one
origin to all destinations.
4) HEAP_ALL_DEST: Binary heap method for shortest paths from
one origin to all destinations.
5) HEAP_SELECT_DEST: Binary heap method for shortest paths from
one origin to selected destinations.
6) AUCTION_SELECT_DEST: Auction algorithm for shortest paths from
one origin to selected destinations, as per the paper "An
Auction Algorithm for Shortest Paths," SIAM J. on Optimization,
Vol. 1, 1991, pp. 425-447, by D. P. Bertsekas.
7) RELAX_QC: Relaxation method for min cost flow, as per the paper
"A Unified Framework for Primal-Dual Methods in Minimum Cost
Network Flow Problems," Math. Programming, Vol. 32, pp.
125-145, 1985, by D. P. Bertsekas.
8) AUCTION: Forward auction algorithm for symmetric assignment
problems, as per the original 1979 MIT report "A Distributed
Algorithm for the Assignment Problem"; see also the paper "The
Auction Algorithm: A Distributed Relaxation Method for the
Assignment Problem," Annals of Operations Research, Vol. 14,
1988, pp. 105-123, by D. P. Bertsekas.
9) AUCTION_FLP: Same as AUCTION but uses floating point arithmetic
to deal with problems with large cost range and/or dimension. For
such problems the prices may overflow the integer range in the
course of the algorithm.
10) AUCTION_AS: Auction algorithm for asymmetric assignment
problems.
11) AUCTION_FR: Forward/reverse auction algorithm for symmetric
assignment problems.
12) NAUCTION_SP: Combined naive auction and sequential shortest
path method for assignment.
13) FORD_FULKERSON: Ford-Fulkerson algorithm for max-flow.
14) E_RELAX_MF: E-relaxation algorithm for max-flow.
15) E_RELAX: E-relaxation algorithm for min cost flow as per the
paper "Distributed Relaxation Methods for Linear Network Flow
Problems," Proc. 25th IEEE Conference on Decision and Control,
Athens, Greece, 1986, by D. P. Bertsekas.
16) E_RELAX_N: E-relaxation algorithm for min cost flow; iterates
from both positive and negative surplus nodes.
17) SLF: Small Label First (SLF) algorithm for finding shortest
paths from one origin to all destinations, as per the paper
"A Simple and Fast Label Correcting Method for Shortest Paths,"
Networks, Vol. 23, 1993, pp. 703-709, by D. P. Bertsekas.
18) SLFT: Combination of Small Label First (SLF) and threshold
algorithms for finding shortest paths from one origin to all
destinations, as per the paper "A Simple and Fast Label Correcting
Method for Shortest Paths," Networks, Vol. 23, 1993, pp. 703-709,
by D. P. Bertsekas.
Comments:
Name: CSMIN
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/goldberg directory.
File: csmin.tar.z
Platform: C compilers.
Install: uncompress then unpack the .tar file, then use `make' to compile
the program.
Language: C.
Author: A.V. Goldberg.
Version: CS version 1.1.
Size: 10 KB in .tar.z form.
Description: CS is a code for solving capacitated transportation problems. The
program reads the standard input and writes to the standard output.
The input must be in the DIMACS min-cost flow format. The program
takes an optional scale factor parameter. The program is a slightly
modified version of the program described in the paper "An
Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm"
by A. V. Goldberg, IPCO '93 proceedings. An earlier version of the
paper appeared as a Stanford Technical Report STAN-CS-92-1439.
Comments:
Name: SPLIB
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/goldberg directory.
File: splib.tar.z
Platform: BSD Unix with C compilers.
Install: uncompress then unpack the .tar file, then run `make' to compile
the program.
Language: C.
Author: Boris Cherkassky (cher@ch.comrel.msk.su),
Andrew Goldberg (goldberg@cs.stanford.edu),
and Tomasz Radzik (radzik@cs.cornell.edu).
Version: SPLIB version 1.0, 7/19/93.
Size: 42 KB in .tar.z form.
Description: SPLIB contains codes, generators, and generator inputs for
shortest paths algorithms. For a detailed description, see
"Shortest Paths Algorithms: Theory and Practice,"
by B.V. Cherkassky, A.V. Goldberg, and T. Radzik, Technical
Report STAN-CS-93-1480, Computer Science Department, Stanford
University, Stanford, CA, 1993. In addition to the algorithms
evaluated in the technical report, SPLIB contains code "dikf"
that implements Dijkstra's algorithm using Fibonacci heaps.
All programs read from the standard input and write to the
standard output.
Comments:
Name: AUGMENT
Site: ftp://elib.zib-berlin.de in /pub/optnet/software/augment
File: augment.tar.gz
Platform: machines who support ANSI C.
Install: "gunzip" plus "tar -xf", then compile with Makefile.
Language: ANSI C.
Author: Michael Bussieck, on.bussieck@zib-berlin.de,
or: bussieck@moa.math.nat.tu-bs.de.
Version:
Size: 86K in tar.gz form.
Description: Suppose that k is a positive integer. This program computes the
smallest increase in the capacities of an integrally capacitated
network so that the edge connectivity numbers is at least k.
Comments:
Name: maxflow
Site: ftp://elib.zib-berlin.de in /pub/mathprog/maxflow
File: files in directories solver-1, solver-3, solver-4.
Platform: C compilers.
Install: use makefile.
Language: C
Author: see Description below.
Version:
Size: 40k source code in solver-1, 300K in solver-3 and 180K in solver-4.
Description: Codes for solving the maximum flow problem in directed and
undirected graphs using the algorithms of Goldberg, Dinic,
and Cheriyan & Hagerup.
In directory solver-1: Goldberg maximum flow algorithm for
undirected graphs written by Ed Rothberg, see A.V. Goldberg/R.E.
Tarjan: "A New Approach to the Maximum Flow Problem", Proc.
18th ACM Symp. on Theory of Computing, 1986.
In directory solver-3: Goldberg and Dinic maximum flow algorithms
for directed graphs written by R. Anderson and J. Setubal, see
article under solver-1 and E.A. Dinic "Algorithm for solution of
a problem of maximum flow in networks with power estimation",
Soviet Math. Dokl. 11 (1980).
In directory solver-4: Cheriyan & Hagerup PLED maximum flow
algorithm for directed graphs implemented by T. Badics,
see J. Cherian and T. Hagerup: "A Randomized Maximum-Flow
Algorithm", Proc. IEEE FOCS (1989).
Comments:
Name: GOLD
Site: ftp://dimacs.rugters.edu in directory
/pub/netflow/maxflow/solver-5
File: GOLD-source.shar
Platform: Unix.
Install: Run GOLD-source.shar in /bin/sh shell, then use "make" to
compile the programs.
Language: C.
Author: Tamas Badics, badics@rutcor.rugters.edu.
Version:
Size: 80 KB source codes.
Description: This package contains the GOLD Maxflow algorithm based on
A. Goldberg's preflow-push algorithm.
Comments:
Name: MAXFLOW
Site: ftp://dimacs.rugters.edu in
directory /pub/netflow/submit/setubal
File: all C files.
Platform: C compilers.
Install: compiled with C compilers.
Language: C.
Author: Richard Anderson, anderson@cs.washington.edu,
Joao Setubal, setubal@cs.washington.edu.
Version:
Size: 2 KB ~ 14 KB for each source code.
Description: This directory contains the source code and executables for the
maximum-flow problem. The code is not commented for the most
part, and it contains several variants of maximum-flow
algorithms. The 3 executables that the makefile generates are
the following:
gold_q: goldberg's algorithm using a queue to select active
vertices. It corresponds to procedure Goldberg1 in file
goldberg.c.
gold_hlf: goldberg's algorithm using highest label first
criterion. It corresponds to procedure Goldberg2 in file
goldberg.c.
dinic: dinic's algorithm. Relevant code in procedure AugmentFlow
in main_dinic.c and in file dinic.c (look for option DINIC_NEW
in the code).
Comments:
Name: mininum_mean_cycle
Site: ftp://elib.zib-berlin.de in /pub/mathprog/netopt-misc
File: files in directory mmc.
Platform: C compilers.
Install: use makefile.
Language: C.
Author: see Description.
Version:
Size: less than 20K source codes.
Description: Algorithm for determining "minimum mean cycle" in a directed
graph, see N.E. Young, R.E. Tarjan, J.B. Orlin: "Faster Parametric
Shortest Path and Minimum-Balance Algorithms", Networks 21 (1991),
205-221, implementation by G. Skorobohatyj.
Comments:
Name: mincut
Site: ftp://elib.zib-berlin.de in /pub/mathprog/mincut
File: files in directories /all-pairs, /global-undir, /global-dir, /odd.
Platform: C compilers.
Install: use makefile.
Language: C
Author: see Description.
Version:
Size: less than 20 KB source codes in all-pairs, 30 KB in global-undir, 25 KB in global-dir, 35K in odd.
Description: Codes for solving some minimum cut problems in directed and
undirected graphs.
In /all-pairs: Code for solving the "all pairs" minimum cut
problem in undirected graphs, see R.E. Gomory and T.C. Hu:
"Multi-Terminal Network Flows", SIAM J, Applied Math. 9 (1961),
551-570, for problem specification and D. Gusfield: "Very
Simple Algorithms and Programs for All Pairs Network Flow
Analysis", Computer Science Division, University of California,
Davis, 1987, for a description of underlying algorithm,
implementation by G. Skorobohatyj.
In /global-undir: Code for solving the "global" minimum cut
problem in undirected graphs, see J.Hao/ J.B. Orlin:
"A Faster Algorithm for Finding the Minimum Cut in a Graph",
Proc. of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms,
Orlando, Florida, 1992, for a description of underlying algorithm,
implementation by G. Skorobohatyj.
In /global-dir: Code for solving the "global" minimum cut problem
in directed graphs, see J.Hao/ J.B. Orlin: "A Faster Algorithm
for Finding the Minimum Cut in a Graph", Proc. of the 3rd Annual
ACM-SIAM Symposium on Discrete Algorithms, Orlando, Florida,
1992, for a description of underlying algorithm, implementation
by G. Skorobohatyj.
In /odd: Code for solving the "odd" minimum cut problem in
undirected graphs, see M.W. Padberg/ M.R. Rao: "Odd Minimum
Cut-Sets and b-Matchings", Mathematics of Operations research,
Vol. 7, No. 1, 1992, for problem specification and description
of underlying algorithm, implementation by G. Skorobohatyj.
Comments:
Name: SHPTHL
Site: ftp://netlib.att.com in /netlib/toms
File: 562.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: U. PAge
Version:
Size: 12 K source code.
Description: This code calculates the shortest path lengths from a specific
node to all other nodes in a network and the shortest paths
between this node and other nodes. Please refer ACM TOMS 6 (1980)
450-455.
Comments:
Name: FCNO (FORTRAN Codes for Network Optimization).
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/Network directory.
File: fortran files in subdirectories, see Description.
Platform: Fortran compilers.
Install: Run f77 to compile the programs.
Language: FORTRAN.
Author:
Version:
Size: 720 KB source codes.
Description: This contains 7 subdirectories with the FORTRAN codes
corresponding to the algorithms presented in the 7 chapters of
the volume " FORTRAN Codes for Network Optimization ", (G. Gallo,
F. Maffioli, S. Pallottino, B. Simeone and P. Toth eds. ), Annals
of Operations Research 7, 1988. Each subdirectory also contains
one or more input data files ( called XXX.INP ) for the test of
the FORTRAN codes.
Each FORTRAN file contains, in addition to the subroutines
corresponding to the algorithm, a simple Main Program which reads
the input data from File #5, calls the main subroutine, and writes
the results on File #6.
1. Subdirectory /SP: " Shortest Path Algorithms ".
FORTRAN Files : L2QUE.FOR; LDEQUE.FOR; LQUEUE.FOR; LTHRS.FOR;
SDIAL.FOR; SDKSTR.FOR; SHEAP.FOR; SORD2.FOR.
Input data File : SP.INP ( for all FORTRAN files ).
2. Subdirectory /MF: " A Computational Comparison of the Dinic
and Network Simplex Methods for Maximum Flow ".
FORTRAN File : DNSUB.FOR.
Input data File : MF.INP.
3. Subdirectory /MCF: " The RELAX Codes for Linear Minimum-Cost
Network Flow Problems ".
FORTRAN Files : RELAX.FOR; RELAXT.FOR; SENSTV.FOR.
Input data File : MCF.INP.
4. Subdirectory /A: " Algorithms and Codes for the Assignment
Problem ".
FORTRAN Files : APC.FOR; APS.FOR.
Input data Files : APC.INP ( for file APC.FOR); APS.INP (for file
APS.FOR ).
5. Subdirectory /NBM: " Solving Non-Bipartite Matching Problems
via Shortest Path Techniques ".
FORTRAN File : SAP.FOR.
Input data File : NBM.INP.
6. Subdirectory /ST: " Algorithms for Finding Optimum Trees :
Description, Use and Evaluation ".
FORTRAN Files: CAM.FOR; KRUS.FOR; ORD.FOR; PRIM.FOR; YAO.FOR.
Input data Files: ST.INP ( for files CAM.FOR, KRUS.FOR and
YAO.FOR); ORD.INP (for file ORD.FOR);
PRIM.INP ( for file PRIM.FOR).
7. Subdirectory /KSE: " A Hybrid Algorithm for Finding the K-th
Smallest of n Elements in O(n) Time ".
FORTRAN File : KSMALL.FOR.
Input data File : KSE.INP.
Comments:
***** Graph Theory Codes *****
Name: GAP
Site: ftp://dimacs.rutgers.edu in /pub/gap
File: gap3r3p0.zoo, unzoo.c
Platform: C compilers or get executable codes from /bin for different
platform.
Install: Compile the zoo archive extractor 'unzoo' with the command
cc -o unzoo -DSYS_IS_UNIX -O unzoo.c
Unpack the distribution with the command
unzoo -x -o gap3r3p0.zoo
Change into the source directory 'gap3r3p0/src/', print the
list of possible targets with the command 'make', select the
target that fits best, and then compile the kernel with the
command
make
cp gap ../bin
Language: GAP language.
Author: Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE.
Version: Version 3 release 3, patch level 0, or GAP 3.3 for short.
Size: 7 MByte of 'zoo' archive.
Description: GAP is a system for computational discrete algebra, which we
have developed with particular emphasis on computational group
theory, but which has already proved useful also in other areas.
The name GAP is an acronym for *Groups, Algorithms, and
Programming*.
Comments:
Name: GROW
Site: ftp://netlib.att.com in /netlib/toms
File: 479.Z
Platform: fortran compilers.
Install: uncompress, and then compiled with fortran.
Language: Fortran.
Author:
Version:
Size: 34K source code.
Description: This code solves the minimal spanning tree and point clustering
problem. The algorithm appeared in COMM. ACM, Vol. 17, No. 06,
P. 321.
Comments:
Name: HC
Site: ftp://netlib.att.com in /netlib/toms
File: 595.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: S. Martello.
Version:
Size: 24 K source code.
Description: This code finds one or more Hamiltonian circuits in a directed
graph. Please refer ACM TOMS 9 (1983) 131-138.
Comments:
Name: MSTPAC
Site: ftp://netlib.att.com in /netlib/toms
File: 613.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: R.E. Haymond, J.P. Jarvis, and D.R. Shier.
Version:
Size: 12 K source code.
Description: This code finds the minimum spanning tree for moderate integer
weights in a connected undirected graph represented in a forward
star data structure.graph. Please refer ACM TOMS 10 (1984)
108-111.
Comments:
Name: pardalos3
Site: ftp://dimacs.rugters.edu under the directory
/pub/challenge/graph/contributed/pardalos.
File: pardalos3.f.
Platform: Fortran compilers.
Install: Compile with fortran compilers.
Language: Fortran
Author: PANOS M. PARDALOS AND RANDY CARRAGHAN.
Version:
Size: 7 KB source codes.
Description: This code implements an efficient partial enumerative algorithm
for the maximum clique problem. The algorithm is described in
details in: R. Carraghan and P.M. Pardalos, An exact algorithm for
the maximum clique problem, operations research letter 9 (1990),
pp. 375-382.
Comments:
Name: pardalos4
Site: ftp://dimacs.rugters.edu under the directory
/pub/challenge/graph/contributed/pardalos.
File: pardalos4.f.
Platform: Fortran compilers.
Install: Compile with fortran compilers.
Language: Fortran.
Author: PANOS M. PARDALOS AND GREGORY P. RODGERS.
Version:
Size: 8 KB source codes.
Description: This code implements an quadratic zero-one programming based
algorithm for the maximum clique problem. The algorithm is
described in details in: P.M. Pardalos and G.P. Rodgers, "A branch
and bound algorithm for the maximum clique problem", Operations
Research, Vol. 19, No. 5 (1992), pp. 363-375.
Comments:
Name: dfmax
Site: ftp://dimacs.rugters.edu in directory /pub/dsj/clique
File: dfmax.c
Platform: C compilers.
Install: Compiled with C compilers.
Language: C.
Author: D.S. Johnson, AT&T Bell Laboratories, Murray Hill, NJ 08544.
Version:
Size: 8 KB source codes.
Description: This code implements a simple-minded branch-and-bound
algorithm very similar to that of Carraghan and Paradalos
[Oper. Res. Lett. 9 (1990), 375-382] to solve the maximum
clique problem. Subproblems are pruned only when the
number of vertices still eligible for the clique is not
enough to unseat the current champion. This C code,
written by David Applegate and David Johnson, has a somewhat
tighter inner loop than does the C&P Fortran code, and runs
significantly faster on a variety of architectures. It assumes
a 32-bit word length, but otherwise should be reasonably
portable. It appears to compile successfully under both ANSI
and non-ANSI C-compilers. On an SGI Challenge computer (comparable
to a DEC Alpha or a Sun SPARCstation 10), it can handle a 500
vertex, p=0.5 random graph in 3 minutes. A summary of results of
the SGI Challenge for random graphs and the DIMACS benchmarks is
in the file results.dfmax.
Comments: To aid in comparisons between papers on the clique problem,
the DIMACS Challenge Steering Committee is making available
two benchmark programs, dfmax.c and dmclique.c. Whether you
are studying exact or approximate algorithms, this code can
serve as a simple benchmark for calibrating your machine's
speed relative to those of the other participants.
If possible, please compile and run it on the supplied p=0.5
random graphs r100.5.b, r200.5.b, r300.5.b, r400.5.b, and
r500.5.b and report your times. For comparison purposes, the
SGI Challenge "user" times (not counting input time) for one
run on each graph were 0.08, 1.00, 7.87, 47.68, and 179.98
seconds, respectively. The code can also be used as a common
point of reference for papers implementing exact clique
algorithms. It is easily beaten on dense graphs (average degree
exceeding $|V|/2$) but may be hard to beat on sparser graphs,
especially random ones.
Name: dmclique
Site: ftp://dimacs.rugters.edu in directory /pub/dsj/clique
File: dmclique.c, nmclique.c
Platform: C compilers.
Install: Compiled with C compilers.
Language: C.
Author: D.S. Johnson, AT&T Bell Laboratories, Murray Hill, NJ 08544.
Version:
Size: 11 KB source codes.
Description: dmclique.c is a variant on the simple "semi-exhaustive
greedy" scheme for finding large independent sets used in the
graph coloring algorithm XRLF described in Johnson et. al.
[Oper.Res. 39 (1991), 378-406], originally suggested by Matula
and Johri. dmclique has four integer input parameters, SETLIM,
TRIALNUM, CANDNUM, and ITERATIONS, of which the key parameters
are SETLIM and CANDNUM. The algorithm proceeds as follows:
At any given time there is a set C (initially empty) of
vertices in the current clique, and a set U consisting of all
those remaining vertices that are adjacent to all members of C.
If |U| <= SETLIM, the branch-and-bound code of dfmax (without the
initial C&P pre-ordering) is invoked to find the maximum clique in
U, and this is added to C. Otherwise, we sample CANDNUM vertices
(with replacement) and choose one with maximum degree
(ties broken in favor of the earlier index). The chosen vertex is
then added to C, U is updated, and we repeat. We then repeat
the entire process TRIALNUM x ITERATIONS times.
Algorithm dmclique algorithm has much in common with the "GRASP"
algorithm of Feo and Resende, except the latter sets SETLIM = 0
and uses a final local optimization phase to improve the clique
found, typically with slightly better results than are obtained
with dmclique. The value of dmclique as a benchmark code (as
with dfmax) is that it represents what can be obtained by a
(relatively) efficient implementation of the most
straightforward of ideas. nmclique.c is a new version of
dmclique.c that prints out the best clique found.
Comments: To aid in comparisons between papers on the clique problem,
the DIMACS Challenge Steering Committee is making available
two benchmark programs, dfmax.c and dmclique.c. If your paper
is on approximation algorithms
for clique, this code should serve as a useful standard for
comparison. Ideally you should re-run the tests summarized
in "results.dmclique" on your own machine (for those instances
you ran your own code on). If time does not allow, an acceptable
substitute would be to scale the times reported there by
the "dfmax r500.5.b" speed-up (slow-down) factor between your
machine and the SGI Challenge.
Name: wmatch
Site: ftp:// elib.zib-berlin.de in /pub/mathprog/matching/weighted
File: all files in the directory.
Platform: C compilers.
Install: see makefile.
Language: C.
Author: Ed Rothberg based on H. Gabow's N-cubed weighted matching
algorithm.
Version:
Size: 65K source codes.
Description: Code for finding a maximum weight matching in an undirected
graph. It is based on H. Gabow's N-cubed weighted matching
algorithm, as described in his Ph.D. thesis "Implementation of
Algorithms for Maximum Matching on Nonbipartite Graphs"
Stanford University, 1973.
Comments:
Name: match
Site: ftp:// elib.zib-berlin.de in /pub/mathprog/matching/card1
File: all files in the directory.
Platform: C compilers.
Install: see makefile.
Language: C.
Author: Ed Rothberg based on H. Gabow's N-cubed non-weighted matching
algorithm.
Version:
Size: 55K source codes.
Description: C code for solving the cardinality matching problem based
on Gabow's N-cubed non-weighted matching algorithm, see H.N.
Gabow: "An Efficient Implementation of Edmond's Algorithm
for Maximum Matching on Graphs", JACM, Vol. 23, 1976.
Comments:
Name: cardmp
Site: ftp:// elib.zib-berlin.de in /pub/mathprog/matching/card2
File: cardmp.f.
Platform: Fortran compilers.
Install: Use fortran compilers.
Language: Frotran 77.
Author: R.B. Mattingly and N.P. Ritchey.
Version:
Size: 36K source codes.
Description: FORTRAN Code for solving the cardinality matching problem
based on the Micali-Vazirani algorithm, see S. Micali/ V.V.
Vazirani: "An $O(\sqrt{ V * E})$ Algorithm for Finding
Maximum Matching in General Graphs", Proc. 21st Annual
Symposium on Foundation of Computer Science, IEEE, 1980.
Comments:
Name: cardmatch
Site: ftp://dimacs.rugters.edu under the directory
/pub/netflow/matching/cardinality/solver-2
File: cardmatch.p
Platform: Pascal compilers.
Install: Use Pascal compilers.
Language: Pascal.
Author: Steven Crocker, crocker@cs.uchicago.edu
Version:
Size: 41 KB source codes.
Description: PASCAL Code for solving the cardinality matching problem
based on the Micali-Vazirani algorithm, see S. Micali/ V.V.
Vazirani: "An $O(\sqrt{ V * E})$ Algorithm for Finding
Maximum Matching in General Graphs", Proc. 21st Annual
Symposium on Foundation of Computer Science, IEEE, 1980.
Comments:
Name: color_loop
Site: ftp://dimacs.rugters.edu under the directory
/pub/challenge/graph/contributed/morgenstern/morgenstern3.
File: All files.
Platform: C compilers.
Install: Use Makefile.
Language: C
Author: C. Morgenstern, morgenst@riogrande.cs.tcu.edu.
Version:
Size: 20 KB source codes.
Description: This package contains an implementation of a localized
backtracking heuristic for 4-coloring planar graphs and
very sparse general graphs. This code is based on methods
discussed in
C. Morgenstern and H. Shapiro. 1991, Improved Implementations of
Dynamic Sequential Coloring Algorithms, Tech Report CoSc-1991-4,
Texas Christian University, Fort Worth, Texas.
C. Morgenstern, 1992, A New Backtracking Heuristic for Rapidly
Four-Coloring Large Planar Graphs. Tech Report CoSc-1992-2,
Texas Christian University, Fort Worth, Texas.
Comments:
Name: dyn_tree
Site: ftp://dimacs.rugters.edu under the directory
/pub/netflow/program_tool/dynamic_trees
File: dyn_tree.shar.
Platform: Unix.
Install: First run dyn_tree.shar file in /bin/sh shell. Then user need only
the dyn_tree.h header file and the object files which can be
created with the enclosed makefile. All the other sourcefiles
could be referred to as a black box. So the first step is to make
the objects with gcc. (type make dyn_tree)
Language: C.
Author: Tamas Badics, badics@rutcor.rutgers.edu
Version:
Size: 22K source codes in ".shar" form.
Description: The code performs Dynamic tree data structure operations
Based on Sleator, Tarjan : Self-Adjusting Binary Search Trees
JACM Vol. 32., No. 3, July 1985 pp.652-686. The main purpose of
using this data structure is to deal with trees of any type of
objects with a value associated with them.
Comments:
***** Codes for Satisfiability Problem *****
Name: sato
Site: ftp://dimacs.rugters.edu under the directory
/pub/challenge/sat/contributed/zhang.
File: sato.tar.Z.
Platform: C compilers.
Install: Use tar -xf, then use Makefile.
Language: C.
Author: Hantao, Zhang, hzhang@cs.uiowa.edu.
Version:
Size: 74 KB in ".tar.Z".
Description: Sato is a decision procedure for testing satisfiability of ground
clauses.It includes the following branching procedures: (1) select
the first minimal atom; (2) select an atom in shortest positive
clauses (default); (3) a variant of (2); (4) select an atom with
most occurrences; (5) select an atom with most occurrences in
all/binary clauses; (6) select an atom with most Jeroslow-Wang
weight.
Comments:
***** Codes for Travelling Salesman Problem *****
Name: tsp_solve
Site: e-mail request to churritz@crash.cts.com.
File:
Platform: Borland, sco and Sun with gcc.
Install:
Lagguage: C++.
Author: Chad Hurwitz, churritz@crash.cts.com and
Robert. J. Craig, kat3@uscbu.ih.att.com, etc.
Version: 1.0 beta.
Size:
Description: Finds Optimal and Heuristic Solutions to many types of TSP.
Comments: tsp_solve finds optimal solutions to geometric TSPs with 100
cities in about one hour (don't go to lenscrafters for this
one.) It will soon have an asymmetric TSP optimal solution
finder that will perform at approximately the same level.
***** Codes for Scheduling Problem *****
Name: ARSME.
Site: ftp://netlib.att.com in /netlib/toms
File: 520.Z
Platform: fortran compilers.
Install: uncompress, and then compiled with fortran compilers.
Language: Fortran.
Author: Weglarzel et. al.
Version:
Size: 15K source code.
Description: This code solves a multiple-resource network scheduling problem
-- preemptive case (activities arbitrarily interrupted and
restarted later without increase in activitity dueation. Use the
revised simplex method with the product form of the inverse.
"activities-on-arcs" network representation is used. Algorithm
appeared in ACM TOMS 3 (1977) 295-300.
Comments:
Name: akraemer_MPM
Site: ftp://elib.zib-berlin.de in /pub/opt-net/software/akraemer
File: akraemer_MPM.tar.gz
Platform: machines with C compilers.
Install: "gunzip" plus "tar -xf", then compile with Makefile, or use the
executable codes directly if on Sun 4 workstations.
Language: C
Author: Andreas Kraemer, AKRAEMER@dosuni1.rz.Uni-Osnabrueck.DE
Version:
Size: 384K in tar.gz form.
Description: Algorithms for solving job-shop scheduling problems with
multi-purpose machines are now available. The package contains
heuristics for calculating approximate solutions (using tabu
search and beam search), a branch and bound method for solving
such problems exactly, and algorithms to calculate lower bounds.
See readme file in MPM directory after unpacking for details.
Comments:
***** Codes for Assignment Problem *****
Name: CSAS
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/goldberg directory.
File: csas.tar.z
Platform: C compilers.
Install: uncompress then unpack the .tar file, then see README in directory
csa before using the Makefile.
Language: C.
Author: Robert Kennedy, (robert@cs.stanford.edu), based on A.V. Goldberg's
cost-scaling push-relabel algorithm.
Version: July, 1993. First distribution.
Size: 63 KB in .tar.z form.
Description: CSA uses a cost-scaling push-relabel algorithm to solve assignment
problems. Two basic versions of the source code (with considerable
overlap) are provided: a precise-costs version and a rounded-costs
version. The rounded-costs version was developed to determine
whether working with integer units of epsilon within a scaling
iteration (and hence using only integer arithmetic except to
compute the rounded costs prior to each iteration) would provide
a performance gain. On our machine, it did not.
Although it would be a simple matter to fix this (and we might
make a later version with this change), THE CODE ASSUMES
EXISTENCE OF A PERFECT MATCHING in the input assignment problem.
No checks are made for this condition. If this condition does not
hold, the code will run forever, unless there are fewer nodes on
the left-hand side than on the right (in which case the computed
assignment is liable not to be optimal).
After unpacking the .tar file, there are three subdirectories under
the directory csas: csa, dimacs, pictures. The `csa' contains two
subdirectories `pre_costs' and `round_costs' for the respective
versions of the algorithm. The `dimacs' contains programs that
generate networks and graphs. Most are in the DIMACS format. For
the others, format translators are or will soon be available.
Generators suitable for multiple problems are in this
directory---problem-specific generators appear in subdirectories.
In directory `picture', the program p5pgmtoasn.c is available to
reads a "P5" format portable grey map image from its standard input
and writes an assignment problem in DIMACS format on its standard
output.
Comments:
Name: ASSCT
Site: ftp://netlib.att.com in /netlib/toms
File: 548.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: G. Carpaneto and P. Toth.
Version:
Size: 6K source code.
Description: This code solves the square assignment problem using Hungarian
algorithm. Please refer to ACM TOMS 6 (1980) 104-111.
Comments:
Name: HGW
Site: ftp://netlib.att.com in /netlib/toms
File: 608.Z
Platform: fortran compilers.
Install: uncompress, and then compiled with fortran compilers.
Language: Fortran.
Author: D.H. West.
Version:
Size: 20 K source code.
Description: This code solves the extended Koopmans-Beckmann quadratic
assignment problem heuristically. It computes a permutation L
of 1:N to approximately minimize the objective function:
OBJ=SUM/I=1 TO N/(C(I,LI)+SUM/J=1 TO N/(F(I,J)*D(LI,LJ)) where
LI,LJ are the image of I, J under L. Neither F nor D is assumed
symmetric, but their diagonal elements are zero. Please refer
ACM TOMS 9 (1983) 461-466.
Comments:
Name: rts_qap (Reactive Tabu Search for Quadratic Assignment Problem).
Site: http://rtm.science.unitn.it/volterra-ftp/code/rts_qap.
File: rts_qap-1.0.tar.gz.
Platform: systems with ANSI C compilers.
Install: gunzip + tar -xf, then use "make" to install.
Language: C.
Author: R. Battiti and G. Tecchiolli, battiti@science.unitn.it.
Version: 1.0
Size: 33 KB in tar.gz form..
Description: Reactive Tabu Search is a heuristic algorithm based on Fred
Glover's Tabu Search. It is based on new local search techniques
that use feedback both to adaptively determine parameters and to
obtain a suitable balance of intensification and diversification.
Basic RTS routines and specific ones for the Quadratic Assignment
Problem are available.
Comments:
***** Codes for Goal Programming *****
Name: PAGP (The Partitioning Algorithm for Goal Programming).
Site: ftp://netlib.att.com in /netlib/toms
File: 557.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: J.L. Arthur and A. Ravindran.
Version:
Size: 30K source code.
Description: This code solves the linear goal programming problem. The
algorithm partitions the goal constraints of the problem
according to the highest priority assigned to either deviational
variable (D- or D+) in each goal. The algorithm is thus able to
solve a sequence of smaller problems in order to find a solution
to the original problem. Please refer to ACM TOMS 6 (1980) 429.
Comments:
***** Codes for Facility Location Problem *****
Name: LOCATE
Site: ftp://netlib.att.com in /netlib/toms
File: 558.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: T. Cheung.
Version:
Size: 27K source code.
Description: This code solves the one-dimensional multifacility location
problem with rectilinear distance.It uses the minimum-cut
approach proposed by Picard and Ratliff (see Operations Research
26 (1978), pp. 422-433). Please refer to ACM TOMS 6 (1980)
430-431.
Comments:
***** Codes for Knapsack Problem *****
Name: MKP
Site: ftp://netlib.att.com in /netlib/toms
File: 632.Z
Platform: fortran compilers.
Install: uncompress, and compiled with fortran compilers.
Language: Fortran.
Author: S. Martello and P. Toth.
Version:
Size: 21K source code.
Description: This code solves the 0-1 multiple knapsack problem. Please refer
to ACM TOMS 11 (1985) 135-140.
Comments:
***** Simulated Annealing Codes *****
Name: ASA (Adaptive Simulated Annealing)
Site: ftp://ftp.alumni.caltech.edu in /pub/ingber
File: ASA-shar.
Platform: many platforms with C compilers.
Install: run "sh ASA-shar" to unshar the archive, then see README file to
run the "make".
Language: C.
Author: Lester Ingber, ingber@alumni.caltech.edu
Version: Version 6.26
Size: 1.02 MB for the archive.
Description: The ASA code was first developed in 1987 as Very Fast
Simulated Reannealing (VFSR) to deal with the necessity of
performing adaptive global optimization on multivariate nonlinear
stochastic systems. VFSR was recoded and applied to several
complex systems, in combat analysis, finance, and neuroscience.
Beginning in January 93, many adaptive features were
developed, largely in response to users' requests, leading to
this ASA code. ASA has been examined in the context of a review
of methods of simulated annealing using annealing versus
quenching (faster temperature schedules than permitted by basic
heuristic proof of ergodicity). ASA is now used world-wide
across many disciplines.
ASA is believed to be faster and more robust than other simulated
annealing techniques for most complex problems with multiple
local optima; again, be careful to note that some problems are
best treated by other algorithms. If you do not know much
about the structure of your system, and especially if it has
complex constraints, and you need to search for a global
optimum, then this ASA code is heartily recommended to you.
Comments:
Name: SA
Site: ftp://usc.edu under /pub/C-numanal
File: sa.tar.gz
Platform: UNIX or MSDOS with C, C++ or Ada.
Install: gunzip + tar -xf, then use "make". See Readme file.
Language: C, C++ or Ada.
Author: Everett (Skip) Carter, skip@taygeta.oc.nps.navy.mil.
Version: Beta version.
Size: 30.8 KB in tar.gz form.
Description: When one trys to estimate such things as the minimum, or the
least-squares optimal parameters of a nonlinear system, the
existence of multiple local minima can cause problems with the
determination of the global optimum. Simulated annealing is a
technique for solving such problems. It works by following local
gradients, but occasionally it will move against the gradient in
order to escape a local extremum.
The attached code implements a straightforward Simulated
Annealing package. There are three versions of the package, one
in C, one in C++ and one in Ada.
Comments:
Name: SDSC EBSA (SDSC Ensemble Based Simulated Annealing)
Site: ftp://ftp.sdsc.edu (198.17.47.33) in directory /pub/sdsc/math/Ebsa
File: specific for different architectures.
Platform: many platforms, including Convex C2 MP (ConvexOS 10.+), Cray
Research YMP and C90 series (Unicos v.7), DECstations (MIPS
ULTRIX4, Alpha OSF/1), HP 700/9000 (HP9000 CPU, HPUXA O/S), Intel
SSD Paragon (OSF/1 rel 1.1+), Silicon Graphics workstations (IRIX
versions 4 and 5), and Sun Microsystems Sparcstations (BSD/Solaris
4.1+)
Install: uncompress and tar -xf.
Language: C.
Author: Richard Frost, frost@sdsc.edu.
Version: Version 2.1.
Size: 434~922 KB on different machines in tar.Z form.
Description: SDSC EBSA is an Ensemble Based Simulated Annealing library for
both single and multi-processor systems. Our ensemble-based,
constant-speed approach is a true analog of annealing theory and
compares favorably with other heuristic optimization techniques.
Three types of parallelism are exploited for task distribution.
The package includes diagnostic profiling to assist with the
determination of annealing parameters. At the user's option some
initializations can be performed adaptively. A sub-library for
visual performance monitoring has been implemented on SGI
workstations.
This is a binary library release with example applications and
source code provided.
Comments:
***** Parallel Computing Codes ******
Name: PCN (Program Composition Notation).
Site: ftp://info.mcs.anl.gov in /pub/pcn
File: pcn_v2.0.tar.Z
Platform: delta, ipsc860, iris, next040, rs6000 and sun4.
Install: Use "uncompress" plus "tar -xf", then see INSTALL.
Language: C.
Author: Ian Foster and Steven Tuecke
Version: v2.0.
Size: 2.8 MB in .tar.Z form, 9 MB after uncompress.
Description: PCN is a system for developing and executing parallel programs.
It comprises a high-level programming language, tools for
developing and debugging programs in this language, and
interfaces to Fortran and C that allow the reuse of existing
code in multilingual parallel programs. Programs developed using
PCN are portable across many different workstations, networks,
and parallel computers.
Comments:
***** Codes for Non-linear Optimization *****
Name: ASCEND
Site: ftp://ftp.cs.cmu.edu at /project/ascend directory.
File: ascend3.tar.Z under directory gnu-ascend.
Platform: Unix.
Install: uncompress and unpack, then see instructions for installation.
Language: C, PASCAL and FORTRAN.
Author: Karl Westerberg, contact ascend+ftp@cs.cmu.edu.
Version: ASCEND3
Size: About 11.2 MB source codes in .tar.Z form.
Description: ASCEND is a software system for building, debugging, and solving
mathematical models in a hierarchical (some would say object
oriented) manner. It is a product of Arthur Westerberg and his
students over the last two decades. It has its own modeling
language. It is GNU window based and has various tool kits such
as SOLVER, SIMULATION, BROWSER and DEBUGGER. It is currently being
ported to C/TCL/TK and we hope to make it available here once we
finish taking care of the legalities and the bug testing.
Comments: The documentations are not complete in the ftp site.
Name: SUBPLEX
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/NonLP directory.
File: subplex
Platform: FORTRAN compilers.
Install: Run "/bin/sh subplex", then edit the Makefile as necessary
and type "make". This will create a linkable library named
subplex.a and a demonstration executable named demo.
Language: FORTRAN.
Author: Tom Rowan, na.rowan@na-net.ornl.gov.
Version:
Size: 53 KB in executable shell file.
Description: Subplex is a subspace-searching simplex method for the
unconstrained optimization of general multivariate functions.
Like the Nelder-Mead simplex method it generalizes, the subplex
method is well suited for optimizing noisy objective functions.
The number of function evaluations required for convergence
typically increases only linearly with the problem size, so for
most applications the subplex method is much more efficient than
the simplex method.
Comments:
Name: PDS
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/NonLP directory.
File: pds.tar.z
Platform: FORTRAN compilers.
Install: uncompress and unpack, then call the subroutines provided.
Language: FORTRAN.
Author: Virginia Torczon.
Version:
Size: 28 KB in executable shell file.
Description: PDS is a collection of Fortran subroutines for solving
unconstrained nonlinear optimization problems using direct search
methods. The software is written so that execution on sequential
machines is straightforward while execution on Intel distributed
memory machines can be accomplished simply by including a few
well-defined routines containing calls to Intel-specific Fortran
libraries. Those interested in using the methods on other
distributed memory machines, even something as basic as a network
of workstations or personal computers, need only modify these few
subroutines to handle the global communication requirements.
PDS encompasses an entire class of general-purpose optimization
methods which require only that the user provide a subroutine to
evaluate the function. These methods require even less of the
problem to be solved since direct search methods presume only that
the function is continuous. Thus, parallel direct search methods
are particularly effective on parameter estimation problems
involving a relatively small number of parameters. They are also
very interesting as parallel algorithms because they are perfectly
scalable: they can use any number of processors regardless of the
dimension of the problem to be solved and, in fact, tend to
perform better as more processors are added.
Comments:
Name: MINPACK
Site: ftp://netlib.att.com at /netlib/minpack directory.
File: all files
Platform: FORTRAN compilers.
Install: uncompress and then use "make" to compile the programs.
Language: FORTRAN.
Author: Jorge More', Burt Garbow, and Ken Hillstrom
at Argonne National Laboratory
Version:
Size: About 190 KB source codes in .Z form.
Description: Minpack includes software for solving nonlinear equations and
nonlinear least squares problems. Five algorithmic paths each
include a core subroutine and an easy-to-use driver. The
algorithms proceed either from an analytic specification of the
Jacobian matrix or directly from the problem functions. The paths
include facilities for systems of equations with a banded Jacobian
matrix, for least squares problems with a large amount of data,
and for checking the consistency of the Jacobian matrix with the
functions. This directory contains the double-precision versions.
Comments:
***** Codes for Non-linear Network Optimization *****
Name: LSNNO (Large Scale Nonlinear Network Optimization).
Site: ftp://ftp.bilkent.edu.tr at /pub/IEOR/Opt/Network directory.
File: lsnno.tar.z
Platform: FORTRAN compilers.
Install: uncompress and unpack, then use "make" to compile the programs.
Language: FORTRAN.
Author: D. Tuyttens
Version:
Size: 110 KB in .tar.z form.
Description: LSNNO is a Fortran Subroutine designed to solve large scale
nonlinear network optimization problems, i.e. problems of the
form :
\[
\begin{array}{lc}
\min_{{\bf x} \in R^{n}} & f({\bf x})
\mbox{subject to} & A{\bf x} = b
& l \leq {\bf x} \leq u,
\end{array}
\]
where $f({\bf x})$ is a nonlinear {\em objective function}, that
is twice continuously differentiable on the feasible set defined
by the above constraints, where the matrix $A$ is a $m \times n$
node-arc incidence matrix, where the supply/demand vector $b$ is
in $R^{m}$ and satisfies $\sum_{i=1}^m b_i = 0$, and where the
vectors $l, u \in R^{n}$ are the lower and upper bounds on the
flows in the oriented network associated with $A$. The routine is
especially effective on problems involving a large number of
variables.
The basic method that is implemented by the routine LSNNO is
described in detail by Toint and Tuyttens (1989). The software
itself is described in Toint and Tuyttens (1992). The concept of
partial separability was first suggested by Griewank and Toint
(1982). The extensions of this concept to network constraints is
new.
The method used is iterative. At each iteration, a quadratic model
of the objective function is constructed. The step is determined
by using a truncated conjugate gradient algorithm, followed by a
linesearch. The strategy for treating bound constraints is based
on the usual projection device. This technique is similar to that
used by Bertsekas (1982).
Comments:
***** Linear System Solver *****
Name: LINPACK
Site: ftp://netlib.att.com at /netlib/linpack directory.
File: all files
Platform: FORTRAN compilers.
Install: uncompress and then use "make" to compile the programs.
Language: FORTRAN.
Author: Jack Dongarra, Jim Bunch, Cleve Moler and Pete Stewart.
Version:
Size: Around 200 KB source codes in .Z form.
Description: LINPACK is a collection of Fortran subroutines that analyze and
solve linear equations and linear least-squares problems. The
package solves linear systems whose matrices are general, banded,
symmetric indefinite, symmetric positive definite, triangular,
and tridiagonal square. In addition, the package computes
the QR and singular value decompositions of rectangular matrices
and applies them to least-squares problems. LINPACK uses
column-oriented algorithms to increase efficiency by preserving
locality of reference.
LINPACK was designed for supercomputers in use in the 1970s and
early 1980s. LINPACK has been largely superceded by
which has been designed to run efficiently on shared-memory, vector
supercomputers.
Comments:
Name: LAPACK
Site: ftp://netlib.att.com at /netlib/linpack directory.
File: lapack.tar.Z
Platform: FORTRAN compilers.
Install: uncompress and unpack, then see instruction for INSTALL.
Language: FORTRAN.
Author: Ed Anderson, Zhao-jun Bai, Chris Bischof, Jim Demmel,
Jack Dongarra, Jeremy Du Croz, Anne Greenbaum, Sven Hammarling,
Alan McKenney, Susan Ostrouchov, and Danny Sorensen.
Version:
Size: About 7.7 MB in .tar.Z form.
Description: LAPACK is a transportable library of Fortran 77 subroutines for
solving the most common problems in numerical linear algebra:
systems of linear equations, linear least squares problems,
eigenvalue problems, and singular value problems. It has been
designed to be efficient on a wide range of modern high-performance
computers.
LAPACK is intended to be the successor to LINPACK and EISPACK.
It extends the functionality of these packages by including driver
routines, iterative refinement and error bounds for linear systems,
the capability for finding selected eigenvalues and invariant
subspaces, and condition estimation for the eigenproblem. LAPACK
improves on the accuracy of standard algorithms for linear systems,
for finding singular values and singular vectors of bidiagonal
matrices, and for finding eigenvalues and eigenvectors of
tridiagonal matrices. The algorithms and software in the package
have been restructured to achieve high efficiency on vector
processors, high-performance "superscalar" workstations, and
shared memory multiprocessors. In addition to the LAPACK routines,
comprehensive testing and timing suite is provided along with the
LAPACK software.
Comments: