The Online Solver for the Shortest Path Problem

The Online Solver for the Shortest Path Problem is now pre-opened.

1: Access the following web page using the FireFox, Opera, Safari, IE and so on.
http://opt.indsys.chuo-u.ac.jp/portal/

2: Change the resolution of the picture and/or the graph file via the pull-down menu. After that push the "Change" button.

3: Input the coordinates or click on the map for specifying the starting point and the destination.

4: Push the "Submit" button and the server starts the program.

SDPA 7.1.1 now available!! : 06/18/2008

We release the new version of SDPA (7.1.1) from the SDPA homepage.

sdpa.7.1.1.src.tar.gz
SDPA source file for Linux/Unix.
See the user's manual below.

sdpa.7.1.1.manual.pdf
SDPA installation manual for Linux/Unix.

The SDPA-GMP is released!! 04/10/2008

The SDPA-GMP is an SDP solver based on the SDPA, which is intended to obtain highly accurate solutions by utilizing arbitrary precision arithmetic in the GNU Multiple Precision Arithmetic Library (GMP). The current version of the SDPA-GMP shares the same features with the SDPA except for user settable accuracy usually for extraordinary accurate calculations. Expect for newly added one parameters ``precision'', user experience is the same as the SDPA. Note that the SDPA-GMP is typically several ten or hundred times slower than the SDPA.

http://sdpa.indsys.chuo-u.ac.jp/sdpa/download.html#sdpa-gmp

SDPA 7.1.0 now available!! : 03/29/2008

We release the new version of SDPA (7.1.0) from the SDPA homepage.

sdpa.7.1.0.src.tar.gz
SDPA source file for Linux/Unix.
See the user's manual below.

sdpa.7.1.0.manual.pdf
SDPA installation manual for Linux/Unix.

Benchmarking results : 02/27/2008

The new versions of optimized BLAS libraries have recently released:

1: GotoBLAS 1.24
2: Intel MKL 10.0.2.018
3: ATLAS 3.8.1

The new Intel processors code-named Penryn have released in 1Q 2008.
New enhancements in Penryn are:

1: 50% larger L2 Cache and Reduction in Bank-Conflict Penalties
2: Super Shuffle Engine and Fast Radix-16 Divider
3: Enhanced Cache Line Split Load
4: Deep Power Down Technology
5: Enhanced Intel Dynamic Acceleration Technology

Intel's new 45nm penryn-based Core 2 Duo (E8200) outperforms the previous 65nm Core 2 Duo with a same clock rate from our numerical results. The improvement when using non-optimized BLAS (BLAS/LAPACK 3.1.1) stands out from the others. The above 1, 2 and 3 enhancements probably works well for non-optimized software.

SDPA 7.0.5 now available!! : 02/16/2008

We release the new version of SDPA (7.0.5) from the SDPA homepage.

sdpa.7.0.5.src.tar.gz
SDPA source file for Linux/Unix.
See the user's manual below.

sdpa.7.0.5.manual.pdf
SDPA installation manual for Linux/Unix.

Benchmarking results : 02/12/2008

We have performed numerical experiments among SDPA(6.2.1, 7.0.5 and 7.1beta) and SDPARA(7.0beta). All software packages are linked against optimized BLAS(GotoBLAS 1.23). Note that SDPA 7.1beta and SDPARA 7.0beta are under development and we have not yet given our decision on when we release them. Through numerical results, we observe some features of each software package as follows:
1: For small SDPs, the SDPAs outperform the SDPARA.
2: If he Schur Complement Matrix (SCM) becomes sparse(ex. Prob(2)), the SDPA 7.0.5 and 7.1beta are much faster than the SDPA 6.2.1.

SDPA 7.0.5 coming soon!! : 02/08/2008

We'll soon release the next version of SDPA (7.0.5) from the SDPA homepage. One of the significant features of this version of the SDPA is that it solves semidefinite programming problems much faster than the previous version of the SDPA without losing its excellent numerical stability.
It utilizes sparse Cholesky factorization for the Schur matrix when the Schur matrix is sparse. In order to obtain an ordering which possibly produces lesser fill-in, the minimum degree ordering in SPOOLES is applied.

We strongly recommend you to use optimized BLAS and LAPACK, e.g.,

1: GotoBLAS:
2: Automatically Tuned Linear Algebra Software (ATLAS):
3: Intel Math Kernel Library (MKL):

Table 1 shows how the SDPA 7.0.5 performs on several benchmark problems when changing the BLAS and LAPACK library. Typically, the SDPA 7.0.5 with optimized BLAS and LAPACK seems much faster than one with BLAS/LAPACK 3.1.1. And furthermore, we can receive benefits of multi-thread computing when using SMP and/or multi-core machines.

Current Works of SDPA Project

We provide several software packages for users in optimization areas. There is still plenty of rooms for improvements for the software packages of the SDPA Family. We show some future works on the SDPA project.

1: For extremely sparse problems:
Note that the Schur Complement Matrix (SCM) is fully dense in general even if data matrices are sparse. However, we found that the SCM often became sparse when we solve extremely sparse problems arising from the polynomial optimization. We need to modify the data structure for the sparse SCM, and employ the sparse Cholesky factorization.

2: For good numerical stability:
We may adopt the arbitrary precision arithmetic when the condition numbers of some matrices at any iterate become ill-conditioned. We replace some double type variables in source codes of SDPA, LAPACK and BLAS with variables with arbitrary precision defined by the GMP which is a free library for arbitrary precision arithmetic and floating point numbers. We also consider the iterative refinement method for the residual which is a free library for arbitrary precision arithmetic and floating point numbers.We also consider the iterative refinement method for the residual correction of linear equations.

3: Accelerated by optimized BLAS
In the latest version of the SDPA 7.x, we also utilizes the GotoBLAS library for computing the matrix-matrix and matrix-vector multiplication, Cholesky factorization of the matrix and so on. The GotoBLAS supports the multi-thread computing on multi-core processor. We have confirmed that it dramatically accelerates the SDPA 7.x on the quad-core processor.

Reseach Project 1: SDPA

The SDPA (SemiDefinite Programming Algorithm) is a C++ implementation of a Mehrotra-type primal-dual predictor-corrector interior-point method(PDIPM) for solving the standard form SDP and its dual.
The main objective of the SDPA Project started in 1995 is to implement the PDIPM for SDPs and to solve large-scale SDPs with various characteristics, e.g., sparsity, large number of constraints and so on.

More detailed information of the SDPA Family(SDPA, SDPARA, SDPARA-C, SDPA-C) is available at the SDPA Web site:
All software packages of the SDPA Family are also available from the above Web site.