最適化ソフトウェアとテスト問題集
Optimization Softwares and Test Problems

English version is here.

このページに加えた方が良い場所をご存知の方は、御一報下さい。
特に日本国内の場所（商用もOK）についての情報をお待ちしております。
初めていらっしゃった方へ
ここには、最適化関連のソフト（コード）に関するリンクを集めました。
初めての方は以下の検索用のサイトを用いるのも一つの手です。
Guide to Available Mathematical Software (GAMS)
NETLIB Index search
OPT-NET Index search
あとは、各サイトのインデックスを御利用下さい。
目次

新着情報！

有名な大きなサイト
NP最適化問題の近似解法の最新結果のページ (情報提供：神戸大学 山口一章様）
OpsResearch
JavaのOR関連オブジェクト集のダウンロードが可能．マニュアル,チュートリアルつき．

OR Software
Seoul National Univ.の Systems Analysis Lab.が提供するORソフトウェア＆ リンク集
特に OR Program LibraryはBASIC,Pascal,C,FORTRANの各言語で書かれたプログラムソース が掲載されている．
WORMS はメルボルンにある OR and Management Science のサイトです。
１９９７年のＡＰＯＲＳに向けて始動中。 ＪＡＶＡのページもすごい！一見の価値あり。 博士課程の学生の方（あるいは取ったばかりの方）は、 Rookies Directory に登録してみては？
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 はこちら。
eLib (ZIB-BERLIN)
以下のように、いろいろなものが入っていて便利なのですが、 いま一つ整理されていません。 ここのソフトは研究用にしか使ってはいけません！ また午後５時以降は混雑するためか殆んどつながりません。 午前中がおすすめです。
Math-Web, Math-Net (ZIB-BERLIN)
いろいろな optimization software へのポインタが示されています。
MATHPROG & MP-TESTDATA
数理計画法関連のプログラム MATHPROG と、 ベンチマーク問題集 MP-TESTDATA にアクセスできます。
OPT-NET (ftp) あるいは こちら (ftp)
最適化に関する最新情報が得られる フォーラムOPT-NET です。
上記のFTPサイトのalgorithms,problems,softwareといった directoryからいろいろもらえます。
NEOS --> OTC 参照
NETLIB & AMPL
AT&T Bell Laboratories Mathematical and Computing Sciences Research
最適化に関するプログラムとベンチマーク問題集 NETLIB や、 モデリング言語 AMPL に関する情報が得られます。
京都大学に ミラーがあります。 当然こちらの方がつながり易いですが、本家もつながり易いです。
OR-LIBRARY
Imperial College Management School
OR関連のプログラム,ベンチマーク問題集 OR-LIB にアクセスできます。
OTC (Optimization Technology Center)
NEOS Guid
LP,NLP,Network Prog., Integer Prog., Global Opt. 等のソフト、テスト問題、論文等が少し手に入る。
NEOS Server
こちらで用意した LP,NLP,Stocahstic Prog., Network Prog. 等の問題を 解いてもらえる（結果は e-mail で返送される）。 Network prog. ではなんんと、RELAX と NETFLO で計算してくれる！
便利なリンク集
Unix と数学的ソフトウェア by 三田村二郎
Decision Tree for Optimization Software (by Hans D.Mittelmann)
LP,QP,NLP,Global Optimization へのリンクが張られています。
GAMS
Guide to Available Mathematical Software
いろいろな mathematical software を、 解きたい問題やソフト名から検索することができます。 これは便利。
Heuristics for Discrete Optimization (Univ. of Trento)
いろいろな発見的解法ソフトへのリンク多数。
でもあまり更新してないみたい。でも便利。
JEA
Journal of Experimental Algorithmics に掲載された論文のソフトがここに公開されます。 リンク等も張られています。
Jiefeng Xu's list
LIST OF INTERESTING OPTIMIZATION CODES in PUBLIC DOMAIN
Jiefeng Xu の個人的なリストです（個人でここまでやるのは凄い！）。 でも結構時間がかかるのが問題。
Mathematics Softwares
Mathematics Information Servers
いろいろな mathematics software へのポインタが示されています。 でも時間はかかるし、名前が書いてあるだけでなんのソフトか分からない （使えん！）。 ただAmericaの大学一覧や、Journal,Publisher 一覧もあってこれは便利。
Network Resources for OR
さまざまな最適化コード等へのリンクが張られています。 少し時間がかかるけど、とても良い。
INFORMS (OR Home Page)
OR関係情報はここにかなり集まっています。
プログラム等のリンクも多数あり。 また論文検索もできて良いようです。
OR subject Index
LP, NLP, 多目的計画等のリンクが張られています。 結構速いし、いろいろあって良い。 組合最適化 はこちら。
Scheduling と Constrained Satisfaction problem の Benchmark
Scheduling と Constrained Satisfaction problem の Benchmark への リンクが張られています。でも更新してないみたい。
College and Univ. Home pages アメリカの大学の Home Page へのリンク。
Erdos Number Project Home Page Erdos number １または２を持つ研究者のリスト（もう笑うしかない！）
論文を探すためのサイト(papers)
問題別のサイト集
データ構造(Data Structure)
  • LEDA データ構造ライブラリLEDAの research version がもらえます。 red-black tree, Fibonacci heap, 基本グラフ算法等そろっているようです。 LEDA を使った Location Problem, algorithm animation 等の プログラムへのリンクもはられています。 （使って見た人は連絡下さい。）
  • dyn_tree Dynamic Tree のパッケージです。C言語です。
線形計画法(LP)
  • NUOPT 学生用無料ダウンロード有り.
  • SOPT の demonstration software
  • simplex pivot tool は R. Vandelbei による JAVA の辞書式単体法。
  • LINDO ホームページ では LIDO, LINGO, What's Best のお試しバージョンがもらえます。 （300変数、150制約式、30整数変数が解ける） ただダウンロードにちょっと時間がかかるかも。
  • Xpress-MP ホームページ では Xpress-MP の Free Student Edition バージョンがもらえます。
  • 線形計画問題コード lp_solve です。 30,000変数 50,000 制約まで解けるそうです。 ただし商用コード程の精度は無いとも言われています。 public domain soft として、計算機実験等に非常に良く使われています。 整数計画も解くことができます。
  • 線形計画問題を解く内点法 LOQO です。 商用コードCPLEXに引けをとらないとの話です。 Benchmark もあります。 e-libのプログラムですから研究用にしか使ってはいけません。
  • Interactive Linear Programming WEB 上でＬＰを解いてもらえます。２変数の際はグラフィックスもあります。
  • 線形計画法 FAQ ソフトやテスト問題へのリンク多数有り。
  • Anima-LP LPの教育用ソフト (Mac用)がもらえます。
  • 線形計画問題を解く単体法コード minit です。minit.Z をもらって下さい。
  • 線形計画問題を解く内点法 LIPSOL です。 MATLAB 上でなくても動くようになったみたいです。 丁寧なマニュアルがあるようです。
  • 線形計画問題を解く主双対内点法 HOPDM 。Gondzio によるソフトです。
  • 内点法の論文や情報は、 NETLIB FTPサイト や NEOS のサイト を参照 （時間はかかる！）。
  • NEOS Server や OSL では、こちらで用意したLP問題を解いてもらえるらしい？ NEOS の Case Study は Diet Problem を解いてくれたりして笑える！
  • Diet problem の問題集
  • Steiglitz のLP based FIR filter design program METOR 。 （Steiglitz の Home Page はこちら(時間かかる！)）
非線形計画法(NLP)
SAT
  • DIMACS Challenge 2 : SAT に関する情報がもらえます。 またソフトや benchmark 等は dimacs 側 の contributed や benchmarks でもらえます。
  • SAT を解くソフト POSIT がもらえます。
(混合)整数計画 ((Mixed) Integer Programming)
  • 整数線形計画問題コード lp_solve です。 30,000変数 50,000 制約まで解けるそうです。 ただし商用コード程の精度は無いとも言われています。 public domain soft として、計算機実験等に非常に良く使われています。 整数計画も解くことができます。
  • Interactive LP
  • OPBDP & PLAM ： 0-1 整数計画ソフト OPBDP (Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolean Optimization) と モデリング言語 PLAM (Prolog and Modelling) がもらえます。
  • MIPlib 混合整数計画ライブラリ。ソフトと問題集
  • MINT 混合整数計画ライブラリ。Nemhauser が一枚噛んでるらしい。 もらうには 作成者にメイルを出す。（使った人は教えて！）
幾何計画(Geometric Programming)
  • XGP 幾何計画用ソフトXGPがもらえます
ネットワークフロー(Network Flow),マッチング(Matching)
  • network simplex method は R. Vandelbei による JAVA の ヴィジュアルネットワーク単体法。
  • Ernest Martins の個人のホームページ。 最短路、第k最短路、最小木等々いろいろあります。
  • Bertsekas の個人的なサイトです。 (線形,非線形)最小費用流問題を解くFORTRANコード RELAXや、 割当問題を解くAUCTION 等がもらえます。問題生成プログラムもあり。
  • DIMACS Challenge 1 : network flow, matching に関する情報やプログラムがもらえます。 問題生成から割当問題、最大流問題、最小費用流問題のソフト等 いろいろあります。
    特に最小費用流を解く Helgason and Kennington の NETFLO は定評あり。
    有名な問題生成プログラム NETGEN も ここ にあります。
  • Goldberg の個人的なサイトです。 最小費用流問題,最短路問題,割当問題,最大流問題のコードがあります。 問題生成プログラムと計算実験レポートも付いています。
  • csas.tar.z R. Kennedy による割当問題のソフト。 アルゴリズムはGoldbergの cost-scaling push-relabel 法。言語はC。
  • NEOS Server では、こちらで用意した Network flow 問題を RELAX と NETFLO で解いてもらえる（結果は e-mail で返送される）。
  • ネットワーク問題のプログラム集 PPRN の ftp サイトです。線形と非線形のソフト及び問題集、 テストレポート有り。（まずはINDEX というファイルを見て！）
  • e-LIB にはいろいろつまっていて、良くわかりません。 eLIBですので商用には使えません。
  • 最小木問題には NETLIB の MSTPAC 。
  • 最小木問題の FORTRAN codes 。
  • K shortest path 問題の ソフト です。Martin & Santos' Allgorithm, Eppstein's Algorithm 等。 FORTRAN もある。
  • Bilkent の ftp サイト では非線形ネットワーク問題のプログラムLSNNO や Fortran Codes for Network Optimization (FCNO) がもらえます。 Bilkent University はこちら。
最大派閥問題、彩色問題(Clique and Coloring)
Hard Routing Problems(TSP,VRP)
その他のグラフ上の問題(graph algorithms)
  • LOLIB Linear Orderling Problem Library. TSPLIB と同じところにあって、 やはり Reinelt が管理している。
  • METIS Graph Partitoning Problem のソフト METIS がもらえます。 行列の分解にも使えるようになっているようです。 かなり大がかりなプロジェクトみたい！
多面体論(Polytope)
  • PORTA 多面体解析ソフト （中を見た方は、教えて下さい）
大域的最適化(Global Optimization)
2次割当問題(QAP)
計算幾何学(Computational Geometry)
相補性問題(Complementarity Problem)
半正定値計画(SDP)
ゲーム理論(Game Theory)
データ包絡分析(DEA)
確率計画(Stochastic Programming)
スケジューリング、物流、交通 関連
時間割問題
露天掘り問題
カッティングストック問題
商用ソフトウェア
  • SAITECH 社 ,
    • SOPT: 線形計画、整数計画、非線形計画に対する最適化ソフトウェア
    • Smart TMS: 総合輸送管理システム
    • SINV： サプライチェーン在庫最適化ツール
    • STARS: 配車システム
    • SFLO: 拠点配置システム
  • ILOG 社 , (日本) .
    • ILOG Solver:　 リソース割り当てのための、制約プログラミングベースの最適化エンジン。
    • ILOG Scheduler: 有限キャパシティスケジューリングアルゴリズムより、 制約条件プログラミングベースの最適なスケジューリングを可能にします。
    • ILOG Planner: CPLEXの高度な技術をC++クラスライブラリで提供する線形プログラミングツール。
    • ILOG Dispatcher: メタヒューリスティックな手法やタブリサーチを駆使した、 派遣や発送・配送のC++クラスライブラリ。
    • ILOG OPL Studio: 線形計画と制約プログラミングの両方が使え、 スケジューリングもできる。 さらに、結果のヴィジュアル化もできる。 評価版も入手可能 。 （情報提供：佐中俊哉様）
    • ILOG CPLEX Suite: 　パフォーマンス、融通性、信頼性に関して 業界標準の非常に高速の線形プログラミングソルバ。
  • LGO An Integrated Model Development and Solver System for Continuous Global Optimization
  • LOGOPT ついに動きはじめたLOGOPT！ サプライチェイン最適化のソフト販売会社です。
  • 制約処理ライブラリ ICS に関する情報が得られます。 特にスケジューリング関連の問題に用いるようです。 JAVAによりお試し画面あり。
  • モデリング言語 GAMS に関する情報が得られます。
  • IBM の Optimization Subroutine Library OSL に関するサイトです。 free benchmark のところでは、 こちらで用意したLP問題を解いてもらえるらしい？ （ためした方がいらっしゃいましたら、教えてください） 向こうで用意したテスト問題はすぐ試すことができます。 解く際のマシンも指定できるところが面白い。
  • 株式会社 数理システム の最適化パッケージ NUOPT や モデリング言語 SIMPLE の情報が得られます。
  • AMPL モデリング言語 AMPL に関する情報が得られます。 京都大学に ミラーがあります(でもこちらだと ftp site になっちゃう)。
  • LINDO 線形計画ソフト LINDO を始めとする LINDO family のページ。
  • 日本ディジタルイクイップメント株式会社 時間割作成支援システムCALTなんてのも作ってる。
  • NEC ソフトウエア
松井知己のホームページにもどるには ここを クリックする．
数理第二研究室のホームページに戻るには ここを クリックする．