From xu@benji.Colorado.EDU Thu Apr 13 17:18:05 EDT 1995
Article: 3182 of sci.op-research
Xref: undergrad.math.uwaterloo.ca sci.op-research:3182
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 1]
Date: 13 Apr 95 05:22:25 GMT
Organization: University of Colorado at Boulder
Lines: 273
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
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.