最近 Process Mining: Data science in Action [1] の受講を初めてしまったので、 Discrete Optimization [2] の方をしばらく放置してしまっていたが、少し再開。 LPについては以前に受講した Linear and Discrete Optimization [3] でも勉強したし、MIPについてもある程度の知識はあると思うので Linear & Integer Programming についての講義は一旦スキップし、Advancedの講義を見てみる。
* Large Neighborhood Search - asymmetric TSP with time windows
Large Neighborhood Search は制約プログラミング(Constraint Programming)やMIPと、局所探索(Local Search)の組合せで、まずCPで実行可能解を求め、その近傍を一部の変数のみその解での値に固定するなどして定義し、その中での最適化をCPで行うことで改善回を求めるというアプローチ。
そういえば、Large Neighborhood Search の話はRAMP2014の Proximity search heuristics for Mixed Integer Programs http://www.orsj.or.jp/ramp/2014/paper/4-2.pdf でもあったなぁ。
* Column Generation - branch and price, cutting stock
Column Generation (列生成法) については漠然としたイメージは持っていたのだけれど、カッティングストック問題(cutting stock problem)を例にした説明は分かりやすくて、ちゃんと理解できたと思う。 branch and price については非常にあっさりとした説明しかしてくれていなかったけれど、 https://en.wikipedia.org/wiki/Branch_and_price のフローチャートを見て理解できたと思う。
そういえば、SCIPのGCG(Generic Column Generation)の作者の Gerald Gamrath に、Column Generation とかを勉強するには何を読んだらいいか昔聞いたら、彼の Ph.D thesis の Generic Branch-Cut-and-Price http://www.zib.de/gamrath/publications/gamrath2010_genericBCP.pdf を紹介してもらったのだった。こっちもそのうち読みたいところ。
* Scheduling - jobshop, disjunctive global constraint
名前だけ知ってたジョブショップ・スケジューリングがどういうものか知った。が、いまいちよく理解できなかったので、ビデオを見なおさないと……
[1] Process Mining: Data science in Action
https://www.coursera.org/course/procmin
[2] Discrete Optimization
https://www.coursera.org/course/optimization
[3] Linear and Discrete Optimization
https://www.coursera.org/course/linearopt
#optimization #dopt003