Modern-Heuristics.com

メタヒューリスティクスの数理のサポートページ

modern heuristics Home
スライド
python-benchmark
English Page
お問い合わせ
サイト マップ
メタヒューリスティクスの数理 (共立出版)


著者

久保幹雄 Mikio Kubo    公式HP   プライベートHP    関連書籍 amazonで購入

J. Pedro Pedroso         HP

 

メタヒューリスティクス(metaheurisitcs, modern heuristics)は,困難な組合せ最適化問題を解くための比較的新しいフレームワークである.本書のポリシーは,以下の通り.

  • 実際に動くプログラムを示し,それを使って解説する.
  • 抽象論(哲学)ではなく,具体的なアルゴリズムを設計する.
  • 実際に役に立つ工夫を紹介する.
  • 自分で一から効率的なメタヒューリスティクスを設計できるようなコツを伝授する.
  • 応用例を多く示す.とりあげる問題は,グラフ分割,最大安定集合,グラフ彩色,巡回セールスマン,2次割当,多制約ナップサック,数分割である.
  • 実際に動くプログラムをソースレベルで解説する.コンパクトに記述するために,用いるプログラミング言語はPythonを選択した.Pythonについての入門ビデオはこちら
 
本書で用いたPythonのプログラム

Programs in Python language

   download all files 
       for Python 2.x zip file
       for Python 3.x zip file

 

  • graph tools (used in common in the following programms)

  • Graph partitioning problem
    • tabu search
    • simulated annealing
  • Maximum stable set problem
    • tabu search
    • plateau search

     

  • Graph coloring problem
    • construction heuristics (including SEQ, DSATUR, RLF)
    • tabu search
    • hybrid of genetic algorithm and tabu search

  • Traveling salesman problem
    • basic local search
    • with GUI (using networkX)

  • Quadratic assignment problem
    • tabu search

  • Multi-constrained knapsack problem
    • tabu search
    • MIP based approach

  • Number partitioning
    • differencing method for bipartition
    • differencing method for multi partition
    • Longest Processing Time (LPT) heuristics (by solving multiprocessor scheduling)


 

誤植等(数式等はLaTeXフォーマットで記述)


p.70 3行目:divide and conqer -> divide and conquer

p.203 13行目: $5L$ -> $5${\tt L}

p.227 左段 21行目(索引): divide and conqer -> divide and conquer

背表紙 著者紹介 4行目: 准教授 -> 教授



Mathematical Programming Formulations and Programs in Mosel (Xpress-MP)

 

graph partitioning problem

 

maximum stable set problem


graph coloring problem

 

traveling salesman problem

 

quadratic assignment problem


multi-constrained knapsack problem

number partitioning problem

lotsizing problem