## Optimization packages

This is an unorganized list of packages that have been announced and caught my attention. John Mitchell.
PACKAGE: ABACUS
From:    Michael Junger's group
Date:    last update August 2007


The following is taken from the

ABACUS is a software system written in C++ that provides a framework for the implementation of branch-and-bound algorithms using linear programming relaxations. Cutting planes or columns can be generated dynamically (branch-and-cut, branch-and-price, branch-and-cut-and-price).

ABACUS allows the software developer to concentrate merely on the problem specific parts, i.e., the separation of cutting planes, column generation, and primal heuristics. ABACUS supports the Open Solver Interface (Osi) developed by the COIN-OR (COmputational INfrastructure for Operations Research) project which means that every solver supported by OSI can be used to solve the relaxations.

Moreover, ABACUS provides a variety of general algorithmic concepts, e.g., a list of different enumeration and branching strategies from which the best alternative for the user's application can be chosen.

Finally, ABACUS provides many basic data structures and useful tools for the implementation of such algorithms. It is designed both for general mixed integer optimization problems and for combinatorial optimization problems. It unifies cutting plane and column generation within one algorithm framework. Simple reuse of code and the design of abstract data structures and algorithms are met by object oriented programming modules.

Michael Jünger's group at the University of Cologne.

PACKAGE: PENNON
From:    Michal Kocvara
Date:    Mon Dec 17,  5:02am -0700

A research paper describing the code PENNON for semidefinite
programming by Michal Kocvara and Michael Stingl is now available


http://www2.am.uni-erlangen.de/~kocvara/pennon/

Abstract:
---------
and Zibulevsky to convex semidefinite programming problems. The
algorithm used is a generalized version of the Augmented Lagrangian
method. We present details of this algorithm as implemented in a new
code PENNON. The code can also solve second-order conic programming
(SOCP) problems, as well as problems with a mixture of SDP, SOCP and
NLP constraints. Results of extensive numerical tests and comparison
with other SDP codes are presented.

Michal Kocvara                     e-mail: kocvara@am.uni-erlangen.de
Institute of Applied Mathematics   http://www2.am.uni-erlangen.de/~kocvara
University of Erlangen/Nuremberg   tel: +49-9131-8527860 (8527509)
Martensstr. 3                      fax: +49-9131-8528126
D-91058 Erlangen
Germany

PACKAGE: WSMP
From: Anshul Gupta
Date: Thu, 1 Nov 2001 11:48:24 -0500
Subject: Linear Programming in Watson Sparse Matrix Package

The Watson Sparse Matrix Package (WSMP) is a high-performance robust
direct solver for both symmetric and unsymmetric large sparse systems
of linear equations.  Currently, it works in serial, multi-threaded
parallel, message-passing parallel, and a combination of message-passing
and multi-threaded modes on AIX.  A Linux version is expected next year.

The symmetric solver has features to support barrier methods for solving
LP problems.  For instance, it provides users a variety of options to
deal with small and negative pivots and the loss of rank.

We have recently added support in the unsymmetric solver that enables
it to be used in conjunction with the Simplex algorithm and other LP
techniques.  This includes routines to factor a basis, update rows or
columns of a previously factored basis, obtain solutions with respect
to the latest updated basis and to obtain and refactor the current basis.


http://www.cs.umn.edu/~agupta/wsmp.html

and send an e-mail to anshul@watson.ibm.com with "LINUX WSMP" in the
subject line if you wish to be notified when the Linux version becomes
available.




PACKAGE: MCF
Subject: Announcement: Network simplex solver MCF-1.1

Sender:  loebel

Primary:   90CXX
Secondary: 68RXX

Category:  Software

Dear colleagues,

I am pleased to announce an updated version of MCF, an implementation in C of
the network simplex algorithm. This program package provides the primal and the
dual approach, which can be used in a stand-alone program expecting input files
in DIMACS format or as subroutines within your own programs.

A doc++-documentation in PS, PDF, or DVI format can be downloaded from

http://www.zib.de/Optimization/Software/Mcf.

MCF has so far been supported for Unix/Linux environments. Now, we also offer a
version for Windows 95/98/NT (created in a Microsoft Visual C++ 5.0 environment).

The updated version of MCF includes some minor bug fixes:

* MCF is now stable for 64-bit architectures.
* The objective value is now be computed correctly by mcflight.
* Fixed arc values are handled correctly.

MCF 1.1 is available for academic use free of charge via WWW at URL


http://www.zib.de/Optimization/Software/Mcf

I welcome and appreciate any feedback of MCF users! Please mail it to
loebel@zib.de.

Best regards,

Andreas Loebel


Previous version of MCF


PACKAGE: DSDP
Announcing new software package DSDP for solving positive
semidefinite programs.

DSDP implements a dual scaling algorithm for mixed linear and positive
semidefinite programming problems with rank-one matrix constraints.
It reads the input data from a MPS-like format. By
exploiting much of the structure and sparsity of many large scale
problems, the SDP relaxation of combinatorial optimization problems
in particular, DSDP can achieve considerable saving in time and
memory over other interior-point methods. The program still generates
both primal and dual feasible solutions, and it terminates at a provable
optimality tolerance.

DSDP also includes randomized rank reduction methods for the maximum
cut, graph-partition, maximum cover, and box constrained quadratic
problems.

The source code is written in ANSI C and, with User-Guide
from the COPL website at:

http://dollar.biz.uiowa.edu/col/


Steven Benson :  benson@mcs.anl.gov
Yinyu Ye      :  yinyu-ye@uiowa.edu

PACKAGE: SDPT3
From: Toh Kim Chuan

SDPT3 - a MATLAB software package for

R.H. Tutuncu, K.C. Toh, and M.J. Todd

Technical Report,
Department of Mathematics,
National University of Singapore,
2 Science Drive 2, Singapore 117543
August 2001

This software package is a MATLAB implementation of infeasible path-following algorithms for
solving conic programming problems whose constraint cone is a product of semidefinite cones,
second-order cones, and/or nonnegative orthants. It employs a predictor-corrector primal-dual
path-following method, with either the HKM or the NT search direction. The basic code is written
in Matlab, but key subroutines in Fortran and C are incorporated via Mex files. Routines are
provided to read in problems in either SeDuMi or SDPA format. Sparsity and block diagonal
structure are exploited, but the latter needs to be given explicitly.

URL of the dvi file: http://www.math.cmu.edu/~reha/SDPT3/guide3.0.ps.gz
URL of the ps file: http://www.math.nus.edu.sg/~mattohkc/papers/guide30.ps.Z

Older announcement:
===================
Title: SDPT3 --- a Matlab software package for
semidefinite programming.

AUTHOR: K.C. Toh, M.J. Todd, and R.H. Tutuncu

Citation details: Manuscript.

Abstract:
This software package is a Matlab implementation of
infeasible path-following algorithms for solving standard
semidefinite programs. The Mehrotra-type predictor-corrector
variants are included. Three types of search directions are
available, namely, the AHO, H..K..M, and NT directions.
A few classes of SDP problems are also included.
Numerical results for these classes show that our algorithms
are fairly efficient and robust on problems with dimensions
of the order of a hundred.

URL of postscript file and software:


http://www.math.nus.sg/~mattohkc/index.html

Sep 28, 1999: Announced version 2.1:
http://www.math.nus.edu.sg/~mattohkc/SDPT3-2.1.tar.Z
and a user's guide is at
http://www.math.nus.edu.sg/~mattohkc/papers/guide.ps.Z

Email: mattohkc@math.nus.sg

Dec 17, 1998:
Dear Colleagues:

This is to announce a new release of SDPT3, our Matlab
software package for semidefinite programming. Version 1.3
is now available from

http://www.math.nus.edu.sg/~mattohkc/SDPT3-1.3.tar.Z

and a user's guide is at

http://www.math.nus.edu.sg/~mattohkc/papers/guide.ps.Z

The main changes are in allowing linearly dependent matrices A_k,
with an added preprocessing step to remove redundant constraints;
improving the linear algebra; setting up the matrices A_k as
sparse when converting from SDPA format; and reclaiming storage
where possible.

again.

Please let us know of any problems you encounter using this software.

-- Kim Chuan Toh

Department of Mathematics, National University of
Singapore, 10 Kent Ridge Crescent, Singapore 119260.
mattohkc@math.nus.edu.sg

Mike Todd

School of Operations Research, Cornell University,
Ithaca, NY 14853-3801
miketodd@cs.cornell.edu

Reha Tutuncu

Department of Mathematical Sciences, Carnegie Mellon University,
Pittsburgh, PA 15213
reha+@andrew.cmu.edu

PACKAGE: RELAX4:

v94w50n6

Subject: tseng: New Code for Minimum Cost Flow Problems
Sender:  on.ptseng

Primary:   49-xx
Secondary: 90-xx

Category:  Software

***********************************************************************
*                                                                     *
*   RELAX-IV, a faster version of the RELAX code, is now available.   *
*                                                                     *
***********************************************************************

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.

To obtain RELAX-IV by anonymous FTP, ftp to LIDS.MIT.EDU with
cd /pub/bertsekas/RELAX
to go to the RELAX subdirectory, which in addition to the RELAX-IV code
contains documentation and random problem generation and conversion
codes.

Dimitri Bertsekas       (617) 253-7267,  dimitrib@mit.edu

Paul Tseng              (206) 543-1177,  tseng@math.washington.edu

PACKAGE: CHACO:

From: Bruce Hendrickson
DATE: Fri, 8 Sep 95 12:53:54 MDT
Subject: Chaco-2.0: Graph Partitioning Software

ANNOUNCING CHACO-2.0
Software for Partitioning and Ordering Graphs

Many problems which arise in the course of scientific computing can be
conveniently described in terms of graph partitioning.  A prominent
example is the problem of decomposing a large, unstructured grid across
the processors of a parallel computer.  Other applications include generating
nested disection orderings for sparse matrix factorizations and devising
efficient circuit layouts.

Version 1 of our graph partitioning code "Chaco" has been licensed to over
100 sites around the world.  We are now releasing version 2.0 with greatly
enhanced performance, ease of use and functionality.  Chaco contains a
variety of partitioning algorithms including spectral bisection, quadrisection
and octasection, the inertial method, the Kernighan-Lin/Fiduccia-Mattheyses
algorithm and multilevel partitioners.  Advanced techniques that are new to
version 2.0 include terminal propagation (a method for improving data locality
adapted from the circuit community), the ability to map partitions
Fiedler vector to assist the development of new applications of spectral
graph algorithms.  This capability has already been used in applications
ranging from gene sequencing to database design.

A user's guide and papers describing the algorithms are available by
anonymous ftp to cs.sandia.gov in the directory pub/tech_reports/bahendr.
Academic user's can obtain the code at no charge under a research license
agreement and it may also be licensed for commercial application. Interested
parties should contact the first author at the address given below.

Bruce Hendrickson (bah@cs.sandia.gov)
Rob Leland (leland@cs.sandia.gov)
Sandia National Laboratories
Albuquerque, NM 87185

PACKAGE: PPRN

From: Jordi Castro Perez
DATE: Tue, 10 Oct 1995 17:52:11 UTC+0100
Subject: New Network Optimization Package Available

Dear colleagues,

This is to inform you that there is available a new package, called
PPRN, for network optimization. The package is appropriate for solving a high
variety of network problems: single/multicommodity network flow problems,
with linear/nonlinear objective function and with/without linear side
constraints. Thus it can be viewed as a general package for many network
optimization problems (though it was originally designed for solving
nonlinear multicommodity problems with linear side constraints).

The code has been tested comparing its performance against other
codes. When solving pure linear network flow problems, it has proved to be
faster than alternative codes like NETFLO (J. Kennington) or RELAX-IV
(D. Bertsekas) in all cases tried of a battery of dimacs problems. When
solving linear multicommodity problems its performance was in general
better, though not in all cases tested, than that of MCNF85 (J. Kennington).
For nonlinear problems it has only been compared with general purpose packages
like MINOS (Murtagh and Saunders) and PPRN always outperformed it.

The package can work as an stand-alone code (reading the model
from a file and reporting the solution in another file) or as a subroutine
in a bigger user application (the communication with the user application
is made through parameters in this case). It can be called from Fortran and
C user applications.

The package is presented as a library and can be obtained via
anonymous ftp from ftp-eio.upc.es (if this doesn't work, try to connect to
gandalf.upc.es), at directory pub/onl/codes/pprn. The package is available
from Sun and DEC-Alpha platforms. If you have a different architecture from
information like some technical reports and papers describing
the package, an user's guide, some test examples, and a converter from dimacs
format to pprn format (this only for the case of linear single commodity
problems).

Should you have any comments or suggestions, you find trouble or
abnormal situations, or you have a different platform from those available,

This code has been released for academic use only. For other types

Jordi Castro                                    Narcis Nabona

Statistics and Operations Research Dept.
Universitat Politecnica de Catalunya
Campus Sud, Edifici U
c. Pau Gargallo 5
08071 Barcelona, Spain

e-mail: jcastrop@eio.upc.es                     e-mail: nabona@eio.upc.es

PACKAGE: SDP by Boyd et al

A beta version of SDP (semi-definnite
prorgram) is available at ftp site boyd@isl.stanford.edu. This
program was developed by Prof. Stephen Boyd et al, and uses
interior point methods. The source code is available, as is
executables which run on SUN and other workstations. If you have
the LAPACK library  ported to a PC environment, you can run the
program on a PC. It has the C code necessary to run as a call
from MATLAB.

PACKAGE DONLP2

From: Peter Spellucci
DATE: Tue, 28 Nov 1995 18:20:45 +0100
Subject: New SQP Optimization Software Available

To anyone concerned with continuous optimization:

I just have completed work on a new implementation of a SQP-method,
which forms the successor of my code "donlp" in netlib/opt. The new
version, being capable of solving problems with a much higher number
of constraints is immediately available for everyone from netlib in
the directory netlib/opt/donlp2.

Have fun in using it (hopefully).

Opt-Net digest: v98w38n1

Subject: New AD version of DONLP2

Sender:  beck@plato.la.asu.edu

Primary:   90C30
Secondary: 90CXX

Category:  Software

A new AD version of Peter Spellucci's NLP package DONLP2 has been
released. It uses the TAMC utility of Ralf Giering.


ftp://plato.la.asu.edu/pub/donlp2/donlp2_td.tar.gz http://plato.la.asu.edu/donlp2.html


- convenient interactive automatic differentiation with included
small script; no implementation of TAMC necessary
- general f77 standard with very few exceptions, no rewriting
of function statements required, no control statements

An online version of DONLP2 can also be accessed via the NEOS Server at
Argonne National Laboratory.
http://www.neos-server.org/neos/
It is intended for testing purposes and accepts input in AMPL. It uses
AMPL's automatic differentiation feature.

PACKAGE: GULF
Dear Colleague,

of GULF from the following WWW page:


http://neumann.math.klte.hu/~erik/tr93-86.html

GULF is a simple to use but powerful, menu driven LINEAR-FRACTIONAL
programming (LFP) and LINEAR programming (LP) package for IBM compatible
MS-DOS microcomputers with minimum of 640K RAM and one floppy disk drive.
The program is capable of handling up to 150 main constraints and 200 nonnegative
variables (in the case of demo-version you have just up to 25 main constraints
and up to 25 variables).

Data can be entered in a spreadsheet styled editor within GULF or from an MPS
format text file. A spreadsheet styled data editor is built into the program.

There is no minimum disk size required as GULF takes up only about 200K of
disk space.  GULF is not copy protected.

INFORMATION ABOUT   G U L F
==============================================================================
You can find more detailed information about GULF in our Technical Report :
1. Erik B. Bajalinov, David J.Pannel :
"GULF : a General User-friendly Linear and linear-Fractional programming
package", Technical Report No.93/86, Institute of Mathematics,
Lajos Kossuth University, 1993, Hungary
You can find this TR and download it in PostScript formatum from WWW page:


http://neumann.math.klte.hu/~erik/tr93-86.html

For more independent information on GULF see :
2. Herve Thiriez, "GULF (version 2.2)", in European Journal of Operational
Research, Vol. 67 (1993), pp.295-296. North-Holland.

FREE DEMO or FULL VERSION (US$250) of GULF by mail. Sincerely Yours, Dr.Erik B.Bajalinov ============================== Institute of Mathematics Lajos Kossuth University H-4010 Debrecen, Pf.12, HUNGARY e-mail : erik@math.klte.hu Phone : (36-52) 316-666/2821 (English,Russian,Hungarian) Fax : (36-52) 416-857 (36-52) 343-746 PACKAGE: PCx We are pleased to announce a new release of PCx, our interior-point code for linear programming. Features of this release include a version for Windows 95/NT and improved algorithmic features such as higher-order corrections, dense column handling, and scaling. The Windows version can be obtained from the following URL:  http://www.mcs.anl.gov/otc/Tools/PCx/Windows/  The source code for the Unix version, together with executables for various architectures, can be obtained from  http://www.mcs.anl.gov/otc/Tools/PCx/  PCx can also be executed remotely through the NEOS Server. For details, see http://www.mcs.anl.gov/otc/Server/ http://www.mcs.anl.gov/otc/Server/neos/software-library/LP:PCX/ Joe Czyzyk, Steve Wright Optimization Technology Center PACKAGE: MCF, a network simplex implementation Subject: Loebel: Announcement of MCF, a network simplex implementation Sender: on.loebel Primary: 90CXX Secondary: 68RXX Category: Software Dear colleagues, I am pleased to announce MCF, an implementation in C of the network simplex algorithm. This program package provides the primal and the dual approach, which can be used in a stand-alone program expecting input files to be in DIMACS format or as subroutines within your own programs. MCF has been compiled with several compilers, e.g., gcc (version 2.7.2) and SUN-CC (version 4.0), for SunOS and Solaris on SUN workstations, for HP-UX on HP workstations, and for Linux. Moreover, it has been installed on IBM, Sony, and CRAY computers. MCF has been made quite robust using PURE ATRIA's Purify, a run-time error detector for a range of memory-related software errors, for moreinformation see http://www.pureatria.com. Besides solving many academic minimum-cost flow test instances, the code has upto now been used to solve real-world problems from vehicle scheduling in publicmass transit and frequency assignment in telecommunication. Combined with a delayed column generation, it is possible to solve truly large-scale problems with up to 50 thousand nodes and 70 million arcs in a few minutes to optimality. For more information on these projects, see our web server at http://www.zib.de/Optimization. The subroutines of the MCF library are currently employed for vehicle scheduling at the Berliner Verkehrsbetriebe, which is the worlds fourth largest public transportation company providing public transportation in Berlin, and is used for frequency assignment at E-plus Mobilfunk GmbH, which is a German mobile phone service provider. MCF is available for academic use free of charge via WWW at URL  http://www.zib.de/Optimization/Software/Mcf.  It is also possible to separately retrieve a postscript version of its documentation, which describes MCF's data structure and interface. I welcome and appreciate any feedback of MCF users! Please mail it to loebel@zib.de. Best regards, Andreas Loebel PACKAGE: ADMIT Automatic Differentiation MATLAB Interface Toolbox Thomas F. Coleman and Arun Verma Center for Applied Mathematics and Computer Science Department Cornell University coleman@cs.cornell.edu verma@cs.cornell.edu Abstract ________ ADMIT-1 enables you to compute *sparse* Jacobian and Hessian matrices, using automatic differentiation technology, from a MATLAB environment. You need only supply a function to be differentiated and ADMIT-1 will exploit sparsity if present to yield sparse derivative matrices (in sparse MATLAB form). Currently, ADMIT-1 requires that the target function you supply (to be automatically differentiated) be written in C/C++. ADMIT-1 also allows for the calculation of gradients and has several other related functions. ADMIT-1 is built on top of the automatic differentiation engine ADOL-C due to Griewank and Utke (http://www.math.tu-dresden.de/wir/project/wwwadolc/wwwadolc.html). For more information on the ADMIT project, see  http://www.cs.cornell.edu/Info/People/verma/AD/research.html  PACKAGE: SDPpack Dear Colleagues, We would like to announce a new version of our code SDPpack (Version 0.9 Beta for Matlab 5.0). This version extends the previous release for semidefinite programming (SDP) to mixed semidefinite-quadratic-linear programs (SQLP), i.e. linear optimization problems over a product of semidefinite cones, quadratic cones and the nonnegative orthant. The code and documentation is available at the URL:  http://cs.nyu.edu/cs/faculty/overton/sdppack/sdppack.html  Farid Alizadeh (Rutgers) Jean-Pierre A. Haeberly (Fordham) Madhu V. Nayakkankuppam (NYU) Michael L. Overton (NYU) Stefan Schmieta (Rutgers) PACKAGE: METIS From: George Karypis DATE: Sun, 20 Sep 1998 15:21:51 -0500 (CDT) Subject: Software for Graphs, Meshes and Sparse Matrices METIS A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices  http://www.cs.umn.edu/~metis http://www.cs.umn.edu/~karypis/metis  Version 4.0 We would like to announce the release of version 4.0 of the METIS package for partitioning unstructured graphs, partitioning finite element meshes, and for computing fill-reducing orderings of sparse matrices. METIS 4.0 contains a number of changes over METIS 3.0. The major changes are the following: * METIS now includes partitioning routines that can be used to partition a graph in the presence of multiple balancing constraints. * METIS now includes partitioning routines that can be used to directly minimize the overall communication volume resulted by the partitioning. * METIS's k-way partitioning routines can now directly minimize the maximum as well as the total number of adjacent subdomains. * METIS's k-way partitioning routines can now reduce the number of non-contiguous subdomains. Overview of METIS METIS is a set of programs that implement various graph partitioning algorithms that are based on the multilevel paradigm. The advantages of METIS compared to other similar packages are the following: - Provides high quality partitions! - It is extremely fast! - Provides low fill orderings! Obtaining METIS METIS is freely distributed. You can download METIS's source code from the WEB at: URL: http://www.cs.umn.edu/~metis or URL: http://www.cs.umn.edu/~karypis/metis Contact Information METIS has been written by George Karypis at the Computer Science Department of the University of Minnesota. If you have any questions or problems obtaining METIS, send email to metis@cs.umn.edu. METIS is Copyrighted by the Regents of the University of Minnesota PACKAGE: ParMETIS From: George Karypis DATE: Fri, 18 Jul 1997 12:48:26 -0500 (CDT) Subject: A Parallel Graph Partitioning and Sparse Matrix Ordering Library ParMETIS: A Parallel Graph Partitioning and Sparse Matrix Ordering Library We would like to announce the release of version 1.0 of the ParMETIS library. ParMETIS is an MPI-based parallel library that implements a variety of algorithms for partitioning unstructured graphs and for computing fill-reducing orderings for sparse matrices. ParMETIS is particularly suited for parallel numerical simulations involving large unstructured meshes. For these computations, ParMETIS dramatically reduces the time spent in communication by decomposing the mesh in a way that balances the load and minimizes the number of interface elements. ParMETIS's algorithms are based on the multilevel partitioning and fill reducing ordering algorithms that are implemented in the widely used serial package METIS. ParMETIS extends the functionality provided by METIS by including routines that are especially suited for parallel computations and large scale numerical simulations. ParMETIS provides the following four major functions: - Partition an unstructured graph. - Improve the quality of an existing partition. - Repartition a graph that corresponds to an adaptively refined mesh. - Compute a fill-reducing ordering for sparse direct factorization. Here is a list of some of the main features of ParMETIS: - It quickly computes high quality partitions of very large unstructured graphs. - It can take advantage of geometry information (when available) to speedup the runtime of the partitioning algorithms without loss in quality. - It can be used to improve (some times dramatically) the quality of partitions produced by other partitioning algorithms. - It can quickly compute high quality repartitions of adaptively refined meshes. It optimizes both the number of vertices that are moved as well as the edge-cut of the resulting partition. - It can compute fill reducing orderings for sparse direct factorization. It uses a node-based nested dissection algorithm that has been shown to significantly outperform other popular ordering algorithms. Obtaining ParMETIS ParMETIS is distributed freely. Information on how to download the source code is available on WWW at: URL: http://www.cs.umn.edu/~karypis/metis ParMETIS has been written by George Karypis, at the Computer Science Department of the University of Minnesota. If you have any questions or problems obtaining ParMETIS, send email to karypis@cs.umn.edu. PACKAGE: PSPASES and WSSMP DATE: Mon, 12 Jan 1998 12:02:48 -0600 (CST) From: Mahesh Joshi To: interior-point-methods@mcs.anl.gov Subject: Announcing PSPASES and WSSMP libraries. PSPASES : A Scalable Parallel Direct Solver for ----------------------------------------------- Sparse Symmetric Positive Definite Systems ------------------------------------------ Mahesh Joshi, George Karypis, Vipin Kumar Department of Computer Science, University of Minnesota, Mineapolis, MN. Anshul Gupta IBM Thomas J. Watson Research Center, Yorktown Heights, NY. We are glad to announce a beta release of PSPASES, a stand-alone MPI-based parallel library for solving linear systems of equations involving sparse symmetric positive definite matrices. The library efficiently implements the scalable parallel algorithms developed by authors, for each of the four phases of direct solution method; viz. ordering, symbolic factorization, numerical Cholesky factorization, and solution of triangular systems. PSPASES is highly scalable, mainly because it uses a highly scalable parallel multifrontal algorithm in the most expensive computational phase of numerical factorization. All the other phases are also scalable by themselves. In our testing, PSPASES solved a system of around 1 million equations in just 62 seconds on 64 processors and in 38 seconds on 128 processors of Cray T3E. This time included times required for all the four phases of the solver. The highest performance clocked by PSPASES is 21.2 GFLOPS for the numerical factorization phase. This efficient and scalable behavior is demonstrated while solving most of the systems appearing in practice. PSPASES is implemented using standard MPI and BLAS, which makes it portable to most of today's parallel computers and networks of workstations. We have tested PSPASES extensively on IBM SP, network of IBM RS6000 workstations, Cray T3E, SGI Origin 2000 and PowerChallenge architectures. PSPASES uses ParMETIS and METIS as default libraries for computing fill- reducing ordering, but it also accepts user supplied ordering. Different functional interfaces are provided for each of the phases of the solver and a simple interface is also provided for easy use. The user can use these interfaces to solve multiple systems with same nonzero structures; to solve same system for multiple right hand sides; and to get different statistical information such as the memory requirements of the solver and the quality of the ordering. Visit the PSPASES web site at  http://www.cs.umn.edu/~mjoshi/pspases  to obtain the software, the manual, and related technical papers. The software can directly be obtained via an anonymous ftp to "ftp.cs.umn.edu". Get the files "pspases-beta..tar.gz" and "README.PSPASES" located in the directory "users/kumar/mahesh". Any comments, questions or bugs regarding PSPASES can be directed to Mahesh Joshi (mjoshi@cs.umn.edu). WSSMP: Watson Symmetric Sparse Matrix Package --------------------------------------------- Anshul Gupta IBM Thomas J. Watson Research Center, Yorktown Heights, NY. Mahesh Joshi and Vipin Kumar Department of Computer Science, University of Minnesota, Mineapolis, MN. A faster version of the solver with enhanced functionality is available for IBM SP and RS6000 systems, as WSSMP. The WSSMP package contains robust industrial strength code for serial and parallel solution of sparse symmetric positive definite and indefinite systems. WSSMP has been clocked at up to 450 MFLOPS on an RS6000/397 workstation and up to 24 GFLOPS on a 64-processor SP with model-397 nodes. Documentation for WSSMP is available at ftp://ftp.cs.umn.edu/users/kumar/anshul/WSSMP-manual.ps. Any questions pertaining to WSSMP may be directed to Anshul Gupta (anshul@watson.ibm.com). PACKAGE: SeDuMi From: Imre Polik, poliki@MCMASTER.CA Date: December 2, 2004.  We are glad to announce that the Advanced Optimization Laboratory at McMaster University, Canada takes over the maintenance and development of the SeDuMi package originally created by Jos F. Sturm, who passed away in October, 2003. The new SeDuMi website is at http://sedumi.mcmaster.ca, it currently contains a Downloads section with the latest SeDuMi releases, documentation, testsets and related papers, FAQ and a user forum. Users can provide feedback and share their opinion and success stories about the software, request new features, report bugs, etc. at the forum. Currently, SeDuMi works in Matlab environment on Windows and Unix/Linux systems. Experimental Mac builds and instructions on how to compile SeDuMi under Mac OS X are under development. Updates for Matlab 7 are going to be released in the near future. The maintainers also plan to provide Windows builds optimized for Pentium IV and Athlon processors. New features are planned to be added based on user requests and recent publications. We hope to see you at the website, Tamas Terlaky, Imre Polik Oleksandr Romanko Previous announcement, by Jos: Wed, Oct 31, 2001 Dear SIAG/OPT fellow members, 1) It is my pleasure to announce a new version of SeDuMi, viz. 1.05, which is available at:  http://fewcal.kub.nl/sturm/software/sedumi.html  (a free solver for linear cone optimization/ LP/LMI/SDP/SOCP, implementing interior point techniques. Author: myself), 2) and an NEW free modeling interface (in MATLAB), which allows you to declare, add, remove and freeze constraints, variables, etc.; it is called SeDuMi Interface 1.01 (by Peaucelle, Henrion and Labit), and is available from:  http://www.laas.fr/~peaucell/SeDuMiInt.html 3) I want to ask excellent students to apply for an excellent PhD project, info at:  http://fewcal.kub.nl/sturm/aioRecruit.html Best Regards, Jos. dr Jos F. Sturm |ph +31 13 466 2031 Dept. Econometrics & OR |fx +31 13 466 3280 Tilburg University |j.f.sturm@kub.nl PO Box 90153 |fewcal.kub.nl/sturm NL-5000 LE Tilburg, Netherlands. PACKAGE: SeDuMi (older version) AUTHOR: Jos Sturm DATE: Oct 1, 1999. Dear fellow members of SIAG/OPT, Please be adviced that a new version of SeDuMi (optimization with linear, quadratic/SOC and hermitian semi-definite/PSD constraints) is freely downloadable (incl full ansi C source and documentation) at  http://www.unimaas.nl/~sturm/software/sedumi.html One of the improvements is the use of a product-form Cholesky to handle dense columns, as proposed recently by Goldfarb and Scheinberg. Enjoy, Jos. Dr Jos F. Sturm Phone +31 43 388 3761 Dept Quantitative Economics Fax +31 43 388 4874 Maastricht University j.sturm@ke.unimaas.nl P.O. Box 616 www.unimaas.nl/~sturm NL-6200 MD The Netherlands Original announcement: DATE: April 17, 1998. Dear colleagues, I am happy to announce the first public release of SeDuMi, a Matlab 5 Toolbox for solving optimization problems over self-dual homogeneous cones. As such, it allows for linear, quasiconvex quadratic and positive semi-definiteness constraints, both with real and complex entries. This is currently the only available code that can handle all these constraint types. It has been designed with the user in mind. Engineers at the Communications Research Lab have already been working with this code. In our experience, SeDuMi is more reliable and also faster than the now popular codes SP (from Stanford) and SDPPACK (from NYU). For instance, truss5, an SDP problem available from the SDPPACK homepage, solves on my computer (Pentium, Linux) in 733 sec. with SP, 86 sec. with SDPPACK and 12 seconds with SeDuMi. Also, ladder1, a SOCP problem from the same collection, takes 17 sec. with SDPPACK and 1.4 second with SeDuMi. The largest problem in this set, truss8, doesn't solve with SP, but takes 905 sec. with SDPPACK and 85.3 sec. with SeDuMi. Results on the NETLIB test set show that it is also competitive for LP-only problems. This finally closes the gap between theory and practice for IPMs, since SeDuMi exactly implements the$O(\sqrt(n) \log \epsilon)\$ algorithm
that I proposed in Chapter 7 of my PhD thesis, which is also freely
available from my homepage.

For the experts: SeDuMi uses a Ye-Todd-Mizuno type self-dual embedding,
the Sturm/Zhang v-space direction with Nesterov-Todd scaling,
the Sturm/Zhang wide region framework, and my centering-predictor-corrector
algorithm, that has a Mehrotra-type centrality correction.
It agressively exploits sparsity at any thinkable place, and beyond.

The installation procedure works well on a Linux system (my own experience),
and hopefully works on any UNIX system.  If anybody knows whether and how the
package can be installed on Windows and Mac workstations, please let me know.

SeDuMi is available from:

http://www.crl.mcmaster.ca/ASPC/people/sturm/software/sedumi.html

Sincerely yours,

Jos F. Sturm.

==========> L e t   Se Du Mi  s e d u c e   y o u   t o o  <==========

Jos F. Sturm                 | Phone +1 905 525 9140 ext 27141
Communications Research Lab. | Fax   +1 905 521 2922
McMaster University          | E-mail sturm@cauchy.crl.mcmaster.ca
1280 Main Street West        | http://www.crl.mcmaster.ca/ASPC/people/sturm
HAMILTON, ONTARIO L8S 4K1    | Room 223.

=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o
Interior-Point Methods Online : http://www.mcs.anl.gov/otc/InteriorPoint

PACKAGE:   CUTSDP

DATE:  7 May, 1998.

I am pleased to announce that Version 1.0 of "CUTSDP - A Toolbox for a
Cutting-Plane Approach Based on Semidefinite Programming" is now available


http://www.imm.dtu.dk/~sk/cutsdp/

The user manual can be obtained via:

http://www.imm.dtu.dk/~sk/cutsdp/cutsdp.ps

CUTSDP is a package of C programs containing an implementation of a
cutting plane approach based on semidefinite programming. The current
version includes also the implementation of three applications: max-cut,
graph bisection, and graph equipartition.

Comments, remarks and suggestions for future versions are very welcome.

Best regards,

Stefan Karisch

PACKAGE: PSPASES
DATE: Mon, 25 May 1998 21:28:06 -0500 (CDT)
From: Mahesh Joshi
Subject: Announcing PSPASES 1.0 and WSSMP 3.7
Sender: owner-interior-point-methods@mcs.anl.gov
To: interior-point-methods@mcs.anl.gov

==========================================================================
*****  Announcing PSPASES 1.0 and WSSMP 3.7
==========================================================================

"PSPASES : A Scalable Parallel Direct Solver Library for Sparse Symmetric
Positive Definite Systems"


http://www.cs.umn.edu/~mjoshi/pspases

by Mahesh Joshi, George Karypis, Vipin Kumar
Department of Computer Science, University of Minnesota, Mineapolis.
&
Anshul Gupta
IBM Thomas J. Watson Research Center, Yorktown Heights, New York.
________________________________________________________________________

We are glad to announce a new version (1.0) of PSPASES.

--- PSPASES Features

*  High Performance Library: Entire solution process for a 1 million
equation system (with 900 million nonzeros in factor L), took
just 4 minutes on Cray T3E. Numerical factorization, which is
computationally the most expensive phase, clocked a 53 GFLOPS
performance!

*  Portable to most of today's parallel computers. Tested on IBM, Cray,
and SGI platforms.

*  Entirely parallel and scalable code. Each of the four phases is
parallelized.

*  Library functions can be called from both C and Fortran 90 codes,
with simple calling sequences.

*  All memory allocations done internally. Memory requirements for the
numerical factorization phase can be pre-estimated.

*  Concept of a communicator is used to enable solving multiple systems
with same sparsity structure, or same system for multiple sets of B.

*  Command line interface provided, which supports four different matrix
formats, including the Harwell-Boeing format.

--- Changes in version 1.0 from version 0.0beta.

1. Fixed problems related to boundary cases, such as relatively small size
of matrices for given number of processors, and diagonal matrices.
Changes were made to PSPASES and Metis code, and the driver codes.

2. Added support for four different formats (.fcc, .bin, .rsa HB, .rsa RB).
Drivers are provided for all these formats in TEST directory.
Note: The previous spd format is now renamed fcc format.

4. Simpler testing interface is now available via improved Makefile and a
"testrun" script in TEST directory.

5. Created matrices directory which has representative matrices in four
formats.

6. Metis code is now version 3.0.6 code with some more fixes in ometispar.c
and sfm.c.

--- PSPASES Abstract

PSPASES is a stand-alone MPI-based parallel library for solving linear
systems of equations involving sparse symmetric positive definite matrices.
The library efficiently implements the scalable parallel algorithms
developed by authors, for each of the four phases of direct solution
method; viz. ordering, symbolic factorization, numerical Cholesky
factorization, and solution of triangular systems.

PSPASES is implemented using standard MPI and BLAS calls, which makes it
portable to most of today's parallel computers and networks of
workstations. We have tested PSPASES extensively on IBM SP, network of
IBM RS6000 workstations, Cray T3E, SGI Origin 2000 and PowerChallenge
architectures.

PSPASES uses ParMETIS and METIS as default libraries for computing fill-
reducing ordering, but it also accepts user supplied ordering. Different
functional interfaces are provided for each of the phases of the solver
and a simple interface is also provided for easy use. The user can use
these interfaces to solve multiple systems with same nonzero structures;
to solve same system for multiple right hand sides; and to get different
statistical information such as the memory requirements of the solver
and the quality of the ordering.

Visit the PSPASES web site at

http://www.cs.umn.edu/~mjoshi/pspases

to obtain the software, the manual, related technical papers, usage notes,
using the PSPASES software.

software via an anonymous ftp to "ftp.cs.umn.edu". Change the directory to
users/kumar/mahesh and get the files pspases-1.0.tar.gz, README.INSTALL,
and README.USAGE (remember to use binary transfer mode).

Any comments, questions or bugs regarding PSPASES can be directed to
Mahesh Joshi (mjoshi@cs.umn.edu).


Previous version

==========================================================================

"WSSMP: Watson Symmetric Sparse Matrix Package"

by Anshul Gupta
IBM Thomas J. Watson Research Center, Yorktown Heights, New York.
&
Mahesh Joshi and Vipin Kumar
Department of Computer Science, University of Minnesota, Mineapolis, MN).
________________________________________________________________________

We are pleased to announce a new version (3.7) of WSSMP.

The enhancements to WSSMP Version 3.7 include run time detection of the
amount of physical memory available to automatically choose some of the
algorithms most suitable for the problem-hardware combination, and an
overall reduction in the memory requirements, especially the serial
version.

--- WSSMP Abstract :

A faster version of the solver with enhanced functionality is available
for IBM SP and RS6000 systems, as WSSMP.  The WSSMP package contains
robust industrial strength code for serial and parallel solution of
sparse symmetric positive definite and indefinite systems.  WSSMP has
been clocked at up to 450 MFLOPS on an RS6000/397 workstation and up to
24 GFLOPS on a 64-processor SP with model-397 nodes.  Documentation for
WSSMP is available at
ftp://ftp.cs.umn.edu/users/kumar/anshul/WSSMP-manual.ps.

Please read the terms and conditions of use, given in the manual, before
using the WSSMP software.

Any questions pertaining to WSSMP may be directed to Anshul Gupta
(anshul@watson.ibm.com).


Previous version

==========================================================================

=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o
Interior-Point Methods Online : http://www.mcs.anl.gov/otc/InteriorPoint

PACKAGE: MINOPT

From: Minopt Software Support
DATE: Sat, 25 Jul 1998 15:00:55 -0400 (EDT)
Subject: Announcement of New Software: MINOPT

MINOPT
A Modeling Language and Algorithmic Framework for Linear,
Mixed-Integer, Nonlinear, Dynamic, and Mixed-Integer
Nonlinear Optimization

C. A. Schweiger and C. A. Floudas
Department of Chemical Engineering
Princeton University
Princeton, NJ 08544-5263


http://titan.princeton.edu/MINOPT/

MINOPT is a comprehensive, powerful, and flexible package for the
solution of various types of optimization problems.  It features both
an ADVANCED MODELING LANGUAGE for the clear and concise representation
of complex mathematical models as well as a ROBUST ALGORITHMIC
FRAMEWORK for the efficient solution of wide variety of mathematical
programming problems.

MINOPT is a flexible tool which can be used in a broad range of
applications:
o Process Systems Engineering
- Process Design
- Process Synthesis
- Process Control
- Process Dynamics
o Optimal Control
o Parameter Estimation
o System Identification
o Process Operations and Operations Research
- Supply chain management
- Scheduling
- Planning
- Portfolio Optimization
- Location/Allocation

MINOPT is capable of handling a wide variety of model types:
o Linear Programs (LP)
o Mixed Integer Linear Programs (MILP)
o NonLinear Programs (NLP)
o NLPs with Differential and Algebraic Constraints (NLP/DAE)
o Mixed Integer NonLinear Programs (MINLP)
o Dynamic Simulations
o MINLPs with Differential and Algebraic Constraints (MINLP/DAE)
o Optimal Control Problems (OCP)
o Mixed Integer Optimal Control Problems (MIOCP)

The MINOPT modeling language allows for the natural representation of
mathematical models using an advance modeling architecture.  Large,
complex models can be expressed in a concise, compact, and
understandable form.  Since the models are easy to understand, the can
be easily debugged, modified, and maintained.

MINOPT has some important key features:
o Clear and concise representation of complex mathematical models
o Representation of both algebraic and DYNAMIC models
o Support for a broad variety of natural mathematical expressions
o Capability to add, change, or delete the sets, variables, data,
and constraints easily
o Capability to accept model information and data provided in
separate input files
o Checks of model syntax and consistency
o Efficient solution for MIXED-INTEGER NONLINEAR PROGRAMMING problems
o Efficient solution for problems with dynamic models
o Efficient INTEGRATION and SENSITIVITY ANALYSIS
o Connection to Chemkin for kinetic modeling
o Ability to switch easily among various solvers
o Ability to fine tune the solution algorithms with an extensive
list of options

MINOPT has links with many popular solvers:
o CPLEX
o LPSOLVE
o MINOS
o NPSOL
o SNOPT
o DASOLV
o DAESSA

MINOPT also provides algorithms for the solution of MINLPs
o Generalized Benders Decomposition (GBD)
o Outer Approximation and its variants (OA, OA/ER, OA/ER/AP)
o Generalized Cross Decomposition (GCD)

MINOPT has an extensive set of options as well as access to the solver
options and parameters.  This makes it possible to tune the various
algorithms and select different algorithm parameters.

MINOPT models are portable and can be used across various platforms.
The MINOPT algorithmic framework is currently available for the
following platforms (operating systems):
o Sun (SunOS 5.5.1)
o HP (HP-UX 10.20)
o IBM (AIX 3.2)
o SGI (IRIX 5.3)
o Intel (Windows 95/NT) (Available soon)

http://titan.princeton.edu/MINOPT/
or email
minopt@titan.princeton.edu

For purchasing and Licensing Information, contact
Jean A. Mahoney
Director, Technology Transfer and Trademark Licensing
New South Building
P.O. Box 36
Princeton, NJ  08544-0036
tel: 609-258-3097
fax: 609-258-1159
jean@Princeton.EDU

PACKAGE: MatView
From: Tamara Kolda
DATE: Fri, 21 Aug 1998 17:30:57 +0000
Subject: New Sparse Matrix Visualization Tool

MatView: Scalable Sparse Matrix Viewer

New at Oak Ridge National Laboratory!

MatView is a handy tool for viewing and exploring large sparse
matrices.  Using MatView, a sparse matrix with millions of elements
can be reduced to a graphically viewable size for overviews of the
high-level structure, or a detailed view can be obtained by zooming
in and navigating through small regions of the matrix.

MatView provides:

* Scalability: Efficient Viewing of Very Large Matrices.
* Easy Thumbnail Navigation, and Zooming In & Out of Matrix Details.
* A Variety of Data Reduction Functions (Avg, Min/Max, Sum, Std, Var).
* Custom Color Adjustments, or Greyscale Rendering.
* Viewing of Matrix Pattern Only, If Desired.
* Printing of Matrix Views, or Saving Views as PostScript / PPM.
* Compatibility with Matrix Market Format, Harwell-Boeing Format,
and Matlab MAT Files.


http://www.epm.ornl.gov/~kohl/MatView


Project Status:

MatView is built using the Tcl/Tk system, and so should theoretically
run anywhere that Tcl/Tk runs (so far tested only on Unix platforms).
MatView is an ongoing project, with ever-continuing user interface
modules for simple matrix transformations, matrix graphing support,
and support for more matrix file formats.  This work is preliminary
and experimental, and is intended only as an assistant to more
elaborate linear algebra solvers and systems.

Contact:

For more details on MatView or any questions, email Jim Kohl
at "kohl@msr.epm.ornl.gov".

MatView Research is supported by the Applied Mathematical Sciences
Research Program, Office of Energy Research, U. S. Department of Energy,
under contract No. DE-AC05-96OR22464 with Lockheed Martin Energy
Research Corporation.

PACKAGE: Colamd
From: Tim Davis
DATE: Thu, 27 Aug 1998 16:33:39 -0400
Subject: Column Minimum Degree Ordering Algorithm

We would like to announce the release of a new sparse matrix ordering
routine, colamd.  Colamd computes a permutation Q such that PAQ=LU typically
has less fill-in than PA=LU, when P is selected via numerical partial pivoting.
It also produces a good ordering for related problems, the Cholesky or LDL'
factorization of AA' or A'A and the QR factorization of A.

Colamd is written in ANSI C.  Included is a Matlab interface for it, and for
symamd.  The symamd mexFunction is used to find a good permutation P such that
PAP' = LL' (or LDL') has less fill-in than A=LL'.  It's based on colamd (by
forming a matrix M such that M'M has the same pattern as A, and then performing
a column ordering on M).  Symamd is only callable from Matlab.

By default, colmmd is used whenever you use "\" or "/" in Matlab.  Colamd can
be used in place of the colmmd Matlab function (but not by "\" or "/", though -
you would have to use lu() or chol() explicitly).  Colamd is typically much
faster than colmmd, and usually produces better orderings.  Likewise, symamd
is much faster than symmmd, and almost always produces better orderings.
However, symamd is slower than AMDBAR (in Netlib) and MC47 (in the Harwell
Subroutine Library), and produces comparable orderings.

Like colmmd, the colamd method represents the graph of A'A implicitly, taking
only O(nz in A) memory to do so.  The time taken by colamd is O(the sum of the
squares of the nonzeros in each column of A, exluding "dense" columns, which
are ignored), which is the same time complexity as colmmd.  This is also
the same as the time taken to form the matrix AA', if dense columns are
ignored.

The code for colamd and symamd, sufficient documentation on how to use them,
and a Matlab demo, are available at


http://www.cise.ufl.edu/~davis/colamd/

Colamd is intended to be included as the preordering for a future release of
SuperLU (in Netlib).  Colamd and symamd have also been submitted to Netlib and
to the Mathworks user-contributed (Version 5) ftp site.  There are no licensing
restrictions on their use or distribution, except to maintain an authorship and
copyright notice.  A technical report & MS thesis are in the works, which will
include further documentation and performance results.  They will appear in
the web site, above.

Tim Davis (Univ. of Florida), Stefan Larimore (Univ. of Florida),
John Gilbert (Xerox PARC), and Esmond Ng (Oak Ridge National Laboratory).

PACKAGE: HQP
DATE: Tue, 15 Sep 1998 10:28:07 +0200
From: Ruediger Franke
To: interior-point-methods@mcs.anl.gov
Subject: new HQP/Omuses version under LGPL
Sender: owner-interior-point-methods@mcs.anl.gov

The nonlinear sparse optimization solver HQP and the front-end Omuses
for optimal control problems have now been released in the new version
1.5 under the GNU Library General Public License (LGPL).

Compared to former versions, following important extensions were made:
-- Mehrotra's interior point algorithm has been implemented for HQP by
E. Arnold
-- new block-wise matrix solver for multistage problems by E. Arnold
-- more robust BFGS update based on eigenvalues of Hessian blocks
-- watchdog algorithm

The source code release is available from
ftp://olymp.systemtechnik.tu-ilmenau.de/pub/tools/omuses

Ruediger Franke

PACKAGE: TOMLAB
ANNOUNCEMENT: The TOMLAB 1.0 Optimization Environment in Matlab

The first official release of the Matlab 5 based optimization
environment TOMLAB is available at

http://www.ima.mdh.se/tom,
     the home page of the Applied Optimization and Modeling group (TOM) at
Malardalen University, Vasteras, Sweden. A 160 page User's Guide in
postscript format is available. For a quick guide showing the ease of
use, see the web pages.
TOMLAB 1.0 is free for academic use.

Much effort has been put on advanced design utilizing the power and
features of Matlab.  The design principle is:
*** Define your problem once, optimize using any suitable solver. ***
This is possible using general gateway and interface routines, global
variables, string evaluations and structure arrays.
A stack strategy for the global variables makes recursive calls
possible, in e.g. separable nonlinear least squares algorithms. One
structure holds all information about the problem and one holds the
results.
TOMLAB should be seen as a proposal for a standard for optimization in
Matlab.

TOMLAB offers about 65 numerically robust algorithms for linear,
discrete, nonlinear, global optimization and constrained nonlinear
parameter estimation. It includes an advanced graphical user interface
a lot of predefined test problems.  New user-defined problems are
TOMLAB has interfaces to C, Fortran, MathWorks Optimization TB, CUTE
and AMPL.
and four types of numerical differentiation are included.  Currently,
MEX-file interfaces have been developed for the commercial solvers
MINOS, NPSOL, NPOPT,
NLSSOL and QPOPT. A problem is solved by direct call to a solver or a
general multi-solver driver routine, or interactively via the GUI or a

TOMLAB is very easy for the occasional user and student to use,
directly giving access to large set of solvers and algorithms. For the
optimization algorithm developer and the applied researcher in need of
optimization tools it is very easy to compare different solvers or do
test runs on thousands of problems.
A tool is provided to automate the tedious work of making
computational result
tables from test runs, directly making LaTeX tables for inclusion in
papers.

The TOMLAB solvers all explicitly handle bounds and linear
constraints,
with an input model upper/lower bound format like NPSOL. Implemented
solvers for general NLP problems include various SQP algorithms
(Schittkowski,
Gill et al., Fletcher-Leyffer, and Han-Powell).  Quadratic programming
(sub-)problems are solved either with QPOPT or the TOMLAB qpSolve,
which is using an active-set method and negative curvature directions
for
indefinite problems.  A structural trust region algorithm for
partially separable functions on convex sets is also implemented (Conn
et.al).

Nonlinear least-squares methods include Gauss-Newton with subspace
minimization, Fletcher-Xu, Al-Baali-Fletcher and the Huschens TSSM
method, combined with an active-set strategy to handle bounds and
linear constraints. The most common unconstrained algorithms are
implemented: Newton, quasi-Newton
and conjugate-gradient methods. Global optimization problems without
derivatives are solved using the DIRECT and EGO algorithms (Jones et
al).

For linear programming, different types of simplex algorithms are
implemented as well as the dual simplex algorithm. MIP problems are
treated by
a branch and bound method and a cutting plane algorithm. Solvers are
also available for various network programs and dynamic programs.

Happy computing with TOMLAB! (Feedback is welcome)

Kenneth Holmstrom

---------------------------------------------------------------------
Dr. Kenneth Holmstrom, Research Director kenneth.holmstrom@mdh.se
Applied Optimization and Modeling (TOM)  http://www.ima.mdh.se/tom
Center for Mathematical  Modeling (CMM)
Dept of Mathematics and Physics (IMa)    +46 21 10 14 39  Office phone
Malardalen University, P.O Box 883       +46 21 10 13 30  Fax
S-721 23 Vasteras, Sweden
http://www.ima.mdh.se/personal/hkh
---------------------------------------------------------------------

PACKAGE: LMITOOL
From lmitool@ensta.fr Wed Jan 13 07:00:16 1999
From: lmitool@ensta.fr
Message-Id: <199901131008.LAA29096@ensta.ensta.fr>
DATE: Wed, 13 Jan 1999 11:15:40 MET
Subject: Announce : Lmitool-2.0 Package
X-UIDL: 82be0e6f6d6bd5a3a5d821eef2af3f3a

Dear user,

we are pleased to announce the new release of Lmitool package

Lmitool-2.0 : An Interface to Solve LMI Problems.

Introduction

LMITOOL-2.0 is a user-friendly package for LMI optimization. It acts as
an interface for the Semidefinite Programming methods (3 are now
available : SP developed by L. Vandenberghe and S. Boyd ; SDP developed
by Alizadeh, J.-P. Haeberly, M. Nayakkankuppam and M.L. Overton ; SDPHA
developed by Florian A. Potra, Rongqin Sheng and Nathan Brixius).

An LMI optimization problem is one where matrix variables are subject
to equality and positive-definiteness constraints, and the objective is
a linear function of these variables. Many engineering problems,
including among others (nonlinear) convex optimization problems, can be
formulated as LMI problems; see for instance, the book Linear Matrix
Inequalities in Systems and Control Theory, by Boyd, El Ghaoui, Feron,
Balakrishnan, SIAM, 1994.

Using the user-friendly Graphic User Interface (TKLMITOOL) of the
LMITOOL-2.0 package, a user can in a few minutes solve Linear Matrix
Inequality problems with matrix variables. All the user has to do is to
specify the LMI constraints and linear objective of the problem at hand
in a matlab .m file. No special syntax or function is to be learned by
the user. LMITOOL-2.0 allows for arbitrary equality and LMI constraints.

What has changed between Lmitool-1.0 and Lmitool-2.0

- The version 2.0 contains all the functionalities of the version 1.0
- The version 2.0 works under the Matlab version 5.0 (and above, without
warranty).
- 3 Semidefinite Programming methods are now available
- The version 2.0 includes the lastest version of the Graphic User Interface
(GUI) TkLmitool.
- The optimisation options are separated into :
* formatting parameters
* optimisation parameters
- A Matlab demo script is included, showing different example problems.

Where to get Lmitool Package


http://www.ensta.fr/~gropco/lmi/index.html

Distribution files:
- by ftp :
ftp ftp.ensta.fr
cd pub/elghaoui/lmitool-2.0
get lmitool_pkg-2.0.tar.gz

- by the WEB Page :
"http://www.ensta.fr/~gropco/lmi/index.html"

Installation

first step of the installation of Lmitool Package.

Since LMITOOL and TKLMITOOL are still under development, all comments,
remarks, bug reports... are welcome. E-Mail us at lmitool@ensta.fr or
elghaoui@ensta.fr

PACKAGE: PREQN
June 15, 1999.

Software for automatically preconditioning the conjugate
gradient method is now available at


http://www.ece.nwu.edu/~nocedal/preqn.html

The preconditioners have proved to be effective in Newton methods
for large-scale optimization.

Contacts:   J.L. Morales,     jmorales@gauss.rhon.itam.mx
********      J. Nocedal,     nocedal@ece.nwu.edu

Description of the Software
---------------------------

PREQN is a package of Fortran 77 subroutines for automatically
generating preconditioners for the conjugate gradient method. It
is designed for solving a sequence of linear systems

A_i x=b_i, i=1,...,t,

where the coefficient matrices A_i are symmetric and positive definite
and vary slowly. The preconditioners are based on limited memory
quasi-Newton updating and are recommended for problems in which:

i) the coefficient matrices are not explicitly known and only
matrix-vector products of the form A_i v can be computed; or

ii) the coefficient matrices are not very sparse.

PREQN is written so that a single call from a conjugate gradient
routine performs the preconditioning operation and stores information
needed for the generation of a new preconditioner.

PACKAGE: MProbe
January 26, 2004

Hello optimization software developers:

has been available for several months.  The AMPL and GAMS model reader
objects are new.  Feedback appreciated, as always.

MProbe version 5.0.
MProbe is a collection of tools for analyzing mathematical programs,
e.g. to determine the "shape" of nonlinear functions or to evaluate the
effectiveness of a constraint.  New in version 5.0: ability to read the
GAMS language and .NET implementation.

http://www.sce.carleton.ca/faculty/chinneck/mprobe.html

This is a Windows COM object for reading MPS files.  Important methods
include ability to read standard and free-format MPS files, view the
contents as equations, submit variable values and receive back the
constraint and objective function values at that point, edit existing MPS
files or create new MPS files, Write out MPS files.


This is a Windows object (avaiable in both COM and .NET formats) for
reading AMPL models. Exposed properties include the names of variables,
constraints and objectives, variable bounds, constraint types, etc.
Methods include the ability to calculate the value of a constraint or
objective at a given point, ability to return gradients at a point, etc.


This is a Windows object (avaiable in both COM and .NET formats) for
reading GAMS models. Exposed properties include the names of variables,
constraints and objectives, variable bounds, constraint types, etc.
Methods include the ability to calculate the value of a constraint or
objective at a given point, ability to return gradients at a point, etc.


--
John W. Chinneck                                tel: (613) 520-5733
Systems and Computer Engineering                fax: (613) 520-5727
Carleton University

http://www.sce.carleton.ca/faculty/chinneck.html


March 7, 2003

--------------------------
MProbe 4.0 Now Available
--------------------------

MProbe is a software tool for probing mathematical optimization models
of all kinds (LPs, NLPs, MIPs).  It provides a suite of tools for

- How effective are the constraints in the model?
- What are the shapes of the nonlinear constraints and objectives
(convex? concave? both? almost linear?)?  Should I consider
linearizing any of these functions?
- Is the nonlinearly constrained region convex or nonconvex?
- Which constraints contain only binary variables?
- Can I see a plot of a function along a line in n-space?
- Does the shape and sense of the objective function make it
unlikely that I will find a global optimum?
- Can I see a list of the variables sorted in order by the
number of functions in which they appear?
- Can I see a histogram of function value samples taken in the
current variable "box"?
- etc.

--------------------
--------------------

Further information and fully-functional demo copies of MProbe are
available at

http://www.sce.carleton.ca/faculty/chinneck/mprobe.html.
MProbe works with the popular AMPL language for describing
mathematical programs. A student/demo edition of AMPL is included

----------------------------
New Features in MProbe 4.0
----------------------------

- a new Points Workshop which permits exchange of points with
external programs such as solvers, analysis of points, etc.

- a method for finding approximately feasible points, even for
nonconvex feasible regions

- the ability to read and manipulate MPS files directly

- a new method for shrinking variable bounds

- improved feasibility bootstrapping

----------------------------
New Features in MProbe 3.2.2
----------------------------

The most important new features are:

- a number of new routines for tightening the bounds on the region of
interest (normally the feasible region). These include:
- analytic bounding methods for linear constraints,
- individual constraint sampling methods for nonlinear constraints,
- simultaneous constraint sampling methods for nonlinear constraints,
- finding an appropriate initial box size when sampling across the
entire variable range is ineffective.
- much more effective routine for finding the first feasible point in a
new convex sampling enclosure.
- new routine for approximating the prime analytic center to generating
sampling rays when working with
- hit-and-run methods for sampling general convex enclosures.
- integer and binary variables are now snapped to appropriate values for
the purposes of evaluating constraint effectiveness (on user request).

--------------------------
New Features in MProbe 3.0
--------------------------

- The ability to analyze functions within an arbitrary space
defined by convex inequalities.  Using a subset of the
constraints from the model to define this convex enclosure
greatly increases the accuracy of the analyses (e.g. function
shape, effectiveness, etc.).

- An analysis of the necessity/redundancy of the constraints
and variable bounds comprising a convex sampling enclosure.
For necessary constraints, an estimate of the fraction of
the enclosure "surface" that each constraint or bound
comprises.

- Many new ways to plot function profiles in n-dimensional space,
points from an external file (e.g. produced by a solver) to
start your plot from that point.

- Hardware is now the only limit on maximum model size (professional
edition).

- Now reports best optimum value and corresponding point sampled during
analysis of objective functions.

- Many improvements to user interface: status bar, copy/paste
in textboxes, copy from grids, reorganized menus, etc.

----------
Email List
----------

Please email me (chinneck@sce.carleton.ca) if you would like to

John W. Chinneck                   Systems and Computer Engineering
tel: (613) 520-5733                Carleton University
fax: (613) 520-5727                1125 Colonel By Drive
email: chinneck@sce.carleton.ca    Ottawa, Ontario K1S 5B6 CANADA
http://www.sce.carleton.ca/faculty/chinneck.html

PACKAGE: TRON
June 15, 1999

We announce the release of TRON, a trust region Newton method for the
solution of large bound-constrained optimization problems.

TRON uses a gradient projection method to generate a Cauchy step, a
preconditioned conjugate gradient method with an incomplete Cholesky
factorization to generate a direction, and a projected search to
compute the step.  The use of projected searches, in particular,
allows TRON to examine faces of the feasible set by generating a small
number of minor iterates, even for problems with a large number of
variables.

No assumptions of strict complementarity.
Global convergence; fast local convergence.
Identification of optimal face in a finite number of iterations.
An incomplete Cholesky preconditioner with predictable storage requirements.

The current release (Version 1.0) is available from


http://www.mcs.anl.gov/~more/tron

For additional information on TRON, see

Chih-Jen Lin and Jorge J. More',
Newton's method for large bound-constrained optimization problems,
Argonne National Laboratory,
Mathematics and Computer Science Division,
Preprint ANL/MCS-P724-0898,
August 1998 (Revised March 1999).
SIAM Journal on Optimization (to appear)
http://www.mcs.anl.gov/~more/papers/tron.ps.gz

Comments and suggestion should be directed to

Chih-Jen Lin (cjlin@csie.ntu.edu.tw) or Jorge More' (more@mcs.anl.gov)

We are interested in contacting users that will use TRON to solve
new and interesting large optimization problems.

=======================================================================

From: Marco Luebbecke
DATE: Mon, 23 Aug 1999 10:53:53 +0200 (METDST)
To: DMANET@zpr.uni-koeln.de
Subject: [DMANET] 0/1 Vertex Enumeration Code: zerOne 1.70

VERTEX ENUMERATION CODE FOR 0/1 POLYTOPES
zerOne 1.70     NOW AVAILABLE

Given the linear description P = {x | Ax <= b} of an arbitrary
polytope P contained in the unit hypercube {0 <= x <= 1}, zerOne lists
all vertices with all coordinates equal to zero or one.

The linear description of the polytope P is provided in CPLEX' LP
format. The output is in PORTA's POI format.

Since zerOne is a special purpose implementation it is much faster
than general codes. The major benefit, however, is its memory usage
being independent of the output vertices.


http://www.math.tu-bs.de/mo/research/zerone.html


Best regards,
Marco E. Luebbecke

Department of Mathematical Optimization          Phone: +49 531 391 7560
Braunschweig University of Technology              Fax: +49 531 391 7559
Pockelsstrasse 14		             Email: m.luebbecke@tu-bs.de
D-38106 Braunschweig, Germany       WWW: http://www.math.tu-bs.de/~marco

PACKAGE:  GIDEN

AUTHOR:  Jonathan Owen

DATE:  Sep 29, 1999.

A beta release of the new GIDEN-2.0 software environment is
now available through the GIDEN web site:


http://giden.nwu.edu/

GIDEN is interactive software environment designed to
facilitate the visualization of network optimization
problems, solutions, and algorithms.  Features of GIDEN
include the following:

- a graphical interface for building and
modifying networks

- facilities for algorithm animation

- an expandable toolkit of animated algorithm
implementations ("solvers")

- a library of network-related data structures

- platform independence (using Java)

The new version of GIDEN is available only as a Java-1.1
application.  The software can be used on any Java-enabled
computing platform with an available Java virtual machine
provides installers for several platforms, including an
installer for Win9x/NT that contains an appropriate Java
virtual machine.

See the GIDEN web site ("http://giden.nwu.edu/") for more
information on the project.  Please direct any questions or

--
Jonathan H. Owen
Assistant Research Professor
Industrial Engineering and Management Sciences
Northwestern University
Evanston, IL  60208-3119

PACKAGE:  MCS

AUTHOR:  Waltraud Huyer and Arnold Neumaier

DATE:  Feb 8, 2000.

Global Optimization by Multilevel Coordinate Search (MCS)

Source:

http://solon.cma.univie.ac.at/~neum/software/mcs/
MCS is a Matlab program for bound constrained global optimization
using function values only, based on a multilevel coordinate search
that balances global and local search. The local search is done via
sequential quadratic programming. The search is not exhaustive; so the
global minimum may be missed. However, a comparison to other global
optimization algorithms shows excellent performance in many cases,
especially in low dimensions.

The new version 2.0 of MCS (from Feb. 8, 2000) runs under Matlab 5
and has a lot of small changes compared to the previous version.
In particular, a bug involving the option including the local solver
was removed.)

MCS now contains a driver for an easy to use version that runs without
any parameters that need to be set by the user; thus MCS can be used
as a completely black box. However, experienced users may make more
sophisticated choices, according to suggestions specified explicitly.

PACKAGE: SBmethod - A C++ Implementation of the Spectral Bundle Method
AUTHOR:  Christoph Helmberg   helmberg@zib.de
DATE:    Thu Oct 12 2000,  6:00pm +0200

Dear Colleagues,

SBmethod Version 1.1 is now available.

The source code
of my implementation of the Spectral Bundle Method
for Eigenvalue Optimization is now available at


http://www.zib.de/helmberg/SBmethod

Unfortunately, the code is not as general
as it could be and the source code is certainly
far from being well organized.
I apologize for this, but hope that it may
be useful for some of you anyways.

The main additions in version 1.1 are:
* a starting point heuristic
* a heuristic for updating the bundle size dynamically
* a heuristic for choosing the Lanczos parameters
* the options have been reorganized
* the manual should now be acceptable

The new default heuristics seem to produce reasonable
results in many cases but they most certainly won't give
the "best" parameter setting. The heuristics have been
added in response to several requests for an acceptable
default setting.

The manual is available as ZIB-Report ZR-00-35 at


ftp://ftp.zib.de/pub/zib-publications/reports/ZR-00-35.ps

Best,

Christoph Helmberg

******************************************************************

Christoph Helmberg

Takustrasse 7
D-14195 Berlin
Germany

Tel.:   ++49 30 84185-294
Fax.:   ++49 30 84185-269
e-mail: helmberg@zib.de
WWW:    http://www.zib.de/helmberg

PACKAGE:  CirCut
DATE:     Dec 13, 2000

Announcing software CirCut version 0.1120

CirCut is a Fortran90 code for approximating some NP-hard, binary
quadratic programs.  The current version can generate approximate
solutions to Max-Cut and Max-Bisection problems.

-- Where to get it? --

CirCut distributions are Gnu-compressed-tar files: circut*****.tar.gz,
where "*****" designates the version number.


http://www.caam.rice.edu/~zhang/circut/

CirCut is free software and comes with no warranty. All files written
by this author are copyrighted under the terms of the GNU General Public

---------
Yin Zhang
Dept. of CAAM
Rice University
Houston, TX 77005, USA

http://www.caam.rice.edu/~zhang/
PACKAGE: CSDP
AUTHOR: Brian Borchers
DATE: 25 September 2004

CSDP 4.9 has been released. See


http://www.nmt.edu/~borchers/csdp.html

This version includes:

- Improved handling of problems with unbounded feasible region.  For
example, the problems eco7, reimer5, butchers, trimlon2, and taha1a
can now be much better solved.

- Improved speed on problems with large numbers of LP variables.

- The MATLAB interface now works correctly under MATLAB 7.0 as well
as 6.x.

DATE: 28 October 2003.

CSDP 4.6 has been released.  See

CSDP 4.6 fixes two bugs in CSDP 4.5:

- There was some confusion about the correct norm to use in the DIMACS
error measures, and the implementation of the measures in version 4.5
was incorrect.

- readsol.m in the MATLAB interface worked incorrectly on certain problems.

DATE: 25 October 2003.

CSDP 4.5 has been released.  See


http://www.nmt.edu/~borchers/csdp.html

Changes in version 4.5 include:

- Eliminated some unneeded matrix variables to conserve virtual storage.
For a problem with m constraints and matrix variables with blocks of
size n1, n2, ..., nk, the storage required is roughly

Storage=8*m^2+8*13*(n1^2+n2^2+...+nk^2)+O(m)+O(n1)+...+O(nk)  bytes

- Changed the balance of primal/dual infeasibility versus duality gap.
The old version of CSDP would insist on keeping feasibility once it
had been obtained.  The new version will give up some degree of
feasibility in order to reduce the duality gap.  Overall, this should
better balance the primal and dual infeasibilities versus the duality
gap.

- Fixed a bug in the MATLAB interface that effected the solution of pure
LP problems with no SDP blocks.

DATE: 7 October 2003.

CSDP 4.4 has been released.  See


http://www.nmt.edu/~borchers/csdp.html

Features:

- Improved performance.  On a large subset of the SDPLIB problems, this
version ran about 15% faster than 4.3.  (Before: 4 hours 37 minutes,
After: 3 hours 57 minutes.)

- New free_prob() routine for returning the memory associated with a problem.

- Fixed various memory leaks.  These weren't an issue with the stand alone
solver (since all storage is returned to the OS at the end of the program
run), but are an issue in the subroutine library.

Brian Borchers                          borchers@nmt.edu
Department of Mathematics               http://www.nmt.edu/~borchers/
New Mexico Tech                         Phone: 505-835-5813
Socorro, NM 87801                       FAX: 505-835-5366


http://www.nmt.edu/~borchers/csdp.html


Previous update:
DATE: 13 September 2003.

CSDP 4.3 has been released.

This release fixes a number of minor but irritating bugs:

- parameters.pinftol and parameters.dinftol weren't being read from the
param.csdp file and used by the code- rather, values of 1.0e-8 were
hardcoded.

- The read_prob() routine crashed if there was no newline at the end of
the last line of the problem.

- The MATLAB interface failed on certain problems involving LP variables,
especially problems with no SDP blocks.

- Minor typos in the users guide.

Brian Borchers                          borchers@nmt.edu
Department of Mathematics               http://www.nmt.edu/~borchers/
New Mexico Tech                         Phone: 505-835-5813
Socorro, NM 87801                       FAX: 505-835-5366


http://www.nmt.edu/~borchers/csdp.html
PACKAGE: OPT++
AUTHOR: Juan Meza
DATE: Jul 19, 2002

The newest version of OPT++ 2.0, an object-oriented package for
nonlinear optimization is now available.  There have been significant
improvements and new capabilities added since the last release.  The new
version includes support for general linear and nonlinear constraints, a
new parallel optimization method, and a new nonlinear interior point
method.  Other capabilities include parallel direct search, nonlinear
conjugate gradient, quasi-Newton and full Newton methods.  OPT++ has
been ported to various platforms including IX86 Linux, Sun, SGI, and
DEC.  A complete set of documentation has also been added with
descriptions of the major classes and extensive sample problems.

The new release of OPT++ is under the GNU Lesser GPL license and may be

http://csmr.ca.sandia.gov/projects/opt++/
 For further information you can contact Juan Meza (JCMeza@lbl.gov),
Patty Hough (pdhough@ca.sandia.gov) or Pam Williams
(pwillia@sandia.gov).

--
High Performance Computing Research
Lawrence Berkeley National Laboratory
Berkeley, CA  94720

http://www.nersc.gov/~meza



From: Arnold Neumaier
Date: Fri Mar 26, 2004  3:09:43 PM America/New_York
To: opt@turing.siam.org
Subject: SIAG/OPT: SNOBFIT for robust noisy optimization

SNOBFIT (Stable Noisy Optimization by Branch and FIT)
is a MATLAB 6 package for the robust and fast solution
of noisy optimization problems with continuous variables
varying within bound, possibly subject to additional
soft constraints. Discrete variables are not supported.

Objective function values must be provided by a file-based
interface; care is taken that the optimization proceeds
reasonably even when the interface produces noisy or
even occasionally undefined results (hidden constraints).
The interface makes it possible to use SNOBFIT with new
data entered by hand, or by any automatic or semiautomatic
experimental system.

This makes SNOBFIT very suitable for applications to the
selection of continuous parameter settings for simulations
or experiments, performed with the goal of optimizing some
user-specified criterion. Since multiple data points can be
entered, SNOBFIT can take advantage of parallel function
evaluations.

The method combines a branching strategy to enhance the
chance of finding a global minimum with a sequential
models to have good local properties. Various safeguards
address many possible pitfalls that may arise in practical
applications, for which most other optimization routines
are ill-prepared. Soft constraints are taken care of by
a new penalty-type method with strong theoretical properties.

Source code and a description of the methods used can be
found at

http://www.mat.univie.ac.at/~neum/software/snobfit/
or via my Global (and Local) Optimization web site.

Arnold Neumaier



COIN-OR: Computational Infrastructure for Operations Research:

open source for the OR community.


http://wwww-124.ibm.com/developerworks/opensource/coin/

Our goal is to create for mathematical software what the open literature is for mathematical theory.

We want to build an open-source community for operations research software in order to speed deployment of models, algorithms, and cutting-edge research, as well as provide a forum for peer review of software similar to that provided by archival journals for theoretical research. \240 This is a lofty goal, but we believe it's a worthwhile one.\240 We have an idea, but we don't have all the answers. Only the community of users and contributors can define what is needed to make it a reality. For further information, please see the FAQs page, as well as the COIN-OR resources page.

The following is a list of projects currently being hosted by COIN-OR:

• BCP: a parallel branch-cut-price framework,
• CGL: a cut generation library,
• CLP: COIN L P, a native simplex solver,
• DFO: a package for solving general nonlinear optimization problems when derivatives are unavailable,
• IPOPT: an interior point algorithm for general large-scale nonlinear optimization.
• Multifario: a continuation method for computing implicitly defined manifolds.
• NLPAPI: a subroutine interface for defining and solving nonlinear programming probl ems.
• OSI: an open solver interface layer,
• OTS: an open framework for tabu search,
• SBB: Simple Branch and Bound, a branch and cut code,
• SMI: Stochastic Modeling Interface, for optimization under uncertainty,
• VOL: the Volume Algorithm,


From: Andreas Waechter
Date: Thu, 11 Mar 2004 18:46:32 -0500 (EST)
Subject: [Coin-announce] Announcing new release of IPOPT 2.2.0

A new release of IPOPT, the interior point code for nonlinear optimization
in COIN-OR, is now available.  It can be obtained via CVS (in the MAIN
branch) or in the latest IPOPT tarball (date >= Mar 11).

Details about IPOPT can be found at


http://www.coin-or.org/Ipopt

Information about an IPOPT specific mailing list is at


http://www-124.ibm.com/developerworks/opensource/mailman/listinfo/coin-ipopt

Some highlights of the new release:

- Improved efficiency and robustness.

- A new restoration phase for the filter method has been implemented.
As a consequence, the third-party program TRON is no longer required
(for the default full-space option of IPOPT).  The new restoration phase
is considerably more robust.

- An interface for C has been added.

- Dynamic memory allocation can be used so that a pre-estimate of the
required work space is no longer required.

- The subroutines/functions for evaluating values and derivatives of the
objective functions and constraints are now passed as function
pointers, i.e. those routines do no longer have fixed names.  This also
allows the compilation of IPOPT as a DLL.

- Much easier installation on Unix/Linux/Cygwin thanks to autoconf (a la
./configure' and make install').

- Better support for Windows, both within Cygwin and for native compilers.
Project files generated by Microsoft Visual Studio 2003 (Standard)
with the Intel Fortran 8.0 compiler are included.

_______________________________________________
Coin-announce mailing list

Coin-announce@www-124.ibm.com http://www-124.ibm.com/developerworks/oss/mailman/listinfo/coin-announce




From: Mike Powell
Subject: NEWUOA (NEW Unconstrained Optimization Algorithm)
Date: Fri, 16 Jan 2004

Unconstrained Minimization without Derivatives

Recently, after about 2 years of development, I finished writing
some Fortran software for unconstrained minimization without derivatives.
I believe that most results of academic research should be available
free of charge, and I am delighted when my work is useful. Therefore
please let me know by e-mail if you would like to receive a copy of the
Fortran. My address is 
mjdp@cam.ac.uk.

The name of the software is NEWUOA (NEW Unconstrained Optimization
Algorithm). It is a development of UOBYQA (Math. Prog. B, Vol. 92, pp.
555-582, 2002), which is unsuitable for large n (the number of variables),
because the quadratic models of UOBYQA are constructed by interpolation
to (n+1)(n+2)/2 values of the objective function. On the other hand, the
number of interpolation conditions in NEWUOA is a parameter, the value
2n+1 being recommended, which reduces the magnitude of the routine work
of each iteration from n**4 to between n**2 and n**3. Thus NEWUOA has
solved problems successfully with up to 200 variables, which would be far
too onerous for UOBYQA. The freedom in each new quadratic model of NEWUOA
is taken up by minimizing the Frobenius norm of the change to the second
derivative matrix of the model.

No report is available yet that describes all the details of NEWUOA,
but I intend to write one in the next 6 months. The work has taken so
long, because rounding errors have caused severe loss of accuracy in an
updating calculation. I found an adequate cure to this damage last June,
which is presented in the report "On updating the inverse of a KKT matrix"
(Number DAMTP 2004/NA01, University of Cambridge). That report is on the
web at the address www.damtp.cam.ac.uk, where one clicks on Numerical
Analysis and then on Reports, because I do not yet have a proper home page
myself. I hope that the NEWUOA software will be helpful to many readers.

January 16th, 2004                       Michael J.D. Powell




SYMPHONY VERSION 4.0 RELEASED
From: Ted Ralphs
Tue, 25 Nov 2003

SYMPHONY (Single- or Multi-process Optimization over Networks) is an
open-source framework for implementing customized branch, cut, and price
algorithms on a wide variety of computing platforms, including
single-processor, shared memory multi-processor, and distributed memory
multi-processor. SYMPHONY is designed primarily for branch and cut
algorithms, but also has limited support for column generation.

There has been a significant amount of new development since the last
version of SYMPHONY was released, making version 4.0 more efficient and
easier to use. SYMPHONY now works out of the box as a generic MIP solver
and makes full use of the COIN-OR libraries for parsing MPS files,
generating cuts, and interfacing to most available LP solvers through
the Open Solver Interface. SYMPHONY can also read GMPL (a subset of
AMPL) files using GLPK's parser. The solver may be customized through
the implementation of user functions that override SYMPHONY's default
behavior. A suite of applications that demonstrate various ways in which
SYMPHONY can be customized is now available. In addition, the SYMPHONY
documentation has been completely overhauled and updated.

both SYMPHONY and the new suite of applications built using SYMPHONY,
visit

http://www.branchandcut.org/SYMPHONY/.
Please let me know if you
have any questions or problems.

Ted
--
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784

tkralphs@lehigh.edu
http://www.lehigh.edu/~tkr2




PACKAGE: MOSEK
From:    Erling Andersen
Version: 3.1, August 2004.


MOSEK is a state-of-the-art solver for linear programming, conic quadratic programming, and other optimization problems. Trial versions of the software can be downloaded for free. The full-blown version of the software is free for students.

MOSEK ApS has contributed an OSI module for the MOSEK solver. Interested users can check out the COIN/Osi/OsiMsk interface. Send feedback to bo.jensen@mosek.com or post to the coin-discuss list.

PACKAGE: Clp
From:    John Forrest
Version: 1, October 18, 2004.


(Apologies for multiple postings)
In conjunction with the move of COIN-OR  to its new host,  we are pleased to announce Version 1.0  of  the COIN-OR LP (CLP) Solver.

CLP Version 1.0 contains:
- a simplex code with dual and primal variants (the dual being the preferred method),
- a presolve capacity which exists in the Coin directory for use by other solvers as well,
- an extensible matrix format which allows for specialized formats, such as a network or all ones.
- virtual message handlers and event handlers for sophisticated users,
- dual and primal ranging,
- an interior point solver,
- three solvers for optimizing a quadratic objective function over a linear constraint set: (i) an interior point solver, (ii) a simplex solver and a (iii) sequential LP solver, and
- extensible matrix formats  for more ambitious structures, e.g. a GUB matrix or a dynamic matrix.

Version 1.0 includes changes which make CLP faster when being used by SBB (Simple Branch and Bound, or as some people have said Slow Branch and Bound).  This will be an on-going project.

Prodded and helped by Thorsten Koch I have just added the ability to import and export bases in MPS format so now we are up to 1.00.01!

Thank you to the  users and contributors in the open-source community for their stress testing, bug reports, and suggestions. Your feedback is invaluable for improving CLP.

John Forrest

PACKAGE: COIN branch-and-cut
From:    John Forrest
Version: 0.70, October 29, 2004.


In order to avoid any confusion with GAMS code SBB and because I can no longer really claim that the Sbb code was a Simple Branch and Bound,  I have renamed it as Cbc (Coin Branch and Cut).  At present the two codes are identical apart from every occurrence of sbb being replaced by cbc.  The Sbb directory and project will remain for as long as anyone wants but will not be changed after this Sunday.

To mark the occasion I have gone from version 0.60 to 0.70!

Obviously if you still use Sbb no changes are needed.  If you change over to Cbc you will need to do a global edit on your files to change sbb to cbc.  I apologize for any inconvenience and I would be interested to hear from anyone who finds that the global edit changes something else by mistake.  Can anyone think of an English word which has sbb in it?

John Forrest