整数計画を見たら考えること
はじめに
この記事は数理最適化アドベントカレンダー 2023 の 12/22 の記事です。
実応用の数理最適化の問題は多くの場合整数計画問題に定式化されます。しかし、整数計画問題は良い性質を持つ特殊な問題以外は NP 困難であり、これをどうやって解くかという問題が残っています。
本記事では sfujiwara が実際に整数計画問題を見たときに考えるアプローチを大雑把に分類して紹介します。
まずはソルバーに突っ込む
だいたい初手はこれです。整数計画のソルバーに突っ込んで最適解が得られるならそれに越したことはありません。
最適解が得られるというのは良い結果が得られやすいという嬉しさもあるのですが、それ以上に最適化アルゴリズムを改善してもこれ以上結果は良くならないという確証が得られるのが大きく
- 結果が微妙だった時に最適化手法ではなく定式化の筋が悪いと問題を切り分けられる
- 最適化アルゴリズムの改善にそれ以上時間を割く必要がなくなる
というメリットがあります。
失敗パターンは計算時間が長くて終了しないケースです。ただ、システムに組み込むには長くても数時間程度で最適解が出るのであれば十分な成果です。ヒューリスティクスを実装する場合でも最適解と比較してどれくらい良い解が得られているかを知ることができます。
そこそこの速度で解けた場合でも整数計画は解くインスタンスによって計算時間のブレが大きいので、システムに組み込む場合には注意が必要です。反復の途中で打ち切った解を採用するなどの工夫で解決できますが、そもそも実行可能解を見つけるのに時間がかかってしまうケースもあります。
自分で最適化アルゴリズムを設計する場合
近傍探索
今の解の近傍へ移動して（少し解を変更して）解の改善を繰り返します。定番どころで言うと焼きなましはこの分類です。近傍をどう定義するかなどの難しさはありますが、一番汎用性が高く、自分でアルゴリズムを書く場合はこの方針に落ち着くことが多いです。
少し厄介なのはソルバーを活用するケースと違ってスクラッチで書くことになるため、Python のような言語だと速度面で十分なパフォーマンスを出せないことがあります。一方で、ソルバーのインターフェースが用意されていたり組織で Python を採用しているなどの事情で初手は Python から入りたいことも多く、言語の選択で悩むことがあるかと思います。
変数の固定
ソルバーを上手く活かしたい場合は次のような方針で考えることがあります:
- 0-1 整数変数のいくつかを 0 か 1 の定数に置き換える
- 変数を減らした整数計画をソルバーで解く
- 1 に戻って固定する変数を変更する
最適化手法としてはこのように変数を固定した sub-problem を繰り返し解くというのは定石の一つです。たとえば連続最適化では Coordinate Descent という 1 変数の最適化を繰り返す手法があります。
問題の分割
整数計画の規模が大きくて解けないのであれば複数の小さい問題に分割することを考えることもあります。たとえばスケジューリングの問題であれば本来二ヶ月分をまとめて最適化したいところを一ヶ月ずつに分割して解くといった具合です。
- 最初の一ヶ月分をソルバーで解く
- 最初の一ヶ月分の変数を上の結果で定数に固定して二ヶ月分をソルバーで解く
という手順になります。ソルバーを活用しやすい方針ではありますが、各 sub-problem を解く手段は必ずしもソルバーである必要はなく、自分で組んだ近傍探索のような手法と組合せても問題ありません。
緩和
0-1 整数変数
- 連続最適化の問題を解く
- 上の結果では
x \in \{ 0, 1 \}
ということをします。一番単純な丸め方はたとえば
丸めると簡単に言いましたが、解が実行可能になるように丸めるのが面倒だったりすることもあるので、この方針を採用する機会は少ないかもしれません。
おわりに
sfujiwara は整数計画を見たら、だいたい上記の方針からどれが良さそうかなということを考えています。たとえば昔やった技術書典のサークル配置最適化は非常に単純なアルゴリズムですが、上記の分類で言うと近傍探索でもあり変数の固定でもあると言えます。逆にどの方針でも難しいようであれば、もう少し問題設定や定式化を簡単にできないかを考えます。
結構人によって考えることは違いそうなので、あくまで一例ということで。他の人がどういうことを考えているかも知りたいです。
Discussion