Operations Research Softwares

Software

For some codes a benchmark on problems from SDPLIB is available at Arizona State University.

• BiqCrunch, by N. Krislock, J. Malick, and F. Roupin.
  A semidefinite branch-and-bound method for solving binary quadratic problems (online platform).
• Biq Mac Solver, by F. Rendl, G. Rinaldi, and A. Wiegele.
  An online platform for solving unconstrained binary quadratic programs and computing a maximum cut of edge-weighted graphs.
• CSDP 4.9, by Brian Borchers (report 1998, report 2001). He also maintains a problem library, SDPLIB.
• CVX, version 1.1, by M. Grant and S. Boyd.
  Matlab software for disciplined convex programming.
• DSDP 5.6 , by S. J. Benson and Y. Ye, parallel dual-scaling interior point code in C (manual); source and excutables available from Benson's homepages.
• GloptiPoly3, by D. Henrion, J.-B. Lasserre and J. Loefberg;
  a Matlab/SeDuMi add-on for LMI-relaxations of minimization problems over multivariable polynomial functions subject to polynomial or integer constraints.
• LMITOOL-2.0 of the Optimization and Control Group at ENSTA.
• MAXDET, by Shao-po Wu, L. Vandenberghe, and S. Boyd. Software for determinant maximization. (see also rmd)
• NCSOStools, by K. Cafuta, I. Klep, and J. Povh. An open source Matlab toolbox for symbolic computation with polynomials in noncommuting variables, to be used in combination with sdp solvers.
• PENNON-1.1 by M. Kocvara and M. Stingl. It implements a penalty method for (large-scale, sparse) nonlinear and semidefinite programming (see their report), and is based on the PBM method of Ben-Tal and Zibulevsky.
• PENSDP v2.0 and PENBMI v2.0, by TOMLAB Optimization Inc., a MATLAB interface for PENNON.
• rmd , by the Geometry of Lattices and Algorithms group at University of Magdeburg, for making solutions of MAXDET rigorous by approximating primal and dual solution by rationals and testing for feasibility.
• SBmethod (Version 1.1.3), by C. Helmberg. A C++ implementation of the spectral bundle method for eigenvalue optimization.
• SDLS by D. Henrion and J. Malick.
  Matlab package for solving least-squares problems over convex symmetric cones.
• SDPA (version 7.1.2), initiated by the group around Masakazu Kojima.
• SDPHA does not seem to be available any more (it was package by F. A. Potra, R. Sheng, and N. Brixius for use with MATLAB).
• SDPLR (version 1.02, May 2005) by Sam Burer, a C package for solving large-scale semidefinite programming problems.
• SDPpack is no longer supported, but still available. Version 0.9 BETA, by F. Alizadeh, J.-P. Haeberly, M. V. Nayakkankuppam, M. L. Overton, and S. Schmieta, for use with MATLAB.
• SDPSOL (version beta), by Shao-po Wu & Stephen Boyd (May 20, 1996). A parser/solver for SDP and MAXDET problems with matrix structure.
• SDP_S, a stand alone tool to formulate and solve semidefinite relaxations for 0-1 quadratic problems by F. Roupin (March 1, 2010).
• SDPT3 (version 4.0), high quality MATLAB package by K.C. Toh, M.J. Todd, and R.H. Tütüncü. See the optimization online reference.
• SeDuMi, a high quality package with MATLAB interface for solving optimization problems over self-dual homogeneous cones started by Jos F. Sturm.
  Now also available: SeDuMi Interface 1.04 by Dimitri Peaucelle.
• SOSTOOLS, by S. Prajna, A. Papachristodoulou, and P. A. Parrilo. A SEDUMI based MATLAB toolbox for formulating and solving sums of squares (SOS) optimization programs(also available at Caltech).
• SP is no longer available (it was a software package for semidefinite programming by L. Vandenberghe, Stephen Boyd, and Brien Alkire).
• SparseCoLO, by the group of M. Kojima, a matlab package for conversion methods for LMIs having sparse chordal graph structure, see the Research report B-453.
• SparsePOP, by H. Waki, S. Kim, M. Kojima and M. Muramatsu, is a MATLAB implementation of a sparse semidefinite programming relaxation method proposed for polynomial optimization problems.
• VSDP: Verified SemiDefinite Programmin, by Christian Jansson. MATLAB software package for computing verified results of semidefinite programming problems. See the optimization online reference.
• YALMIP, free MATLAB Toolbox by J. Löfberg for rapid optmization modeling with support for, e.g., conic programming, integer programming, bilinear optmization, moment optmization and sum of squares. Interfaces about 20 solvers, including most modern SDP solvers.

Reports on software:

• M. Yamashita, K. Fujisawa, M. Fukuda, K. Nakata and M. Nakata.
  "Parallel solver for semidefinite programming problem having sparse Schur complement matrix",
  Research Report B-463, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, September 2010.
  opt-online
• Hans D. Mittelmann.
  "The state-of-the-art in conic optimization software",
  Arizona State University, August 2010, written for the "Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications".
  opt-online
• K.-C. Toh, M. J. Todd, and R. H. Tütüncü.
  "On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0",
  Preprint, National University of Singapore, June, 2010.
  opt-online
• K. Cafuta, I. Klep and J. Povh.
  "NCSOSTOOLS: A Computer Algebra System for Symbolic and Numerical Computation with Noncommutative Polynomials",
  University of Ljubljana, Faculty of Mathematics and Physics, Slovenia, May 2010.
  opt-online
• I. D. Ivanov and E. De Klerk.
  "Parallel implementation of a semidefinite programming solver based on CSDP on a distributed memory cluster",
  Optimization Methods and Software, Volume 25, Issue 3 June 2010 , pages 405 - 420 .
  OMS
• M. Yamashita, K. Fujisawa, K. Nakata, M. Nakata, M. Fukuda, K. Kobayashi and Kazushige Goto.
  "A high-performance software package for semidefinite programs: SDPA 7",
  Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, January, 2010.
  opt-online
• Sunyoung Kim, Masakazu Kojima, Hayato Waki and Makoto Yamashita.
  "SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems",
  Report B-457, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, July 2009.
  opt-online
• K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto and M. Yamashita.
  "ser's Manual for SparseCoLO: Conversion Methods for Sparse Conic-form Linear Optimization Problems",
  Research report B-453, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan, February 2009.
  opt-online
• Sunyoung Kim, Masakazu Kojima, Martin Mevissen, Makoto Yamashita.
  "Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion",
  Research Report B-452, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan, November 2008.
  opt-online
• D. Henrion, J. B. Lasserre, and J. Löfberg.
  "GloptiPoly 3: moments, optimization and semidefinite programming",
  LAAS-CNRS, University of Toulouse, 2007.
  opt-online
• Didier Henrion and Jérôme Malick.
  "SDLS: a Matlab package for solving conic least-squares problems",
  LAAS-CNRS, University of Toulouse, 2007.
  opt-online
• M. Grant and S. Boyd.
  "Graph Implementations for Nonsmooth Convex Programs",
  Stanford University, 2007.
  opt-online
• K. K. Sivaramakrishnan.
  "A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs",
  Technical Report, Department of Mathematics, North Carolina State University, Raleigh, NC, 27695, December 2006. Revised in June 2007 and August 2007.
  opt-online
• Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuhide Nakata.
  "Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs",
  Research Report B-415, Tokyo Institute of Technology, 2-12-1, Oh-okayama, Meguro-ku, Tokyo, Japan, March 2005.
  opt-online
• B. Borchers and J. Young.
  "How Far Can We Go With Primal-Dual Interior Point Methods for SDP?",
  New Mexico Tech, February 2005.
  opt-online
• H. Waki, S. Kim, M. Kojima and M. Muramatsu.
  "SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems",
  Research Report B-414, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro 152-8552, Tokyo, Japan, March 2005.
  opt-online
• M. Kocvara and M. Stingl.
  "PENNON: A code for convex nonlinear and semidefinite programming",
  Optimization Methods and Software (OMS), Volume 18, Number 3, 317-333, June 2003.
  
• Brian Borchers.
  "CSDP 4.0 User's Guide",
  user's guide, New Mexico Tech, Socorro, NM 87801, 2002.
  opt-online
• M. Yamashita, K. Fujisawa, and M. Kojima.
  "SDPARA : SemiDefinite Programming Algorithm PARAllel Version",
  Parallel Computing Vol.29 (8) 1053-1067 (2003).
  opt-online
• J. Sturm.
  "Implementation of Interior Point Methods for Mixed Semidefinite and Second Order Cone Optimization Problems",
  Optimization Methods and Software, Volume 17, Number 6, 1105-1154, December 2002.
  optimization-online
• S. Benson and Y. Ye.
  "DSDP4 Software User Guide",
  ANL/MCS-TM-248; Mathematics and Computer Science Division; Argonne National Laboratory; Argonne, IL; March 2002.
  opt-online
• S. Benson.
  "Parallel Computing on Semidefinite Programs",
  Preprint ANL/MCS-P939-0302; Mathematics and Computer Science Division Argonne National Laboratory 9700 S. Cass Avenue Argonne, IL, 60439; March 2002.
  opt-online
• D. Henrion and J. B. Lasserre.
  "GloptiPoly - Global Optimization over Polynomials with Matlab and SeDuMi",
  LAAS-CNRS Research Report, February 2002.
  opt-online
• M. Kocvara and M. Stingl.
  "PENNON - A Generalized Augmented Lagrangian Method for Semidefinite Programming",
  Research Report 286, Institute of Applied Mathematics, University of Erlangen, 2001.
  opt-online
• D. Peaucelle, D. Henrion, and Y. Labit.
  "User's Guide for SeDuMi Interface 1.01", Technical report number 01445 LAAS-CNRS : 7 av. du Colonel Roche, 31077 Toulouse Cedex 4, FRANCE November 2001.
  opt-online
• Jos F. Sturm.
  "Using SEDUMI 1.02, a MATLAB Toolbox for Optimization Over Symmetric Cones (Updated for Version 1.05)",
  October 2001.
  opt-online
• Hans D. Mittelmann.
  "An Independent Benchmarking of SDP and SOCP Solvers",
  Technical Report, Dept. of Mathematics, Arizona State University, July 2001.
  opt-online
• K. Fujisawa, M. Fukuda, M. Kojima and K. Nakata.
  "Numerical Evaluation of SDPA",
  Research Report B-330, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152, September 1997.
  ps.Z-file (ftp) or dvi.Z-file (ftp)
• L. Mosheyev and M. Zibulevsky.
  "Penalty/Barrier Multiplier Algorithm for Semidefinite Programming: Dual Bounds and Implementation",
  Research Report #1/96, Optimization Laboratory, Technion, November 1996.
  ps-file (http)

Due to several requests I have asked G. Rinaldi for permission to put his graph generator on this page. Here it is: rudy (tar.gz-file)

---

Last modified: Thu Sep 8 18:02:50 CEST 2011