« 読了：11/17まで (NF) | メイン | 読了：11/18まで (A) »
2009年11月19日 (木)
宮代隆平，松井知己 (2006) ここまで解ける整数計画. システム/制御/情報 : システム制御情報学会誌, 50(9).
昨年，勤務先の仕事の都合で組み合わせ最適化について勉強する羽目になった。勉強するといっても，素人向け入門書を読みかじる程度なのだが，この入門書というのがどれもギリシャ語のような按配なのである。途中で何度か半泣きになった。
そのプロセスでもっとも役に立ったのが，意外にも，ネットで拾ったこの文献であった。いまでもことあるごとに読み返している。感謝の意を込めてメモしておく。
変数間の関係に線形な制約が課せられていて，それらの制約を満たす値の組を見つけるような課題のことを線形計画問題という。最近は技術が進歩して，ソフトウェア(ソルバー)が大変優秀だし，フリーのソルバーさえ存在する。で，変数(の一部)が整数であることが求められている場合を，特に整数計画問題という。普通の線形計画問題より，整数計画問題のほうがはるかに難しい。使えるソルバーはすごく高価だし，フリーのソルバーはオモチャ並みの性能しか持たない。
資料を読みかじっていてびっくりしたのは，この分野には素人考えでは想像もつかないような不思議なノウハウがある，というところ。たとえば，制約式が少ないほど速く解けそうなものだが，そうともいえない。冗長な制約を重ねて定義すると遅くなりそうなものだが，これがそうでもない。また，この論文によれば，単に許容解がひとつわかればいいという場合でも，嘘でもいいからなにかの目的関数の最小化を目指したほうが速く解けるし，目的関数の係数がばらばらの値であるほうが速く解けたりするんだそうだ。わけわからんなあ。
整数計画問題がうまく解けない場合の対処策には，大きく分けて(1)あきらめる，(2)あきらめない，のふたつの方法がある由。ははは。で，後者を選ぶ場合には，緩和課題(変数を整数ではなく実数にしてしまった課題ということだと思う)を解いて，(1)その最適解で，値が0ないし1になっている変数の個数をみる，(2)最適解発見までの時間をみる，(3)最適解が元の整数計画課題の何割くらいになっているかどうかをみる...のがお勧めだそうだ。(3)の意味がよくわかんないんだけど...すでに整数計画問題で最適解が得られている場合の話であろう。
2009/12/20追記
著者の松井先生からご教示を頂くことができました。上記(3)は，すでに小さめの整数計画問題で解を得ているとき，その目的関数の値に対して，その問題を実数に緩和した問題の目的関数の値がどのくらい小さいかを調べる，ということだそうです。なるほど。。。
松井先生，親切なご教示，誠にありがとうございました。
久保幹雄 (2006) 数理計画ソルバーを用いたメタ解法. システム/制御/情報 : システム制御情報学会誌, 50(9).
最適化の問題へのアプローチには，線形計画法で最適解を求めるやり方と，メタ・ヒューリスティクス(汎用的なヒューリスティクスのこと。局所探索とか焼きなまし法とか)を使って近似的な解を探索するやり方がある。本屋であれこれ探していて，線形計画の本には線形計画，メタ解法の本にはメタ解法のことしか書いてないことに気が付いた。なんでもいいから解き方を教えてくださいよ，というアサハカな立場からみると，この状況はかなり不思議であった。
先週たまたま見つけたのが，上記と同じ特集号に載ったこの論文。内容は難しすぎて手に負えない部分が多いのだが，冒頭2ページの概観を読んで，霧が晴れるような思いであった。著者らによれば，整数計画ソルバーで解く方法のほうが実務的汎用性がある。メタ解法は問題の構造を正しく捉えないと設計できないし，ちょっと問題が変化しただけで位置からやり直しになってしまいかねない。いうなれば，ソルバーは万能ナイフ，メタ解法は日本刀や中華包丁のようなもの。で，このふたつの技術はほとんど独立のグループによって研究されており，あまり接点がないのだそうだ。
なるほど。。。ことばから受ける印象では，メタ解法のほうが汎用的，という感じだが，現実にはそうでもないんですね。先週から遺伝的アルゴリズムの入門書を何冊か読みかじっていたのだけれど，どうやらポイントはアルゴリズムそのものより，課題の構造をうまく捉えた遺伝子型の設計にあるようで，これは案外に名人芸の世界なんじゃないか，と混乱していたところであった。この論文のおかげで，疑問が氷解した思いである。
(で，この著者の名前に惹かれて久保&ペドロソ(2009)を買い込んだら，その第三章がこの論文の中身と同じだった。やられたぜ)
思うに，こういう素人向け啓蒙論文を書いたところで，あまり業績評価にはつながらないのではないだろうか。そういう点でも，著者の先生方に感謝。それともORの世界では，こういう啓蒙も研究者の大事な仕事だと認められているのだろうか。そうだといいんですが。
論文：データ解析(-2014) - 読了：11/18まで (AS)