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 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.
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
on the PENNON home page
http://www2.am.uni-erlangen.de/~kocvara/pennon/
Abstract:
---------
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
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.
For more details, please visit
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
(postscript file) and sample problems, can be downloaded
from the COPL website at:
http://dollar.biz.uiowa.edu/col/
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:
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.
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
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
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.
http://www.mcs.anl.gov/home/otc/Server/neos.html
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:
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.
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:
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
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 |
=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
from the CUTSDP Home Page at:
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
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"
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.
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
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,
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
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
WSMP
==========================================================================
=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)
For more information, visit the MINOPT homepage at
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.
* 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:
http://www.epm.ornl.gov/~kohl/MatView
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.
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
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
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
(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
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
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
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
Home Page:
http://www.ensta.fr/~gropco/lmi/index.html
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
"http://www.ensta.fr/~gropco/lmi/index.html"
Installation
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
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:
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.
http://www.sce.carleton.ca/faculty/chinneck/mprobe.html
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.
http://www.sce.carleton.ca/faculty/chinneck/MPSreader/MPSobject.html
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.
http://www.sce.carleton.ca/faculty/chinneck/AMPLreader/AMPLObject.html
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.
http://www.sce.carleton.ca/faculty/chinneck/GAMSreader.html
--
John W. Chinneck tel: (613) 520-5733
Systems and Computer Engineering fax: (613) 520-5727
Carleton University
Ottawa, Ontario K1S 5B6 CANADA
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
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
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
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
comprises.
- 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
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
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
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.
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
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
Reply-To: m.luebbecke@TU-BS.DE
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.
For further information and download:
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
(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:
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
Konrad-Zuse-Zentrum fuer Informationstechnik Berlin
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.
To get a version, please visit the CirCut home page on the Web:
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
License as published by the Free Software Foundation.
---------
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
http://www.nmt.edu/~borchers/
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
http://www.nmt.edu/~borchers/
PACKAGE: OPT++
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:
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).
--
Department Head
High Performance Computing Research
Lawrence Berkeley National Laboratory
One Cyclotron Road, MS: 50B-2239
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
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
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.
For more information on SYMPHONY and to download the source code for
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