第3回 Asprova プログラミングコンテスト
第3回 Asprova プログラミングコンテストに参加しました。1位だったようです。最後にパラメータをいじって数回提出したら900万点ぐらい上がってしまった結果なので、3位から上のスコアに本質的な差を感じられず、その点は運がよかったなあという感想になりました（完全に偶然上がっただけというわけではありませんが）。
コンテスト中にやったことをまとめてみます。
問題
その前に問題の内容ですが、ここには雰囲気だけ書くことにします。もとの問題文と違うことを書いていたり情報が足りなかったりするので、正式かつ正確な内容は問題文を見てください。
あなたは工場を持っています。工場には複数の設備があり、それらを動かして複数の品目を生産しています。それぞれの品目は複数の工程を経て完成し、各品目の各工程に使用する設備は一意に決まっています。
工場ではたくさんの注文を受け、それらを受けた順に生産することになっています。注文にはそれぞれ納期が決まっており、それに遅れるとお金はもらえません。
ある日あなたは、注文を受けすぎて現状の設備では納期までに全く対応しきれないことに気付きました。そこであなたは資金を投資することで設備の生産性を上げることにしました。
適切に投資して利益を最大化する計画を立ててください。なお必ずしもすべての注文を納期に間に合わせる必要はありません。
方針が固まるまで
各工程を割り付ける設備は一意に決まっているし、同じ設備に割り付ける工程の順番も決められているので、設備の能力の上げ方を固定すればなるべく早い時間から貪欲に割り付けていくのが最適スケジュールになる（と問題文にも書いてある）。そうすると、考えるべきことはどの設備の能力をどの日に上げるかだけなる。
よくわからないけどとりあえず山登り、と思ったがこれはよくなかった。ほとんどスコアが上がらない。考えてみればそれはそうで、近傍のとり方が下手だと初期状態から遷移できる先でスコアが上がる状態がほとんど存在しない。そしてこの段階でとった近傍はだいたい下手である。
こういう状況でまず最初に思いつくのはスコア関数をいじることで、今の場合だと納期遅れを一時的に許容したい感じなので、納期遅れが発生したときは遅れの量に応じて利益に一定の割り引き係数をかけてみた（元々のスコア関数は少しでも遅れると 0 になる）。ところが、これは係数が大きすぎると遅れをあまり気にしない計画になって能力追加するメリットが少なくなるし、係数が小さすぎると能力追加コストが見返りに勝ってしまうので何もしないほうが得になってしまう。ということであまりいい結果が出ない。
ビジュアライザを見た感じだと、広範囲に対してまとめて能力追加しないとあまり効果がなさそう。追加コストの評価も一時的に小さくする、とか考えられないわけではないけど、こういうことを積み重ねるのもちょっとアドホック感が出てくるきらいがある。
そこで別の方針を考えた。能力をちょうどいいところまで上げる問題ではなく、最初に多すぎるくらい追加しておいてちょうどいいところまで下げる問題だとみなす。これがわりとよかったようだ。何しない状態だとスコアの上がる遷移があまり見つからないのに対して、上げすぎの状態は不要なところをちょっと下げるだけでスコアが上がるので、スコアが更新される遷移がたくさんあるのだ。
まず最初に、コストパフォーマンスのよさそうな（性格には、単位資金あたりの短縮稼動時間が最大の）設備を選んでちょっとずつ増やすループを回し、遅れがなくなったらそこから各設備と各日付けについて減らしても大丈夫ならちょっと減らすループを回して解を作ってみた。練習用データだといい具合になったと思ったけど、提出してみたら一部のテストケースで大幅にマイナスになって-10億点が出た。負の点数でも一応 AC は出るようだ（最高点が負だと新システムの順位表では0点になり、旧システムだと負の点数になって未提出よりも下位に表示される？）。
スコアは負になったけどこれを初期解にして山登りでもするか、という気持ちになって試してみたらすぐ局所最適解に到達したので、焼き鈍すことにした。近傍のとり方は設備と連続する何日かをランダムに選んで、その日の能力を 8〜現在値+8 の範囲でランダムに変更する、とかだったと思う。ここまでのことを実装して 957875042 が出ている。
焼き鈍しができたので、高速化する意味があるかどうかを見るために回す時間を伸ばしたところ、まだけっこう上がるようだった。
このあたりまででだいたいの方針は出ていて、あとはずっと焼き鈍しを頑張る感じになった。後半は高速化にかなりの時間を費やしていた気がする。細かいところでは 1.1 乗をメモ化するとか温度の計算を 256 回おきにするとかメモリアクセスの局所性を頑張って上げるとかいろいろよくある最適化をした。高速化はループ回数という形でわかりやすく結果が出るので楽しいのかもしれない。最終的に焼き鈍しのループは practice05 で322万回ぐらい回っている。
あと、そろそろテストケースを手元で作るべきなんだろうなと思い始めたけど、結局作らなかった。
焼き鈍し周り
近傍のとり方
日をランダムに選ぶと全く稼動してない日を選んでしまう可能性がそこそこあって無駄になってそうだと思ったので、日を直接選ぶのではなく工程を選んでそれが割り当たっている日を取得することにした（各工程の開始と終了の時刻を覚えておく）。
practice04 の局所最適解（後述）を見て、同じ品目の連続する二工程に対して変更をするのも近傍に追加してみた。効果がどれくらいあるか実ははっきりしなかったのだが、平均的にはスコアはよくなってるようにも見えるので採用することにした。
近傍は時間経過に合わせてだんだん狭める。具体的には、x = (経過時間)/(制限時間) として ±(2+log_2(x)) の幅で能力追加量を変化させる。ただし一番スコアがよかった提出では x < 0.15 のときはもっと大きく動かしている。ちなみにこの式は x = 1, 0.5, 0.25 でそれぞれ 2, 4, 6 ぐらいになってくれるとまあまあよさそうな感じが（実験的に）したのでそれっぽいのにした。別にきれいな式にする必要はないし折れ線とか階段でもよかったと思う。
最後の 0.1% の時間は、追加能力を減らす方向だけを試す山登りにする（たぶん運がいいとこれで数十万点上がる）。
差分計算
一部の追加計画を変更すると何も割り当たっていない時間に能力追加してしまって無駄が発生することがあり、それが嫌だと思ってスコア計算中にいろいろ書き変える仕様にしてしまったため（そうする必要があると思ったのかどうかよく覚えていない）、状態を変更してスコアを計算し直す際に元の状態を丸ごとコピーしなければならなくなった。ここが最初ボトルネックになっていた。結局、状態とその一時保存先へのポインタを持っておいて、保存するときは memcpy して元に戻したいときはポインタの swap をするだけで済むようにした。
利益の差分計算は、最初に工程間の依存関係を表すグラフを作り（各工程から同じ設備の次工程と同じ注文の次工程へ辺を張る）、変更の影響を直接受ける工程から到達可能な工程だけ計算し直すようにするとやや速くなる。
能力追加コストの計算は、能力追加量を変更するときに毎回更新すればよい。
スコア関数
高速化と近傍のとり方以外でスコアに効いたかなと思うのは、評価関数を少しいじったこと。最初のうちは納期遅れをやや許容する形の式にして、時間経過とともに許容度を下げて、最終的には本来のスコア関数と一致するようにする。初期に試してうまくいかなかったやつだけど、能力を上げすぎて下げる方針に変えたのでまた状況が違う。
局所最適解にはまる様子
なかなかスコアが安定しないなあと思いながらずっとやっていたのだけど、結局最後まであまり安定しなかった気がする。特に practice04 のスコアがかなりぶれるので（平均で2600万ぐらい出るが悪いときは2500万ぐらい）、解をたくさん作って様子を見てみたところ、局所解はまりポイントが（少なくとも）二つあり、それぞれ50万点ぐらいずつもっていかれる様子が観察できた。
ひとつはオーダー番号4の注文で、これは主に設備7, 8を強化すると間に合うのだが、7により比重をおくのが正解で、8のほうに比重をおきつつ10も少し強化するというのがはまる局所解のようだ。近傍をうまくとれればたぶん脱出できるのだが、複数設備にまたがった変更が必要なのが難しいところか。この状況が存在することに気付いたので二つの連続する工程の位置に同時に変更を加えるという近傍を追加してみた。
もうひとつは終盤の品目3に対する注文群で、間に合わせようとするとコストが大きくなって割に合わないので切り捨てるのが最適のようなのだが、それなりの数をまとめて切り捨ててやる必要があるためか、頑張って間に合わせるスケジュールが局所最適になって抜け出しにくいらしい。こっちは対策できていないけど、あまりこれにはまるケースは多くはなかったような気がする。
焼き鈍しのスコア変化の様子
温度を変えながらそれぞれ10回ずつ実行したときのスコア上昇の様子をグラフにしてみた。
温度が高めのときにはあるところまで下がりぎみで、途中から上昇に転じる様子が見えたので、それなら上昇を始めるあたりの温度を初期温度にすればいいのでは、と思いそうしてみたところ具合がよさそうだった。そうすればいいと思ったのは理論的な根拠があったわけではなくてなんとなくなんだけど、これって一般的にうまくいく方法なんだろうか。
その他
終了後に、初期解をそのまま返すコードを投げてみたら 669780418 が出た。2000ms ぐらいかかっていて、わりと想定外だった。手元で真面目にテストケースを作ってみていたら事前にわかっていたのかもしれない。
でも今回は前回に比べるとある程度ちゃんとデータを見ながら正しい方向に改善を考えられた気がする。テストケース作らなかったけど。
