3/5(水)〜3/7(金)でOR学会の2025年春季シンポジウムと研究発表会があった。
そこでいろいろ話を聞いてきたので、興味深かったものをいくつか書いてみたい。
シンポジウム
毎年シンポジウムはテーマが決まっていくつかの講演がされる感じだったけど、今年はパネリストを複数人招いてのパネルディスカッションを行う形式で、いつもとはちょっと違う感じだった。 入門書の話、コミュニティの話、海外の話と、いろんな話題について多くの人の話を聞ける形になっていたのは面白かったと思う。
ただまぁ初めての試みということもあって、進行がちょっと大変だったのかなという感じも。 基本的には司会と各パネリストとの間の会話がパネリストの分だけ繰り返されるという感じになりがちだったので、もっとパネリスト間での会話も聞きたかった感じがあったかなぁ。 もちろん会話の制御は難しくなるけど、せっかく複数人のパネリストを集めたんだから、その絡みによる創発的な議論が生まれるともっと面白かったと思う。
植物工場における照明配置スケジューリング
植物工場では人工光を使って植物を育てるんだけど、電気代がめっちゃかかるので、それを安くできないかという話。
想像してたのは安い時間の電気をうまく使えるようにするとかなのかなと思ってたんだけど、実際には月単位で定額定量みたいな契約になっているらしく、電力量の総量を減らさないとダメという感じだった（これは質問して分かった）。 そうなると工夫の余地ってほとんどなさそうな気もしたんだけど、そんなことはなくて、いろんな工夫が考えられていてとても興味深かった。
2次元グリッド上で配電損失を最小化する全域木について
家庭に電気を送るときには電線を使うわけだけど、電線が多いとメンテナンスとかも大変。 そこで、全部の家庭に電気を送れるような木構造（＝電線が最小限になる）で、できるだけロスの少ないものを見つけようみたいな動機の問題。
問題をシンプルにするために、2次元の格子状のグラフを考えて、左上の頂点が発電所、それ以外の頂点はすべて家庭とする。 これで全域木を作れば全部の家庭に電気を送れることになる。 その上で、各辺に流す電流を（流入量）＝（流出量の和）＋（家庭の需要の1）として、各辺に流れる電流の二乗の和をロスと考える（$P$を電力、$I$を電流、$R$を抵抗とすると、$P = I^2R$なので、電流の二乗がロスになるイメージ）。 このロスを最小にするような全域木を求めるという問題（損失最小全域木問題）。
もちろん、これはかなりシンプルにしてて、もっと複雑なグラフ構造を考えたり、各辺に重みを与えたり（＝抵抗が辺によって異なるイメージ）、各頂点の需要を変えたりというのがより一般的な形ではあるんだけど、実はこのシンプルな形であってもNP-困難になってるんだとか （これがNP-困難であることの証明が1つ目の成果とのこと）。
さらに、これに対してmin-minアルゴリズムという精度保証付きの近似アルゴリズムが提案されていて、これまでは近似精度が2倍という解析結果だったけど、それを9/8倍という解析結果に改善できたとのこと（これが2つ目の成果）。
このmin-minアルゴリズムの動きが面白くて、パズルみたいに解を組み上げていくのがまるで手品のようだった。 いやー、面白い解き方を考えるもんだなぁとすごく感心した。
問題設定としても面白いし、解き方も面白かったので、とても興味深い問題だったなぁ。
決定木を用いたカテゴリカルデータへの距離の付与
データ分析をやってるときに、カテゴリカルデータに対して「データ同士の近さ」のようなものを考えたくなることがあるけど、それを決定木を使ってやってみたよという話。 数値やベクトルにエンコードするというよりかは、カーネル関数（っぽいもの）を与えるイメージだと思う。
発想としてはシンプルで、対象とするカテゴリカルデータを含むデータで何かしらのタスクについて決定木を作って、各データが行き着く葉の間の枝の数について、平均をとる感じ。 特徴として離れたものであれば最初の方に枝分かれするから距離が長くなり、似たものであれば最後の方で枝分かれするから近くなるでしょ、みたいな。
まぁタスクによって決定木の形は変わってしまうから得られた結果が汎用的に使えるのかは怪しそうだけど、手法としてはお手軽だし使える場面もありそうなので、ちょっと覚えておきたいなと思った。
Feasibility JumpのNuorium Optimizerへの導入
発表内容としては、混合整数計画問題（MIP）を解くときに、PACSという既存手法の前にFeasibility Jumpという手法をやっておくと、よりいい結果になったよ、というものだったんだけど、このFeasibility Jumpが個人的に気になった。
Feasibility Jumpは、目的関数はとりあえず置いといて、まずは実行可能解を見つけましょというもので、線形計画法を使わずに、局所探索で実行可能解を探していくものらしい。 このときの近傍の選び方でけっこう頑張っているっぽい。
で、この実行可能解を見つけるというのが、パズルとかを整数計画問題として解こうと思ったときに、そのまま使えたら面白いよなと。 局所探索の話とかを聞くたびに、そのうち実装してみたいなと思ってはいたけど、なかなか手が出せなかったところがあるので、試すのにちょうどいいお題が降ってきた感じ。 ということで、そのうち実際に試してみたいと思う。
大規模・不確実な組合せ最適化問題に対する理論とアルゴリズム
普通の最適化だと最初にデータが全部与えられて問題を解くとなるけど、実際には大量のデータがあるので全部を一度には処理できなかったり、不確実性があってデータが順番に現れてきて、全部のデータが揃う前に意思決定をしないといけない場合がある。 そこで、データが順番に出てきて、できるだけ小さいメモリで処理をしたり（ストリーミング計算）、データが出てきた順に意思決定をして、あとからは解を変えられない（オンライン計算）ときに、解がどうなるかという研究。
取り上げられてたのは単調劣モジュラ関数の最大化をストリーミング計算で考えるというものと、二部グラフの最大マッチングをオンライン計算で考えるというもの。 前者はセンサ配置や機械学習、画像処理で応用があるらしく、また後者はタスクの割り当てやカーシェアリングなどで応用があるらしい。 後者はイメージしやすいし、たしかに現実の問題に近そうで、興味深い。
そして研究としては精度保障のある近似アルゴリズムを考えるというもので、とくにデータが全部揃っている場合との比較がされている感じだった。 当然、最初からデータが揃ってる場合に比べて解は悪くなるんだけど、それが最悪どれくらい悪くなるのかというのを理論的に示していて、これも面白い。 その中で離散的な構造に関する研究の成果が活かされているっぽい。
現実問題に近いところを解いているという面白さと、その中で理論的な成果も活かされるという両方の面白さがあるのがとてもいいよね。
株式市場状態推定とそのポートフォリオ最適化への応用
投資をするときに、いくつかの投資先を組み合わせることで、リスクを抑えつつ利益も出るようにしようというポートフォリオ最適化は昔から研究されている内容。 ただ、そのときに必要となるのが、各投資に対するリターンの期待値と分散がどうなっているのかというデータ。 基本的には一定の期間の実データから期待値と分散を計算することになるけど、この期間をどうすべきかというのが悩ましい問題。 長すぎると古いデータも入ってきて現状にそぐわないものになっている可能性もあるし、逆に短すぎると直近の動きに影響を受けすぎてしまって通常の動きとは大きく異なるものになっている可能性もある。 そこで、時系列データをいい感じにクラスタリングしてあげて、現在の状態が含まれるクラスタについて期待値と分散を計算してやれば、いい感じのデータになるのでは、という研究。
時系列データをいい感じにクラスタリングしたいというのはけっこうあって、すごく興味深い話だった。
ちなみに、単純にクラスタリングするとクラスタが飛び飛びになってしまったりするので、隣接する点ができるだけ同じクラスタに入るような工夫を入れたとのこと。 そして組み合わせとかも入ってきてちょっと解きにくい問題となるので、EMアルゴリズムを使っているらしい。 結果例も出てたけど、たしかに社会的に大きな動きがあったり（たとえばリーマンショックとか新型コロナとか）で市場の様子が大きく変わったときにクラスタが変わる感じになっていて、よさそうな感じだった。
あとは気になるところは、じゃあ現在の状態が他の状態に移ってしまわないかということになると思うので、そういう判断ができないかどうかというのをちょっと質問してみた。 普通のクラスタリングで、現在の点が連続的に移るのであれば、クラスタの中心近くにいれば他のクラスタには移りにくいと判断できそうだし、クラスタの端近くにいたら他のクラスタに移る危険性が高そうと判断できそうかなと。
ただ、これについてはまだ調べてないとのこと。 実際問題、たとえば新型コロナのように予測もつかないような出来事でクラスタが急に変わってしまうこともあるから、なかなか難しそうという感じではあるらしい。 とはいえ、そういったイレギュラーなケースでなければクラスタを移るときに何か特徴があるかもしれないし、今後の研究にも期待したいところ。
今日はここまで！
