数理最適化問題で柿の種を食べた話
きっかけ
母「10000円超えるように組んで」(レシートの束ﾎﾟｲｰ)
ぼく「なにこれ」
母「原信でキャンペーンやってて、10000円分のレシート集めると粗品がもらえるの」
ぼく「めんどいなぁ」
母「粗品、柿の種選べるけど」
ぼく「やるかーーーーー」(柿の種めっちゃすき(ちょろい))
↑原信のPB柿の種。個人的には亀田製菓と浪花屋製菓に次いで美味いと思う。
解いてみた
やりたいのは「金額がバラバラなレシートの束(今回は13枚)から、合計金額が10000円以上で、かつ最も10000円に近いレシートの組み合わせを出す」ということ。
単純に考えれば、13枚それぞれに対して最適な組み合わせに入るか入らないか選んでいけばよさそう。ということは 213 = 8192 通りを考えることになる。 この数を手作業でやるなんて、(ある程度枝切りできるとはいえ)とてもじゃないけどやってられない。+500円以内のやつを見つけた時点で妥協することになりそう。
などと言っていると、
母「目の前にある Mac 使いなさいよ」
傍らには YouTube の動画を再生する MacBook Air くん。ぐうの音も出なかった。
どのように解くか
人にやらせるなら「こうやれ」で済むけど、コンピュータに解かせるとなると、この問題を理解できる形に変換してあげなければならない。 このような類の問題を数理最適化問題という。
幸いにも自分は学部3年で「数理計画法」、今年の前期に「組合せアルゴリズム特論」という講義を聴講していたので、これについての知識が少々あった。せっかくなので、この知識を応用してみることにする。
※以下、こちらの記事を参考に進めました。
1. 数理モデル
解くには、問題を数理モデルで表す = 定式化する必要がある。
数理モデルには、
- 変数
- 目的関数
- 制約条件
という3つの必要な要素がある。
今回の場合、
変数: レシートそれぞれに対する組合せに含まれるかどうか(= 0 or 1) 目的関数: 変数にレシート金額をかけ合わせて足した数の最小化 制約条件: 変数×レシート金額の合計が10000円以上
2. 下準備
参考サイトにならって Python を使ってみる。触ったことないけど！
科学技術計算用のパッケージである Anaconda (ここからインストール)、数理最適化のモデラーである PuLP (pip install pulp)、
標準問題用のライブラリ(pip install ortoolpy)をインスコ。
環境は MacBook Air (Late 2015)、Python 2.7.12。
3. プログラムを書く
初めて Python を書いたので、文頭に文字エンコーディングを明示しておかないといけないのを知らなかった。
内容はこんな感じ。
4. いざ実行
yuki-albno273:python yuki$ python receipt.py (10000.0, [1, 2, 3, 5, 9, 10, 11])
一瞬で出てきた！ってか10000円ぴったりのやつあんの！？
2630 + 2446 + 1543 + 1148 + 800 + 725 + 708 = 10000
マジじゃねーか！数理最適化すげえ！
解いてみて
- 母にたいへん褒められました
- 一瞬で解けたことより1万円ぴったりの組み合わせがあったことに感動した。むしろジャストのやつなかったらブログに書いてないと思う
- 身近な問題の最適解がすぐ出てくるからみんなもやろう
- 柿の種おいしい
オチが弱いけどまとめ方が思いつかないので終わり。
