AtCoder Heuristic Contest 004

phyllo(フィロ) @phyllo

そもそも大きく勘違いしてた・・・ ずっとM/8^Lだと思いこんでたけど、20*20の行列の任意点から取り出すからパターンがめっちゃ少ないのか・・・問題文ちゃんと読めてなかった。

phyllo(フィロ) @phyllo

致命的だ

Eikyu Ito @aq3948

1/ AtCoder Introduction to Heuristics の問題を商用ソルバで解いてみる、というのをやってみましたのでご報告。 最近Gurobiというソルバをいじれるようになり、マラソンの問題とか解けないかなーと思いちょっと試してみました。結論から書くと今回はうまく行かなかったのですが、

Eikyu Ito @aq3948

2/ まあ私がなんか間違えてるかもしれないので、あくまで参考まで、ということで。何かツッコミありましたら歓迎です。 Gurobiというのは、商用の数理最適化ソルバの中では最も高性能なもの（の一つ）です。PuLPを知ってる人は、あれをもうちょい賢くした感じ、と思ってもらえるとよいかと。

Eikyu Ito @aq3948

3/ 今回扱った問題はこれです： atcoder.jp/contests/intro… 問題については細かい説明は省略します。詳細はリンクを参照ください。ざっくり言うと

Eikyu Ito @aq3948

4/ 「D日間の間、K種のコンテストを交代で開く。d日めにコンテストkを開くと参加者の満足度がs[k,d]上がる。コンテストkをi日めに開き、以降j日めまで開かないと、満足度がc[k]*(j-i)下がる。満足度を最大化するコンテスト予定を立てよ」 というものです。

Eikyu Ito @aq3948

5/ 実はK=26、D=365固定なんですが、たぶんこの問題サイズは解けないだろうなーと最初から思ったので、サイズを可変にしました。 さて、定式化です。あまり凝ったことはせず、愚直なやり方でやってます。（私はGurobi、というかソルバに関してはほぼ素人です。）

Eikyu Ito @aq3948

6/ 変数は以下の2種、いずれもbinary： x[m][i] : コンテストmをi日めに開く islast[m][j][i] : コンテストmをi日めに開き、以降j日めまで開かない 当然、islastはxから決まります。配列の取り方の都合上[j][i]と順番が逆になってます。

Eikyu Ito @aq3948

7/ xはK*D個、islastはK*D*(D-1)/2個あります。Dの2乗になってますが、もっとうまいやり方があるのか？よくわかりません。とりあえず今回はこれで。 あとはやることは自明でしょう。開く満足度はx[m][i]*s[m][i]。開かない不満度はislast[m][j][i]*c[m]*(j-i)。これらを足し合わせたものが目的関数。

Eikyu Ito @aq3948

8/ 制約は実質 「sum(x[*][i])==1 但し0日めはx[*][0]は全て1とする」 だけです。コード上は、islastの否定をislastbという変数にしてる関係で islast[..]+islastb[..]=1 というのが加わってますが。 参考までにコードをつけます。結果のチェックはmdl.solを目視、という原始的な方法でやってます pic.twitter.com/pISSgKebSv

拡大

拡大

Eikyu Ito @aq3948

9/ さて、結果です。K,Dをいろいろ変えてやってみました。 K D 実行時間 10 13 1.7sec 10 14 12sec 10 15 17sec 10 16 (5分経って終わらず) 9 15 4.9sec 9 16 (3分経って終わらず) でした。本当はK=26,D=365なので「全然だめじゃん！」という結果です。

Eikyu Ito @aq3948

10/10 くどいようですが私はソルバ素人なので、もしかしたら「こうすればもっと速く解ける」というテクがあるのかもしれません。指摘歓迎します。ただまあ、今回はこういう結果だった、ということで。個人的には「ソルバ使えねぇ…」という印象を抱く結果に終わりました。

Umepon @shunji_umetani

@aq3948 整数計画ソルバーは問題によって向き不向きがあるのですが一点だけ．最適解が得られず計算が終了しなくても質の良い暫定解を保持していることは少なくないので，計算時間の上限を設定した上で，暫定解を取り出すようにした方が良いと思います．ヒューリスティックコンテストなので．

Eikyu Ito @aq3948

@shunji_umetani 今回はやってませんが、了解です。わざわざありがとうございますm(__)m

Eikyu Ito @aq3948

まああれですね、Introduction to Heuristicsで(1点でも)正の得点をとった人はとりあえず「俺は（アタシは）世界最高のソルバを越えた！」と胸を張っていいんじゃないかとｗ

Eikyu Ito @aq3948

11/ …てなことを書いたらなんと数分も経たぬうちに大学の数理最適化専門の先生からアドバイスが来ました。ツイッターしゅごい。でさっそく実験してみました。 やってみたのは ・TimeLimitパラメタを設定する ・制限時間内に得られた上界と下界のギャップを見る です。

Eikyu Ito @aq3948

出力ログに"gap XX%"　("best objective"と"best bound"の差)があるので、この数字を見てみました。 K D timelimit gap(%) (sec) 10 15 10 3.4 15 20 10 28.7 15 20 60 20.2 20 35 10 105 20 50 10 278 20 50 60 255 26 365 10 3分で終らず

Eikyu Ito @aq3948

AtCoderでは制限時間2secですが、ここでは10秒からにしました。 先ほど「終わらない」としていた(10,15)は、実は10秒で誤差3.4%以内の解が求まっていました。ただ(15,20)だと20%強に。(20,35)だと100%以上で、この辺はやはりダメそうです。また、10秒を60秒に延ばしても大きくは改善しませんでした。

Eikyu Ito @aq3948

ダメ元で本来の(26,365)もやってみましたが、これは制限時間過ぎても終わりませんでした。TimeLimitは"Optimize()"だけのもので、その前のモデリングで時間がかかってる、てことでしょうか。

Eikyu Ito @aq3948

というわけで、若干よくなったものの、やはりIntroduction to Heuristicsには使えない、という結論は変わらなかったです。ただやはりいろいろテクニックはあるみたいなので、今回はあまりに遠すぎましたが、「あと少し」くらいまで行ってる問題ならば粘ってみる価値はあるかもしれません。

Eikyu Ito @aq3948

というわけで今回得られた教訓は「とりあえずなんかやったらツイッターなり何なりに書いてみろ」ですね。思わぬところからフィードバックが来る（かもしれない

Umepon @shunji_umetani

ふと，AtCoderさんがヒューリスティックコンテストに，整数計画ソルバーで瞬殺できる問題を出題するなんて迂闊なことはせんやろうと思った．

Eikyu Ito @aq3948

@shunji_umetani ですよね…