応用プログラミング演習
ホーム 上へ 流通最適化工学 流通OR 流通管理特論 流通経営工学演習 流通最適化工学特論 応用プログラミング演習

 

 

講義名:応用プログラミング演習
担当:久保 幹雄,渡部大輔
対象:流通情報工学
単位:2単位
開設時期:前学期

講義内容(前半;後半は渡部先生によるVisual Basic):

Python ダウンロード(授業ではバージョン2.xを使用します.)

入門用スライドのPowerPointファイルはこちら.(English version  python_crash_course.pdf.)
日本語のビデオはこちらのPython入門とドットインストールを見ておくこと
英語版のビデオは以下を参照:
edXのIntroduction to Computer Science and Programmingのページ (登録が必要)
MITのPythonを使った講義のページ(Introduction to Computer Science and Programming) 
日本語版公式マニュアル
Python課題集追加課題集

このページは,副読本の「メタヒューリスティクスの数理」 (共立出版)のサポートページも兼ねています.

授業のテキストとしては,「あたらしい数理最適化 -GurobiとPython言語で解く-」を使います.サポートページはこちら(サンプルコードなどがダウンロードできます).

著者

久保幹雄 Mikio Kubo 

J. Pedro Pedroso HP

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

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

Pythonのプログラム (Programs in Python)

download all files

  for Python 2.x zip file

  for Python 3.x zip file

  1. graph tools (used in common in the following programs)
  2. Graph partitioning problem o tabu search o simulated annealing
  3. Maximum stable set problem o tabu search o plateau search
  4. Graph coloring problem o construction heuristics (including SEQ, DSATUR, RLF) o tabu search o hybrid of genetic algorithm and tabu search
  5. Traveling salesman problem o basic local search o with GUI (using networkX)
  6. Quadratic assignment problem o tabu search
  7. Multi-constrained knapsack problem o tabu search o MIP based approach
  8. Number partitioning o differencing method for bipartition o differencing method for multi partition o Longest Processing Time (LPT) heuristics (by solving multiprocessor scheduling)

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

  1. p.70 3行目:divide and conqer -> divide and conquer
  2. p.203 13行目: $5L$ -> $5${\tt L}
  3. p.227 左段 21行目(索引): divide and conqer -> divide and conquer
  4. 背表紙 著者紹介 4行目: 准教授 -> 教授