Optimization packages

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

The following is taken from the
ABACUS home page:

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.

ABACUS has become open source software distributed under the GNU lesser general public license.

ABACUS home page: http://www.informatik.uni-koeln.de/abacus/

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

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
on the PENNON home page


This article describes a generalization of the PBM method by Ben-Tal
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

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. For more details, please visit

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

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

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


I welcome and appreciate any feedback of MCF users! Please mail it to

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 (postscript file) and sample problems, can be downloaded from the COPL website at:

For more information, contact

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

PACKAGE: SDPT3 From: Toh Kim Chuan SDPT3 - a MATLAB software package for semidefinite-quadratic-linear programming, version 3.0 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:

Sep 28, 1999: Announced version 2.1:
and a user's guide is at

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 

and a user's guide is at
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. 
If any readers downloaded the code from 11/24/98 to 11/30/98, your
version of mexProd2.mexsol could be bad; please download the code 
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. 
     Mike Todd
        School of Operations Research, Cornell University,
        Ithaca, NY 14853-3801 
     Reha Tutuncu 
        Department of Mathematical Sciences, Carnegie Mellon University, 
        Pittsburgh, PA 15213 

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 username ANONYMOUS, enter password as directed, and type 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 intelligently to hypercube and mesh architectures, and easy access to the 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 those, please contact us at jcastrop@eio.upc.es. There is also additional 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, please contact us at jcastrop@eio.upc.es. This code has been released for academic use only. For other types of usage, please contact with the authors at some of the ordinary or e-mail addresses below. 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

Main difference to the previous AD version DONLP2_AD:

 - 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.
It is intended for testing purposes and accepts input in AMPL. It uses
AMPL's automatic differentiation feature.

PACKAGE: GULF Dear Colleague, I would like to inform you that you can download demo-version of GULF from the following WWW page:

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. 

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:

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.

If you have not access to the WWW, please e-mail me and I will send you 
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:

The source code for the Unix version, together with executables for
various architectures, can be obtained from


PCx can also be executed remotely through the NEOS Server. For
details, see


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

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

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

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:

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
  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

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

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:
  (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:
3) I want to ask excellent students to apply for an excellent PhD project,
 info at:
Best Regards,

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
One of the improvements is the use of a product-form Cholesky to handle
dense columns, as proposed recently by Goldfarb and Scheinberg.

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

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

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:


Please send your feedback to:  sturm@cauchy.crl.mcmaster.ca

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.
 CANADA                       |

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 from the CUTSDP Home Page at:

The user manual can be obtained via:


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 Reply-To: Mahesh Joshi ========================================================================== ***** Announcing PSPASES 1.0 and WSSMP 3.7 ========================================================================== "PSPASES : A Scalable Parallel Direct Solver Library for Sparse Symmetric Positive Definite Systems"

  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 

  *  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 

  *  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.

  3. Added README.USAGE file explaining some usage related issues, and the
     formats, and changed README.INSTALL file.

  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

  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 

  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


  to obtain the software, the manual, related technical papers, usage notes,
  and to see some performance benchmarking results. Please read the terms
  and conditions for use, given at the website, before downloading and 
  using the PSPASES software.

  If your machine does not have access to the web, then you may obtain the 
  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
  --- 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 

  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

Previous version



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

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
  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 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:

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)

For more information, visit the MINOPT homepage at
or email

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

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. * Loading of Compressed or Gzipped Matrix Files. Software Download: The MatView 1.0 Alpha Software is available for FREE DOWNLOAD from the MatView Home Page, at:

 Please feel free to download MatView and give it a try!

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
 additions and improvements, and there are plans to add pluggable
 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.


 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

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 Reply-To: Ruediger Franke 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
     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 
     TOMLAB should be seen as a proposal for a standard for optimization in 
     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 
     (GUI), menus, graphics and 
     a lot of predefined test problems.  New user-defined problems are 
     easily added. 
     TOMLAB has interfaces to C, Fortran, MathWorks Optimization TB, CUTE 
     and AMPL.  
     Automatic differentiation is easy using an interface to ADMAT/ADMIT TB 
     and four types of numerical differentiation are included.  Currently, 
     MEX-file interfaces have been developed for the commercial solvers 
     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 
     menu system.
     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 
     The TOMLAB solvers all explicitly handle bounds and linear 
     with an input model upper/lower bound format like NPSOL. Implemented 
     solvers for general NLP problems include various SQP algorithms 
     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 
     indefinite problems.  A structural trust region algorithm for 
     partially separable functions on convex sets is also implemented (Conn 
     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 
     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                

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 Home Page:

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

    - by the WEB Page :
      follow the links in the section "Download the package" at


  The README file of the distribution contains informations about the
  first step of the installation of Lmitool Package.

Comments, bug reports

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

PACKAGE: PREQN June 15, 1999. Software for automatically preconditioning the conjugate gradient method is now available at
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: A new release of MProbe is now available for download. The MPS file reader 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.

MPS File Reader Object 1.2.
  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.

AMPL Model Reader Object 1.0.
  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.

GAMS Model Reader Object 1.1.
  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
Ottawa, Ontario K1S 5B6 CANADA

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 
answering general queries about optimization models such as:

  - 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.

For More Information

Further information and fully-functional demo copies of MProbe are 
available at
MProbe works with the popular AMPL language for describing 
mathematical programs. A student/demo edition of AMPL is included 
with the download.  A new technical paper describing the techniques
used in MProbe is also linked from the MProbe home page.

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

- Many new ways to plot function profiles in n-dimensional space,
  including along the gradient direction.  You can also read in
  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

- 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
be alerted about new releases of MProbe (low frequency list:
about 1-4 mailings per year).

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

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. Advantages of TRON include 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

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)

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
Reply-To: m.luebbecke@TU-BS.DE

	           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.

For further information and download:


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:

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
(version 1.1.7 or higher). The GIDEN-2.0 download page
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
comments via email to "giden@iems.nwu.edu".

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

PACKAGE: MCS AUTHOR: Waltraud Huyer and Arnold Neumaier DATE: Feb 8, 2000. Global Optimization by Multilevel Coordinate Search (MCS) Source:
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

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



Christoph Helmberg


     Christoph Helmberg

     Konrad-Zuse-Zentrum fuer Informationstechnik Berlin
     Takustrasse 7
     D-14195 Berlin

     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. To get a version, please visit the CirCut home page on the Web:

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 
License as published by the Free Software Foundation. 

Yin Zhang
Dept. of CAAM
Rice University
Houston, TX 77005, USA
AUTHOR: Brian Borchers
DATE: 25 September 2004

CSDP 4.9 has been released. See


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
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

  - 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
  - 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



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
  - 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



AUTHOR: Juan Meza
DATE: Jul 19, 2002

OPT++ 2.0 Available for Download

 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
downloaded at:
 For further information you can contact Juan Meza (JCMeza@lbl.gov),
Patty Hough (pdhough@ca.sandia.gov) or Pam Williams

Department Head                         
High Performance Computing Research   
Lawrence Berkeley National Laboratory               
One Cyclotron Road, MS: 50B-2239
Berkeley, CA  94720

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

The method combines a branching strategy to enhance the
chance of finding a global minimum with a sequential
quadratic programming method based on fitted quadratic
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
or via my Global (and Local) Optimization web site.

Arnold Neumaier

COIN-OR: Computational Infrastructure for Operations Research:

open source for the OR community.


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:

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


Information about an IPOPT specific mailing list is at


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 

      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

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.

For more information on SYMPHONY and to download the source code for
both SYMPHONY and the new suite of applications built using SYMPHONY,
Please let me know if you
have any questions or problems.

Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University

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.

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