離散系と連続系

連続系での最適化ソルバーには、Simplexや内点法があります。連続線形領域では、NP困難の世界から脱することができます。連続系の解は、2.5人とか、1.3人とかになります。人を、そんな風に分割することはできないので、整数化した解が欲しい訳です。組み合わせ最適化の世界は、整数の世界です。ところが、整数の世界の最適値と、連続系の最適値は、似て非なるものです。難しいのは、整数化です。連続系からなんとかしようというのがOR的アプローチAlgorithm4になります。一方で、最初から、整数の世界でなんとかしようというのが、AI的アプローチでAlgorithm1です。
最適化解は、時間をかければ、Algorithm4の方が得やすいです。一方、Algorithm1は、短い時間で近似解を得るのが得意です。現在行っているのは、Algorithm4で、近似解でよいから短い時間オーダで解を得るものです。整数化解をいつどのタイミングで得るかということが問題です。INRC2の８Weeksの１インスタンスデータを得るのに数日かかっていますが、これに近い解を１０数分程度内に得ることが目標です。とても不可思議な世界で、整数化世界とは、全く異なる様相です。多分、機械学習させれば、なんらかの法則性や相関性が見出せるのではないかと思いますが、そこまでは行わずに、アイデアをCut＆Tryするということを行っています。