AHC 044 混合整数計画ソルバー解法

AHC 044 の 混合整数計画（MIP）ソルバーによる解法を紹介する。

Transcript

1. AHC 044 混合整数計画ソルバー解法 Kiri8128
2. サマリ • 混合整数計画（MIP）ソルバーを使った AHC 044 の解法を紹介する • 多くのケースで実行時間内に 999000 点以上のスコアを得られた • 実行時間が安定せずイテレーションを多く回せないこともあり、スコアは 安定せず平均スコアはこれよりかなり下がった • 150ケースのスコアでは本番25位相当のスコアが得られた • 本コンテストでのベストな立ち回りと言えるかは不明だが、他コンテスト でも応用が効く可能性があるので紹介する • なお筆者は MIP ソルバーについては初心者であり、高速化などの工夫に ついては十分に触れられていない可能性がある
3. 混合整数計画（MIP）ソルバーとは • 複数の1次不等式で与えられる制約条件の元で、1次式の最大値・最小値を 与える整数解を求めることができる • 筆者は Python の PuLP ライブラリを使った なお実数範囲ではより大きな解があるが、整数範囲での最大値を返してくれる（実数範囲での最適化も可能） （例） 𝑥 ≥ 0, 𝑦 ≥ 0, 2𝑥 + 𝑦 ≤ 8, 𝑥 + 2𝑦 ≤ 8 の下で 4𝑥 + 3𝑦 を最大化する整数 𝑥, 𝑦 の 組を求めよ。 この例では 𝑥, 𝑦 = 3, 2 のとき最大値 18 を取る。
4. 問題の言い換え • 最適化がうまくいけば、各頂点は 𝑇 に近い回数だけ通るはず • つまり問題は次のように言い換えられる ←ここの目標値の合計の半分が ←ここの目標値に近いと嬉しい • 逆にこれが満たされてかつ全体が連結であれば良い解が得られることが分かる 各頂点 𝑖 について、それを行き先とする集合（以下「親集合」と呼ぶ） の目標値の和の半分を自身の目標値（ 𝑇 ）に近付ける
5. 差が小さくなる候補の列挙 • 頂点ごとにそれを行き先とする集合（以下「親集合」と呼ぶ）をうまく決めたい • 頂点 𝑖 の親集合が 𝑠 のとき、ペナルティ（ 𝑝 , とする）は 2𝑇 − ∑ 𝑇 ∈ • 工夫の余地もある（後述） • 事前に1～3個からなる集合の合計を計算しておき、 𝑖 ごとにペナルティが小さくなる集合の候補を たくさん（50～100個程度）列挙しておく （イメージ）頂点1の親集合の候補の例 1 3 5 6 1 4 9 1 7
6. 条件を定式化 • 各頂点は、行き先としてはちょうど1回、親集合の元としてはちょうど2回選ばれる必要 がある • 頂点 𝑖 の親集合が 𝑠 であるときに1、そうでないときに0を取る整数変数を𝑥 , とすると、 各𝑖について ∑ 𝑥 , = 1 および ∑ 𝑥 , ∈ = 2 が成立 • この条件の元で ∑ 𝑝 , 𝑥 , を最小化する 𝑥 , たちを求めたい 1 ←ここが1になるのは1つ 1 ←ここに1が含まれるのは2つ → 条件・評価関数がいずれも1次式なのでソルバーで解ける！ ※ これが解けることは、言い換え問題の厳密解が得られることと同値
7. 少しずつ最適化 • 100 頂点を一気に最適化しようとすると PuLP では実行時間に間に合わない • 筆者環境ではパラメータによるが数分から数時間かかった • 50 頂点ごとなど、部分的に少しずつ最適化する方法を考える • 行き先頂点の集合 𝐼 について最適化する場合、 𝑖 ∈ 𝐼 について ∑ 𝑥 , = 1 、 1 ≤ 𝑖 ≤ 𝑁 に ついて ∑ 𝑥 , ∈ ≤ 2 が成立する必要がある。 • 最後のステップ以外は制約が緩いので、比較的短時間で最適解が見つかる • 𝑇 が小さい方から決めると後半で良い解が見つかりやすい まず一部だけ最適化する
8. 時間管理の難しさ • ソルバーを用いる解法ではいつ解けるかを予想しづらいので時間管理が難しい • 工夫しても2秒では1～2回の試行が限界。必ず1回まわるかも確実とは言えなかった • 候補の親集合の個数 • 候補が少なすぎると条件を満たす解が存在しない可能性が上がる • 候補が多すぎると変数が増えるため計算時間が増える • ステップの区切り方 • 一気に全部を最適化しようとすると計算時間がかかりすぎる • 細かく区切りすぎると最後のステップで解が存在しない可能性が上がる • Time Limit の設定 • PuLP では Time Limit の設定ができる • 時間切れになるとその時点での最適解を返してくれる • ただし実験すると設定した時間の 3 倍程度かかることもあり、挙動は不明 • このため「1.9秒で打ち切る」のようなことは機能せず、時間に余裕を持った回数だけ回すこ とを行った • 残り時間の 0.3 倍などで何度か試すとACを取ることはできたが、再現性は保証されない • うまい方法があるかもしれないが見つけられず
9. その他工夫 以下のような工夫が考えられる。MIPソルバーとは直接関係ないので詳細は省略 • ペナルティ • 差の絶対値そのままでなく2乗にする方法もある • 親集合の個数が少ないものを優先するペナルティとする方法もある • 𝑇 が小さく到達する必要がない頂点は予め 𝑇 = 0 としてソルバーに投げるとノイズが減らせる • 部分的に最適化した際、決まった部分については親集合をもとにその頂点の重みを更新する • 実スコアを計算して反映する • 今回は 𝐴 と 𝐵 への寄与をどちらも としたが、実際は 𝐴 の方が期待値が ほど大きいため、 + と − にするとより正確になる • 問題としては難しくなるので、ソルバーが解を見つけるまでの時間は⾧くなる可能性がある • 連結性の確認 • 今回は連結性の確認は行わなかった • ただし自己ループや 𝐴 = 𝐵 となることを禁止して、連結にならないリスクを軽減した
10. 結果と考察 • 結果 • 50頂点ごとなどにソルバーに投げると多くのケースで 99.9% （150 ケースこれが続 くと本番 1 位を超えるぐらい）以上の得点が取れる解を返してくれる • ただし実際に投げるとスコアが悪いケースの影響が大きいようで、 149,651K（本番 25位相当）が取れた • https://atcoder.jp/contests/ahc044/submissions/64110491 • 時間管理が難しいこともあり、安定した得点を出すのは筆者には難しかった • 考察・感想 • 混合整数計画ソルバーをまじめに使ったのは初めてだったが、自然な制約を追加す るだけでそれなりに良い解を出してくれるのは驚きだった • 今回の問題では実行時間の問題もあり投げるだけで最上位スコアが出るとまではい かなかったが、問題によってはうまく使えることもありそう