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

　

　

講義名：応用プログラミング演習
担当：久保 幹雄，渡部大輔
対象：流通情報工学
単位：2単位
開設時期：前学期
授業のサポートページへ（旧）

講義内容（前半）：

Pythonのみ（AMPLはやらない）；以下のいずれかを自宅PCにインストールしておくことが望ましい．

Python ダウンロード（授業ではバージョン2.6を使用します．）

ActivePython ダウンロード（授業ではバージョン2.6を使用します．）

PythonとAMPLについての入門ビデオはこちら．
入門用スライドのPowerPointファイルはこちら．（English version  python_crash_course.pdf.）
参考：MITのPythonを使った講義のページ（Introduction to Computer Science and Programming） ビデオやハンドアウトがダウンロードできます．
日本語版公式マニュアル（バージョン2.5用だけど気にしない）
Python課題集

講義内容（後半）： VIsual Basicの情報はこちら

　

このページは，「メタヒューリスティクスの数理」 （共立出版）のサポートページも兼ねています．

著者

久保幹雄 Mikio Kubo 

J. Pedro Pedroso HP

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

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

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

download all files

　　for Python 2.x zip file

　　for Python 3.x zip file

  1. graph tools (used in common in the following programms)
  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行目： 准教授 -> 教授