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: