NASA との共同研究での 3D パッキング問題

INFORMS Annual Meeting で聞いた発表のひとつに、NASA との共同研究で 3D パッキング問題を解いている、というものがあった。

ふつうの問題とは若干違っていて、ひょっとしたら数学的性質がかなり違うのかもしれない。
発表の中では、「厳密解を求めるために、今は整数計画問題として解いている」ということで、定式化されている整数計画問題は比較的オーソドックスに定式化されていた。

これは、なかなかに面白いネタだと思う。
例えば、
１）定式化を工夫して、冗長な情報を除去したり、CPLEX などで高速に解けるようにする
２） Bender's decomposition などが使えるか検討する
３） Lagraingian 緩和, SDP 緩和などの緩和手法で近似値を低コストで得る
などなど、いろんな発展があるんじゃないかと思う。

発表のパワーポイント資料を発表者から頂くことができたので、定式化については検討してみようと思う。