Optimization Softwares and Test Problems

Tomomi Matsui

Japanese version is here

---

When WWWcount does not work, please try the URL http://misojiro.misojiro.t.u-tokyo.ac.jp/~tomomi/opt-codeE.html .

---

• What's New
• Well-known Sites
• Useful Links
• Bibliography
• Problem Oriented Sites
  
  • Data Structure
  • Linear Programming
  • Nonlinear Programming
  • Satisfiability Problem
  • Mixed Integer Programming
  • Geometric Programming
  • Network Programming
  • Clique and Coloring Problem
  • Routing Problems (TSP,VRP)
  • Miscellaneous (Network Optimization)
  • Polytopes
  • Global Optimization
  • Quadratic Assignment Problem
  • Computational Geometry
  • Complementality Problem
  • Semidefinite Programming
  • Game Theory
  • Deta Envelopment Analysis
  • Stochastic Programming
  • Scheduling Problem
  • Timetabling Problem

---

---

Whats new!

• Continuous Global Optimization: An Introduction to Models, Solution Approaches, Tests and Applications. Appeared in ITORMS, 1999
• Continuous Global Optimization Software: A Brief Review.
• An Integrated Development Environment for Continuous Global Optimization
• LOG OPT is a leading provider of optimization software for business decision support systems, especially for logistics and supply chain management.

---

Well known sites

WORMS OR and Management Science

Home page of APORS1997

DIMACS (Center for Discrete Mathematics and Theoretical Computer Science)

The DIMACS Challenge

Challenge 1 : network flow, matching

Challenge 2 : clique, coloring, SAT

Challenge 3 : parallel algorithms

Challenge 4 :

DIMACS ftp site

elib (electric Library) in ZIB-BERLIN

Math-Web, Math-Net (ZIB-BERLIN)

Pointers to optimization softwares

MATHPROG & MP-TESTDATA

MATHPROG contains softwares. MP-TESTDATA is a set of test problems

OPT-NET (ftp) , OPT-NET in MATHPROG (ftp)

Directories 'algorithms','problems','software' contain some softwares.

You can get information from OPT-NET mailing list.

NEOS --> see OTC

NETLIB in AT&T Bell Laboratories Mathematical and Computing Sciences Research

NETLIB contains many softwares and test problems.

OR-LIBRARY in Imperial College Management School

OR-LIB contains many softwares and test problems.

OTC (Optimization Technology Center)

NEOS Guide

LP,NLP,Network Programming, Integer Programming, Global Optimization pages.

• Global Optimization page is very good!
• (Commercial) Optimization Software Guide
• In Case Study page, you can solve the Diet Problem.
• Portfolio Optimization is under construction.

NEOS Server

You can solve LP,NLP,Stochastic Programming, Network Programming problems. Solutions are sent by e-mail. Network programming page uses the well-known codes RELAX and NETFLO.

---

Useful Links

Decision Tree for Optimization Software (by Hans D. Mittelmann)

Links to public domain codes for LP/QP/NLP problems.

GAMS

Guide to Available Mathematical Software (Search Tool)

Heuristics for Discrete Optimization (Univ. of Trento)

Links to many heuristic codes.

JEA

Journal of Experimental Algorithmics

Jiefeng Xu's list

LIST OF INTERESTING OPTIMIZATION CODES in PUBLIC DOMAIN

Jiefeng Xu's page. It is exciting but too large for me.

Mathematics Softwares in Mathematics Information Servers

There are many pointers to mathematics softwares. The page also contains the list of universities and publishers in America.

Network Resources for OR

I like this page very much!!

INFORMS (OR Home Page)

Some links to softwares and search tool for papers.

OR subject Index

LP, NLP, muliti-objective programming. Combinatorial optimization page is here

Scheduling and Constrained Satisfaction Benchmark

College and Univ. Home pages in America.

Erdos Number Project Home Page contains the list of researchers with Erdos number 1 or 2.

---

Bibliography

• The Hypertext Bibliography Project contains the papers in proc. of STOC, FOCS.
• A Collection of Computer Science Bibliographies
• Computer Science Technical Reports in Japan
• Links to some technical report pages in Japan
• Stewart and Xu are trying to construct the list of algorithms for graph problems. (It's exciting.)

---

Problem Oriented Pages

Data Structure

• LEDA is a data structure library which contains red-black tree, F-heap, etc. You can get the research version.
• dyn_tree is a library of dynamic tree. (written in C)

Linear Programming

• Interactive Linear Programming System to solve and display linear programs over the web.
• LP FAQ
• Anima-LP is an educational LP software for Mac.
• lp_solve is a well-known LP code. (variables 30,000, constraints 50,000)
• minit.Z is a simplex code.
• LIPSOL is a interior point method. (Now it works without MATLAB.) There also exists a good manual.
• LOQO is a interior point method code in e-lib.
• HOPDM is a primal-dual logarithmic barrier method.
• Papers on Interior Point methods are in NETLIB FTP site , NEOS site .
• NEOS Server in OSL solves your LP problem. At Case Study page, you can solve your Diet Problem.
• Benchmark of diet problems
• METOR (LP based FIR filter design program) by Steiglitz.

Nonlinear Programming

• NLP FAQ contains many links to softwares and test problems.

Satisfiability problem

• DIMACS Challenge 2 : (see the directories 'contributed', 'benchmarks' of ftp site.
• POSIT is a software for SAT.

(Mixed) Integer Programming

• OPBDP & PLAM OPBDP (Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolean Optimization) is a 0-1 integer programming code. PLAM (Prolog and Modeling) is a modeling language.
• MIPlib is MIP library.
• MINT is MIP library (Nemhauser).

Geometric Programming

• XGP is a GP code.

Network Flow, Matching, Shortest Path, Spanning tree, etc.

• Bertsekas' site contains some FORTRAN codes. RELAX solves (nonlinear) minimum cost flow problem. AUCTION solves the assignment problem. There also exist some problem generators.
• DIMACS Challenge 1 : Softwares for minimum cost flow, maximum flow, matching problem.
  NETGEN is a well-known problem generator.
  
• NEOS Server You can solve Network Programming problems by well-known codes RELAX and NETFLO. Solutions are sent by e-mail.
• Goldberg's site contains softwares for min-cost flow, shortest path, max flow, assignment problem. There are good test reports.
• PPRN contains network problems with test reports.
• elib (electric Library) in ZIB-BERLIN
  • minimum cut problem
  • minimum mean cycle problem & parametric shortest path problem
  • matching problem ((non)bipartite,weighted,cardinality)
• MSTPAC in NETLIB solves minimum spanning tree problem.
• Eppstein's algorithm for K-shortest paths
• K shortest path problem (by Martin & Santos)
• LSNNO solves nonlinear network programming. Please see the ftp site in Bilkent University.

Clique and Coloring

• DIMACS Challenge 2 : clique, coloring
  • /pub/graph/solvers/ directory contains some basic tools.
  • /pub/graph/contributed/ contains come softwares. Morgenstern's program solves four color problems.
  • D.S.Johnson's programs for coloring problems.
• Michael Trick's graph coloring page
• Jensen and Toft's graph coloring page
• Culberson's graph coloring page
• Bibliography by (search engine) Glimpse
• Bibliography by (search engine) Waters
• Antonio Sassano's Page
• Carlo Mannino's Page

Routing Problems (TSP,VRP)

• LOG OPT is a leading provider of optimization software for business decision support systems, especially for logistics and supply chain management.
• TSPBIB Listing of papers and source codes for the Traveling Salesman Problem.
• TSPLIB is one of the most famous site!
• TSP algorithms by Lionnel Magis.
• HC in NETLIB finds one or more Hamilton cycles.
• Solomon Instances of VRP
• VRP datasets from e-LIB
• VRP page from droopy.imag.fr (See INSTANCES and BIBLIOGRAPHY)
• Deadline data sets by Sam Tangiah
• Vehicle Routing Home Page by Tim Duncan
• Eric Taillard's Home Page contains some test problems.
• Single Depo Problem data set by Andreas Reinholz. Visualization is very clear.
• VRP research group in University of Koeln
• Split Delivery Arc Routing page by Paul Abraham Mullaseril

Miscellaneous (Network Optimization)

• LOLIB Linear Ordering Problem Library.
• METIS is Graph Partitioning Problem Software

Polytope

• PORTA

Global Optimization

• Continuous Global Optimization: An Introduction to Models, Solution Approaches, Tests and Applications. Appeared in ITORMS, 1999
• Continuous Global Optimization Software: A Brief Review.
• An Integrated Development Environment for Continuous Global Optimization
• non-convex nonlinear programming using SDP by Baoyan and Ding
• Streltsov's page
• Neumaier's page
• NEOS Guide, Global Optimization
• BARON (Branch-and-Reduce Optimization Navigator)
• Test problems of reverse convex programming, concave minimization
• Journal of Global Optimization at ZIB-BERLIN

Quadratic Assignment Problem

• H.Wolkowicz's QAP Page
• QAPLIB
• Eric Taillard's Home Page contains some test problems.

Computational Geometry

• Korean VLSI and CAD Newsletter
• Geometric Software by K.Sugihara
• Line segment Voronoi by T.Imai
• Carleton's CG page
• Erickson's CG page ; Interactive Demo (written in JAVA) is interesting.
• Eppstein's CG page
• Amenta's CG page

Complementarity Problem

• Complementarity Problem Net

Semidefinite Programming

• Home page for semidefinite programming by Christoph Helmberg
• H.Wolkowicz' Home page
• SDPSOL is a software by Boyd and Vandenberghe
• SDP Home Page in Waterloo
• Alizadeh's SDP Home Page
• SDPA is a software by Kojima and Fujisawa

Game Theory

• Games and Diversions (Zero-sum game solver, On-line forecaster, The cooperative learning game. ) by David K. Levine
• GAMBIT (programs for analyzing games)
• Martin J. Osborne
• M. Kandori
• A. Matsui
• H. Takizawa
• Ken Binmore
• Tilman Borgers
• Irinel Dragan
• Chaim Fershtman
• Peter Fishburn
• Drew Fudenberg
• Raimo P. Hamalainen
• Sergiu Hart
• Kjell Hausken
• David Levine
• Daniel E. Loeb
• Interuniversity Centre for Game Theory and Applications
• group of Bachem and Schrader publications
• T. Watanabe
• Y. Funaki
• Eppstein's Combinatorial Game Theory page
• Loeb's Combinatorial Game Theory page
• Ratliff's game theory page
• Al Roth's game theory page (including two-sided matching)
• Prisoner's Dilemma ; interactive demo.

Deta Envelopment Analysis

• Ali Emrouznejad's DEA(Data Envelopment Analysis) Home page
• Anderson's DEA page
• Ali Emrouznejad's DEA page
• DEA page in OR-LIBRARY

Stochastic Programming

• NEOS Server ; You can solve Stochastic Programming problems. Solutions are sent by e-mail.
• Stochastic Programming Home Page

Scheduling

• akraemer_MPM in OPT-NET (ftp) solves job-shop scheduling problem.
• Eric Taillard's Home Page contains some test problems of Flow shop, Job shop, Open shop scheduling.
• Tools for Logistics Problem Solving ,
• Akamatsu's traffic network library
• CASTLE lab in Princeton Univ. Dept. of Eng. and OR
• Logistics Engineering Center (LEC)

Time tabling problem

• Timetabling Research , Machine Intelligence Group, Department of Computer Science, University of Nottingham, UK
• Evolutionary Timetabling, Department of Artificial Intelligence, University of Edinburgh, UK
• KnowTIS, Artificial Intelligence Division, School of Computer Studies, University of Leeds, UK
• Data archive at University of Toronto (Canada)
• Data archive at University of Nottingham
• TTP Timetabling mailing list
• Comprehensive bibliography (in BibTeX)
• Bibliographies in Nottingham
• NEC software 'School Magic'; You can get the research version.
• Software CALT in DEC Japan

---

Tomomi Matsui HP

---