Optimization Software & Theory Software (MATLAB codes), papers, and background, related to the research of Henry Wolkowicz is available in fortran and/or matlab, e.g. for Semidefinite Programming (see e.g. Handbook on SDP.) In each directory there should be a readme file as well as a tar file containing all the files and subdirectories. Also available are various locations for theoretical background. ( a short publication list) Mathtools.net>MATLAB>Optimization)

of further interest::
• UW-IBM Facility for Scientific and Deep Computing, Information Systems and Technology for IBM RS6000 SP.
• Guide to Optimization Software, based on expanded and updated version of More-Wright book.
• GSL -- The GNU Scientific Library.
• A guide to available mathematical software elsewhere. Also HotGams A Java(tm) powered frontend to the NIST Guide to Available Mathematical Software.
• local (UofW) software information
• Published SPEC results in tabular form.
• FAQ (frequently asked questions) for linear programming
• FAQ (frequently asked questions) on nonlinear programming;
• Math Programming Glossary, from Harvey Greenberg, Denver
• bibliography on sensitivity analysis, and other links to bibliographies, by Hossein Arsham.
• the MATLAB site. A personal collection of miscellaneous information on matlab.

Combinatorial Optimization

• Graph Partitioning
• Max-Cut
• Semidefinite Programming
• Quadratic Assignment Problem
• Set Partitioning
• List of Related References

Graph Partitioning

A Projection Technique for Graph Bisection; a fortran program that finds both a good equipartition of a given graph and a bound of the optimum value of this partition. This is based on a computational based research report published in Mathematical Programming, 1994. A related theoretical paper, published in Annals of Operations Research, 1993 is also available.
A semidefinite programming relaxation paper presents improved bounds.

Max-Cut

The Research Report Simple Efficient Solutions for Semidefinite Programming describes an algorithm that can be applied to solve the SDP relaxation of the maxcut problem. Numerical tests were done using MATLAB 6 with the files in this directory. Also available: a ps file with the latest numerical test

(PLEASE NOTE that these are matlab files. They do not include mex files. Therefore the speed is misleading when compared to other packages that are written in compiled languages. In addition, these files are under constant improvement. The cputimes are significantly better than those reported in the above cited Research Report.)
The algorithm is based on an inexact Gauss-Newton (GN) method using preconditioned conjugated gradients (PCG) to solve the least squares problem. Important features: q-quadratic convergence and high accuracy.
(We use the PCG type algorithm LSQR written (in MATLAB) by Michael Saunders and available on his web page.)

Available from Hans Mittlemann: bench marks for two problems from SDPLIB (mcp250-1, mcp500-1), for 7 other packages, i.e. the relevant numbers are (cputime and sign. digits)

 problem    CSDP  s   SDPA  s   SDPHA  s  SDPT3 s    SP   s  SeDuMi s SDPpack s
===============================================================================
 mcp250-1     26  7     44  7    1758  7    39  7   1796  5    104  7 6447    7
 mcp500-1    171  7    492  7   39585  7   361  7         a   1212  7 144376  7

Further details about the problems are available from SDPLIB. See also Gset, a group of graph problems from Yinyu Ye. ( from Brian Borchers web page).

Semidefinite Programming ( NOTATION; Search Results at simplifynet. )
Bibliography, Eigenvalues, Sdp Homepages, SDP Solvers, Test Problems,

Semidefinite programs are linear programs where the nonnegativity constraint is replaced by a positive semidefinite constraint on matrix variables. Semidefinite programs arise in many applications, e.g., combinatorial optimization, control theory, statistics, and nonlinear programming. In particular, semidefinite programs arise from Lagrangian relaxations of quadratic approximations; thus they provide improvements over linear approximations. (And "the world is not linear".)

Following are a list of related sites as well as descriptions of locally available related papers. (Please send me your comments and/or related papers to add to the bibliography.)

Bibliography Information

• An annotated bibliography (hyperref) pdf file (with latest entries and abstracts) A gzipped bib file with related papers.
• Bibliography on Semidefinite Programming, a searchable bib collection from :The Collection of Computer Science Bibliographies --> Subject area: Bibliographies on Mathematics.
• Several of my papers related to semidefinite programming are available through the abstracts file.

Eigenvalue Optimization and SDP

• Mike Overton's home page

Home Pages for SDP

The special home page for semidefinite programming, organized by Christoph Helmberg, Professor of Algorithmic and Discrete Mathematics, Chemnitz University of Technology, Department of Mathematics, D-09107 Chemnitz, Germany.
• A special home page for semidefinite programming, organized by Farid Alizadeh at Rutgers University.

Lecture Notes on SDP

• Also available is information on several projects that use the SDPSOL toolbox: project on graph partitioning using SDP by Bo Yu; project on nonconvex nonlinear programming using SDP by Baoyan Ding. These projects were for a course on SDP.

SDP Solvers

NAME	TYPE	AUTHORS
CSDP	C	B. Borchers
DSDP	C	Steve Benson, Yinyu Ye
MAXDET	Matlab,MEX	Lieven Vandenberghe, Stephen P. Boyd.
PENNON	AMPL	MICHAL KOCVARA, originally PBM method of Ben-Tal and Zibulevsky.
SeDuMi 1.1+	Matlab,MEX	Jos F. Sturm, but now at Advanced Optimization Laboratory, at McMaster University, Canada
SeDuMi 1.05	Matlab,MEX	Jos F. Sturm
SDPA	C++	K. Fujisawa, M. Kojima, K. Nakata
SBmethod	C++	Christoph Helmberg
SDPpack	Matlab,MEX	F. Alizadeh, J-P A. Haeberly, M. V. Nayakkankuppam, M. L. Overton, S. Schmieta
SDPT3	Matlab,MEX	K.C. Toh, M.J. Todd, R.H. Tutuncu
SIMPLE	Matlab	by Henry Wolkowicz; solves the SDP relaxation of Max-Cut
SP	Matlab,MEX	L. Vandenberghe, S. Boyd

• lmitool-2.0 : An Interface to Solve LMI Problems, uses 3 possible optimization packages.
• YALMIP (Yet another LMI parser), YALMIP serves as an interface to a number of solvers. Johan Lvfberg, M. Sc. (johanl@isy.liu.se), Division of Automatic Control, Department of Electrical Engineering, Linkvping University.
• Semidefinite Programming, contains (locally) a toolbox with matlab programs for semidefinite programming.
• A package is available from Boyd and Vandenberghe. SDPSOL is available via anonymous ftp to isl.stanford.edu in /pub/boyd/semidef_prog/sdpsol. More information on the package, is available at nanet.
• version 1.0 of "CUTSDP with user manual. 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.

Test Problems

• Generating Hard Instances of SDP: The two MATLAB files: (i) rungenHard.m (which uses writesdpa.m from CSDP webpage to get both SeDuMi format and .dat-s format), and (ii) genHardSDP.m, generate hard instances of SDP. These are SDP problems where strict complementarity fails. This gzipped tar file contains the MATLAB mat files with the test problems gap0 to gap24 used in the research report genhardsdp.pdf, where the details for the problem generation are provided. (authors: Hua Wei and Henry Wolkowicz.)
• SDPLIB Test Problems (on SDP), from Brian Borchers and a large collection with benchmarks from Hans Mittlemann.

Workshops and Conferences on SDP

• workshop at the Fields Institute, on Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems, Toronto, Ontario, May 15-17, 1996.
  There are two volumes of proceedings, New Approaches to Hard Discrete Optimization, volume 6 #3 in J. Comb. Opt. Kluwer Academic Publishers, Hingham, MA, 2002;
  and Novel Approaches to Hard Discrete Optimization, The Fields Institute for Research in Mathematical Sciences, Communications Series, Providence, RI, 2003. American Mathematical Society,
  see e.g. bib data.
• Novel Approaches to Hard Discrete Optimization, April 2001 Workshop at Univ. of Waterloo.
• Large Scale Nonlinear and Semidefinite Programming Workshop, Wednesday, May 12 to Saturday, May 15, 2004 at University of Waterloo; and Call for Papers Special Issue MP

Further Notes and Papers Available:

• Semidefinite Programming Bibliography/Comments, organized by Henry Wolkowicz
• Matrix Inequalities in Science and Engineering, organized at Math Dept, College of William and Mary.
• long list of related references found using MathSearch
• primal-dual algorithms from Monteiro;
• Interior-Point Archive, papers;
• Game Theory Resources on the Net

Quadratic Assignment Problem

The QAP is an NP hard problem where even moderate sizes (n=16) can be very hard to solve. The problem is an extension of the linear assignment problem where the objective function can be quadratic. See e.g. the OTC guide with examples and mathematical formulation.
• Quadratic Assignment Problem, contains the fortran code of Burkard-Derigs;
• A paper which provides an SDP relaxation for QAP is available. Also available: Semidefinite Programming Relaxations for Paritioning and Assignment Problems, the PhD Thesis of Qing Zhao.
• Other workers in this area: Grant Telfar from New Zealand; Stefan Karisch (and Franz Rendl) from Austria (has a database of problems); Panos Pardalos has solved QAP's of size n=20 in collaboration with Mauricio G.C. Resende from AT&T Bell Laboratories Computing Science Research Center. A paper of theirs with Z. Drezner solves instances up to n=20. Test problems for QAP and other hard combinatorial problems can be obtained by e-mail to o.rlibrary@ic.ac.uk (send message info). also see People Working on QAP, maintained at QAPLIB - A Quadratic Assignment Problem Library Which is maintained by Stefen Karisch
• A long list of URLS on SDP (and QAP and SQP)

Set Partitioning

The model is: minimize cost cx
s.t. Ax=1 , x is 0,1,
and c,A are given 0,1 matrices.
The best know application is to airline crew scheduling. A set of flight legs (between cities) are given that must be flown; each constraint (row) represents a flight leg. Feasible trips (i.e. a sequence of flight legs) for crews need to be chosen (columns of constraint matrix). A local paper which provides an SDP relaxation for SP is available. Also:
• J.E. Beasley home page section or alternate address also OR-library, a collection of test data for a variety of problems. (including:
  Assignment problem; Bin packing; Capacitated minimal spanning tree; Crew scheduling; Data envelopment analysis; Frequency assignment problem; Generalised assignment problem; Graph colouring; Integer programming; Linear programming; Location:; capacitated warehouse location; p-hub; p-median - uncapacitated; p-median - capacitated; uncapacitated warehouse location; Matching; Maximum clique; Min-cut clustering; Multiple knapsack problem; Network flow; Quadratic assignment problem; Resource constrained shortest path; Scheduling:; aircraft landing; flow shop; job shop; open shop; Set covering; Set partitioning; Steiner:; Euclidean Steiner problem; ectilinear Steiner problem; Steiner problem in graphs; Stochastic linear programming; Three-dimensional packing; Time series forecasting; Tinetabling; Travelling salesman:; period salesman; single period; Two-dimensional cutting: ; assortment problem; constrained guillotine; constrained non-guillotine; unconstrained guillotine; Vehicle routing: ; fixed areas; fixed routes; multiple depot; period routing; single period; sparse feasibility graph;
• Avishai Wool home page section

List of Related References in Combinatorial Optimization

• IFIP Working Group 7.4 on Discrete Optimization
• Projects in Combinatorial Optimization at ZIB, Berlin, includes integer programming, SDP, graph problems, ...
• A href="ftp://ftp.nmt.edu/pub/nmt/papers/borchers/readings.ps"> reading list, by Brian Borchers.
• Report Series of the Optimization Group at the TU Graz
• combinatorics bibliography
• JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, new electronic journal.
• MIPLIB collection of discrete optimization instances by Bob Bixby.
• combinatorics reading list from Brian Borchers.
• a good collection of info/links related to vehicle routing
• a gallery of fake pictures of combinatorics people
• Sparse Matrix Ordering and Graph Partitioning Software; Anshul Gupta , WGPP: Watson Graph Partitioning (and sparse matrix ordering) Package.
• Electronic Colloquium on Computational Complexity, with Research reports, surveys and books in computational complexity

Matrix Approximation Problems Using SDP

• A list of researchers and home pages in matrix theory and related areas:
  • A bib file with reference on AC and EDM and SDP in general.
  • Alan Edelman, MIT, (Grassman manifolds, Kronecker form, matrix pencils)
  • Volker Mehrmann,, Technische Universitat, Berlin, (completion problems, control theory, matrix pencils).
  • G.W. (Pete) Stewart, at University of Maryland, (numerical analysis!!)
  • Global Optimization Algorithms for Macromolecular Modeling, Jorge Moré and Zhijun Wu.
  • Clark Wells, working on molecular conformation problems.

Linear Programming

• Linear Programming, contains matlab programs for linear programming, including a well tested simplex method routine and several examples.
• PCx, interior point codes for various platforms from Stephen Wright et al (at Argonne).
• FAQ (frequently asked questions) for linear programming
• A comparison of simplex algorithms complete with Matlab scripts, thesis by Steven Morgan at Univ. of Florida, 1997.

Nonlinear Programming

Unconstrained Nonlinear Programming

Two popular methods for unconstrained minimization are: trust region methods and quasi-Newton methods.
• Trust Region Subproblems consist in minimizing a quadratic function subject to a quadratic constraint. The directory contains programs for solving the trust region subproblem. This routine is in matlab. It uses the matlab eigs function, i.e. it finds the smallest eigenvalue using the Lanczos algorithm. This program can solve large sparse problems very quickly. The related research report is available. Also available are two related research reports:
  • indefinite trust region subproblems provide characterizations of optimality and relations to perturbed eigenvalue problems for the case where both the objective and constraint can be indefinite;
  • nonsymmetric eigenvalue perturbations provides relationships between trust region subproblems and eigenvalue perturbations.
• Quasi-Newton Methods or Least Change Secant Methods are based on approximating the Hessian using gradient information. The following three papers deal with measures for finding best Hessian approximations:
  • Sizing and Least Change Secant Methods;
  • MEASURES FOR SYMMETRIC RANK-ONE UPDATES
  • AN ALL INCLUSIVE EFFICIENT REGION OF UPDATES FOR LEAST CHANGE SECANT METHODS
  • Also available Measures for Least Change Secant Methods, Master's thesis of Qing Zhao.
  • Bibliography for Optimization with Sensitivity Analysis, long list of links related to sensitivity analysis.

Constrained Nonlinear Programming

• Work on SQP methods is in progress - more forthcoming ....
  Semidefinite Programming Applied to Nonlinear Programming Master's Thesis by Serge Kruk, a preliminary to an SQQP algorithm, and a Research Report on an SQQP algorithm.

• A list of home pages in nonlinear programming and related areas:
  • COPS, Large-Scale Nonlinearly Constrained Optimization Problems; for developing test problems.
  • HQP Optimization service, provides java interface for solving NLPs by e.g. SQP. (includes large scale capability); also available is The FSQP home page
  • A reading course on nonlinear programming was held during fall/95, in C & O at UofW. We read the book on Nonlinear Programming by Dimitri P. Bertsekas.
  • FAQ (frequently asked questions) on nonlinear programming;
  • Convex Analysis with Eng Appl. method, notes from a course given by Steven Boyd at Stanford University.
  • Newton-Raphson method online lessons at the University of Utah.
  • CUTE, test problems and testing package;
  • ADIFOR: Automatic Differentiation of Fortran Codes. ADIFOR is a tool for the automatic differentiation of Fortran 77 programs.
  • More sites on Optimization.

Regularization

• Two Master's Theses:
  • Trust Region Subproblems and Linear Least-Squares Regularization,
    by Mike Froh, University of Waterloo.
  • Regularization Using a Parameterized Trust Region Subproblem
    by Oleg Grodzevich, University of Waterloo.
• a directory with the MATLAB software for the regularization from the above thesis of Oleg Grodzevich. (See e.g. the demo file - but you will need the Hanson package for this demo file, see below.) The dll files are available for windows MATLAB.
• A list of home pages in Regularization and related areas:
  • Informatics and mathematical modelling at Technical University of Denmark Contains MOORE TOOLS, an object oriented toolbox for Matlab, and Regularization Tools, the MATLAB package by Prof Per Christian Hansen.



Home Page

, by Henry Wolkowicz

---

splines Directory on Orion