------------------------------------------------------------------------ List of OR Codes in Public Domain[Part 1] From: xu@benji.Colorado.EDU (XU JIEFENG) Date: 13 Apr 95 05:22:25 GMT Organization: University of Colorado at Boulder Newsgroups: sci.op-research ------------------------------------------------------------------------ List of Interesting Optimization Codes in Public Domain Last Update: 04/10/95 Introduction ------------- This list is a collection of codes for optimization and related fields. Most codes are in public domain and can be retrieved via anonymous ftp. The collection concentrates on codes in network optimization, graph theory and other combinatorial optimization problems, and has a bias towards Unix platforms. This list is compiled by Jiefeng Xu of University of Colorado at Boulder. I hope this list is helpful, and welcome your additions, corrections and suggestions. I solicit comments on your experience in using these codes. I would like to include your input to this list to make it more informative and complete. Authors are encouraged to submit any new developments (freeware/shareware codes) to this list using the format described below. This list is currently maintained by Jiefeng Xu and will be updated periodically to accommodate the changes. Explanations of fields ---------------------- Name: the name of the archive. If no original name exists, I create something sensible. Site: ftp site or other site information from where you can retrieve the archive. File: the files you need to retrieve. Platform: the platform of the codes. Install: the installation of the codes, including unpack and decompression. Language: the language in which the codes were written. Author: the author of the codes and/or other contact address. Version: the version of the codes. Size: the size of the code. Description: the description of the codes. Most of them are excerpted from the README file of the software. This is meant to give readers more detailed information on what the code is, what it solves for and what it is based on. Comments: the users' evaluations, experience and comments. (welcome users to fill this entry). Summary of the list -------------------- This list currently contains 55 codes in 15 categories as follows: o Optimization Library -- LEDA (A Library of Efficient Data Types and Algorithms) o Generalized Linear Programming -- lp_solve (a code for generalized LP and MIP) -- LIPSOL -- Linear programming Interior-Point SOLvers -- LOQO -- an efficient implememtation of an interior-point method for large-scale linear and/or quadratic programming problems. -- minit (a linear progarmming package based on the dual simplex method). o Generalized Integer Programming -- opbdp (an implementation of an implicit enumeration algorithm solving linear 0-1 optimization problems). o Network Optimization -- RELAX-IV (a Fortran code for solving minimum cost flow problems). -- NETFLOW (algorithm for solving minimum cost flow problems). -- lopnet (codes for linear network optimization). -- CSMIN (C code for solving capacitated transportation problems). -- SPLIB (codes, generators, and generator inputs for shortest paths algorithms). -- AUGMENT (code for a specific network problem). -- maxflow (Codes for solving the maximum flow problem in directed and undirected graphs). -- GOLD (codes for the GOLD Maxflow algorithm based on A. Goldberg's preflow-push algorithm). -- MAXFLOW (codes for maximum-flow problem). -- minimum_mean_cycle (determined "minimum_mean_cycle" in a directed graph). -- mincut (solving some min-cut problems). -- SHPTHL (finds shortest paths from one specific node to the other nodes). -- FCNO (FORTRAN Codes for Network Optimization). o Graph Theory -- GAP (a system for computational discrete algebra, with particular emphasis on computational group theory). -- GROW (solves the minimal spanning tree and point clustering problem). -- HC (finds one or more Hamiltonian circuits in a directed graph). -- MSTPAC (minimum spanning tree for a graph). -- pardalos3 (an efficient partial enumerative algorithm for the maximum clique problem). -- pardalos4 (an quadratic zero-one programming based algorithm for the maximum clique problem). -- dfmax (a simple-minded branch-and-bound algorithm very similar to solve the maximum clique problem). -- dmclique (a variant on the simple "semi-exhaustive greedy" scheme for finding large independent sets). -- wmatch (Code for finding a maximum weight matching in an undirected graph). -- match (C code for solving the cardinality matching problem based on Gabow's N-cubed non-weighted matching algorithm). -- cardmp (FORTRAN Code for solving the cardinality matching problem based on the Micali-Vazirani algorithm). -- cardmatch (PASCAL Code for solving the cardinality matching problem based on the Micali-Vazirani algorithm). -- color_loop (a localized backtracking heuristic for 4-coloring planar graphs and very sparse general graphs). -- dyn_tree ( performs Dynamic tree data structure operations). o Satisfiability Problem -- sato (a decision procedure for testing satisfiability of ground clauses). o Travelling Salesman Problem -- tsp_solve (Finds Optimal and Heuristic Solutions to many types of TSP). o Scheduling Problem -- ARSME (solves a multiple-resource network scheduling problem -- preemptive case (activities arbitrarily interrupted and restarted later without increase in activitity duration). -- akraemer_MPM (Algorithms for solving job-shop scheduling problems with multi-purpose machines). o Assignment Problem -- CSAS (uses a cost-scaling push-relabel algorithm to solve assignment problems). -- ASSCT (solves the square assignment problem using Hungarian algorithm). -- HGM (solves the extended Koopmans-Beckmann quadratic assignment problem heuristically). -- rts_qap (Reactive Tabu Search for Quadratic Assignment Problem). o Goal Programming -- PAGP (The Partitioning Algorithm for Goal Programming). o Facility Location Problem -- LOCATE (solves the one-dimensional multifacility location problem with rectilinear distance). -- MKP (solves the 0-1 multiple knapsack problem). o Simulated Annealing -- ASA (Adaptive Simulated Annealing). -- SA (Simulated Annealing PAckage). -- SDSC EBSA (SDSC Ensemble Based Simulated Annealing). o Parallel Computing -- PCN (Program Composition Notation). o Non-linear Optimization -- ASCEND (a software system for building, debugging, and solving mathematical models in a hierarchical (some would say object oriented) manner). -- SUBPLEX (a subspace-searching simplex method for the unconstrained optimization of general multivariate functions). -- PDS (a collection of Fortran subroutines for solving unconstrained nonlinear optimization problems using direct search methods). -- MINPACK (a software for solving nonlinear equations and nonlinear least squares problems). o Non-linear Network Optimization -- LSNNO (Large Scale Nonlinear Network Optimization). o Linear System Solver -- LINPACK (a collection of Fortran subroutines that analyze and solve linear equations and linear least-squares problems). -- LAPACK (a transportable library of Fortran 77 subroutines for solving the most common problems in numerical linear algebra). Other Useful Lists ------------------- o Linear Programming - Frequently Asked Questions List by John W. Gregory, jwg@cray.com 612-683-3673 Applications Dept. Cray Research, Inc. Eagan, MN 55121 USA ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq o Noninear Programming - Frequently Asked Questions List by John W. Gregory, jwg@cray.com 612-683-3673 Applications Dept. Cray Research, Inc. Eagan, MN 55121 USA ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq o Neural-net-faq by prechelt@ira.uka.de (Lutz Prechelt) http://wwwipd.ira.uka.de/~prechelt/FAQ/neural-net-faq.html ftp://rtfm.mit.edu/pub/usenet/news.answers/neural-net-faq o The Hitch-Hiker's Guide to Evolutionary Computation (FAQ in comp.ai.genetic). by Joerg Heitkoetter c/o EUnet Deutschland GmbH, Techo-Park, Emil-Figge-Str. 80, D-44227 Dortmund, Germany or and David Beasley c/o Department of Computing Mathematics University of Wales, College of Cardiff Cardiff, United Kingdom ftp://rtfm.mit.edu:/pub/usenet/news.answers/ai-faq/genetic/ as the files: part1 to part6. o comp-constraints-faq. by Michael Jampel . ftp://ftp.cs.city.ac.uk [138.40.91.9]:/pub/constraints/comp-constraints-faq http://web.cs.city.ac.uk/archive/constraints/constraints.html o The index of resources for numerical computation in C or C++. by Ajay Shah, ajayshah@cmie.ernet.in. ftp://usc.edu/pub/C-numanal/numcomp-free-c.gz Acknowledgement --------------- This project is supported by Modeling Group, USWEST Advanced Technologies. I am grateful for their support and for generous permission to allow me to post this list. Thanks to Jenny Ryan of USWEST, as the supervisor of this project. Acknowledgements are also due to Cheryl Persinger of USWEST for her tremendous information collecting in the initial stage of this project. Finally, I thank all the authors on this list who contributed their works to the public and made this list possible. Contact Information ------------------- You can reach me by email at: Jiefeng.Xu@colorado.edu or by mail to: Jiefeng Xu Graduate School of Business University of Colorado at Boulder Campus Box 419 Boulder, CO 80309 U.S.A. Disclaimer ---------- This list is distributed only to individuals and institutions for non-commercial purposes by Jiefeng Xu in the hope that it will be useful but without any warranty. In no event will I, or any institutions with which I associate, accept responsibility to anyone for the consequences of using it or whether it serves any particular purpose or works at all. No warranty is made about the listed software or its performance. This list is for your information only and I hereby bear no responsibility about the correctness of its contents. Individual software listed below may have its own license and/or disclaimer information. In any case, please follow these specific information. Readers take their own responsibilities and risks to use any individual software in this list. Neither I nor any institutions with which I associate shall be liable for any violations of the license for individual software in this list by any of the readers. I reserve the rights to change contents and/or policies regarding this list. ------------------------------------------------------------------------