10日前まで開催されていたKaggleのSanta's Workshop Tour 2019に参加していました。結果は1620チーム中の142位。Kaggleで初めてのメダルであるブロンズメダルを獲得できました。最適化系のコンテストなのに問題のサイズが小さく、コンテストの序盤から最適解にたどり着く人が徐々に増えていく展開。しかも最適解にたどり着いた人は皆Gurobi や CPLEXなどの商用最適化ソルバを使っているらしいことがわかり、途中で戦意喪失しました。
問題概要
5000個のファミリーをday1からday100までのいずれかに割り振り、あるコストを最小化する最適化問題です。
各ファミリーには以下の情報が与えられます。
- 家族を構成する人数: 2人から8人。4人が一番多い
- 希望日: 各家族はchoice_0からchoice_9までの希望日を持っている。
コストは以下の2つの和として計算されます。
- preference cost
- 家族の割りあて方に対してつくコスト。各家族は、choice_0に割り当てるとコストが小さく、choice_9に割り当てるとコストが大きい。choice_0からchoice_9以外の日に割り当てるとさらに大きなコストとなる。
- accounting penalty
- 各日に割り当てられた人数の連続性に対してつくコスト。ある日に割り当てられた人数と、その次の日に割り当てられた人数とのずれが大きいほど大きなコストとなる。
- accounting penaltyは具体的には下式で与えられる。ちょうど125人のときにpenaltyが0になることに注意。
やったこと
基本的には、以下の繰り返しでした。
- 強いNotebookが発表されて自分の順位がガタ落ちする
- 強いNotebookの出力を初期値として、自分の実装した最適化手法を適用し、すこし良い値を出す
最終スコアである69410.61には以下のようにして到達しました。
- Manual to improve submissions | Kaggle で提案された、特定の日を強制的に125人にするノートブックを流用。day37, day44, day51, ...を強制的に125人とした
- それにより得られた解はいったんスコアがとても悪くなるが、以下の最適化を繰り返すと、最終的に69410.61に到達した
- 2家族をランダムに選び、割り当て日をスワップ
- スコアが悪化する場合でも、少しの悪化であれば確率的に受け入れる
- N家族をランダムに選び、そのN家族について割当を総当りし、もっともよいスコアのものを選ぶ
- もしある家族が今choice_Kを選んでいるとしたら、choice_0からchoice_Kまでを総当り
- Nを大きくするほどあたりを引く可能性が大きくなるが、計算時間も大きくなる
- 2家族をランダムに選び、割り当て日をスワップ
焼きなましで最適解に近づけないかと試行錯誤しましたが、うまくいきませんでした。最適解の割当結果を見るとちょうど125人である日がもう一日多かったのですが、そのような分布を焼きなましで作ることは相当難しいようでした。
