線形計画問題

今回テックブログを書くにあたり、以下の記事を参考にしました。 qiita.com こちらの記事では、マクドナルドのメニューを対象に組み合わせ最適化問題を扱っており、内容も非常に面白く読ませて頂きました。 今回、弊社askenでも自社データを使用して食事の組み合わせ最適化問題をやってみたのでご紹介します。 はじめに こんにちは！ askenで機械学習エンジニアとして働いているyumaです。 shoku_panという名前でTwitterをやってます。 さてみなさん、弊社ダイエットアプリ「あすけん」をご存知ですか？ www.asken.jp あすけんでは、その日の食事内容を記録すると栄養士の未来（み…

線形計画問題のファルカスの補題から、強双対定理を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.9である。解答は自己流なので間違っていたらご容赦ください。強双対定理およびファルカスの補題については、下記を参照のこと。 su-butsu-kikaigakusyuu.hatenablog.com 強双対定理のステートメント： 主問題に最適解が存在すれば、双対問題にも最適解が存在し、が成り立つ。 以下、証明 双対問題はと表せる。これに実行可能解が存在するとすると、弱双対定理により、が成り立つ。 よって、強双対定理を示すには、あるがを満たすことを示せばよい。 この条件を別の表現で表すと、、、…

線形計画問題の弱双対定理から、ファルカスの補題を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.8である。解答は自己流なので間違っていたらご容赦ください。弱双対定理およびファルカスの補題については、下記を参照のこと。 su-butsu-kikaigakusyuu.hatenablog.com 以下、証明 ファルカスの補題の(1)が成り立つとき、(2)が成り立たないことを示す (1)の仮定の下では、主問題 は実行可能解を持つ。ここで、特にとすると、これの双対問題は となる。 よって、を仮定すると、このは双対問題の実行可能解となる。よって、弱双対定理より、 が成り立つ。従って、とを満たす…

線形計画法による最適化で特に重要な概念が、ファルカスの補題、弱双対定理、強双対定理である。これらにより、主問題とその双対問題を解くことの関係性が示される。 以下、これらの定理をまとめる。 ・ファルカスの補題(Farkas' lemma) 行列とベクトルが与えられる。この時、次のいずれか一方の条件のみが成り立つ。 (1) を満たす解が存在する。 (2) を満たす解が存在する。 このように二律背反な関係にある形の定理を、一般に二者択一定理と呼ぶ。なお、上記を必要十分条件の形式の主張に言い換えると、下記のようになる。 (1') を満たす解が存在する。 と、 (2') ならば、が成り立つ。 は等価であ…

2022/01/15 修正 ・有向グラフの図追加 初めに 牛ゲーとは 最大値と最短経路 具体例 初めに AtCoderの問題で牛ゲーが出たので、まとめておきます。数学的に厳密でない部分や、誤りを含む場合もありますのでご了承ください。 牛ゲーとは 以下の2つの問題があります。 という「2つの値の差分についての制約」のみからなる制約の元で、と各の差を最大化する線形計画問題 重みつき有向グラフについて、頂点から頂点にコストの有向辺があることをと表現する。 という辺がある重みつき有向グラフについて、始点から各頂点への最小コストを求める最短経路問題 この2つから得られるの最大値と、始点から頂点への最小コ…

結論 をポテンシャルとして の最大値を求める問題は、 を始点としてへの最短路長を求める問題の双対問題（dual problem）となる。 前提 線形計画問題（以下 LP ）: の行列 次元のベクタ 次元のベクタ が与えられ、 の制約下において、 objective function を最大化する 次元のベクタ を求める問題。 ポテンシャル 以下のグラフを LP で定式化することを考える。 それぞれの辺がどの頂点を繋いでいるのかを表現した 行列 を用意する。 辺 について 列 , 列 , それ以外の要素を 埋めして表現する。 さらに、 それぞれの頂点への到達コストを、 次元のベクタ それぞれの辺…

2.1 連立方程式をPythonの数理最適化ライブラリで解く 【問題】 1個120円のりんごと1個150円のなしを合わせて10個買ったら代金の合計が1440円でした、りんごとなしはそれぞれ何個買ったでしょうか。 2.2 線形計画問題をPythonの数理最適化ライブラリで解く 【問題】 ある工場で製品p,qを作っている。製品p,qを作るには原料m,nが必要 p[kg]=1m[kg]+2n[kg] q[kg]=3m[kg]+1n[kg] mの在庫30[kg],nの在庫40[kg] pは1万円、qは2万円で売れる。

問題（ざっくり） 1〜Nまで番号のついた牛がいる 牛は番号順に並んでいる 仲良しの牛a, bは距離d1以内に並べる 中が悪い牛c, dは距離d2以上離して並べる 1番目の牛とN番目の牛の距離の最大値を求めよ。 そのような並び方が存在しない場合は-1, いくらでも離せる場合は-2を出力 原文はこちら 3169 -- Layout まずはベルマンフォード法を確認する ベルマンフォード法を使って解くので、まずはこれを理解する。 ベルマンフォード法に関しての解説はこちらの記事が分かりやすかった。 2, 3回ほど以下の記事を行ったり来たりしながら、ゆっくり読むとだいたい理解できた。 Bellman-Fo…

この記事は Google Apps Script Advent Calendar 2021 の 13 日目の記事となります。 はじめに Apps Script には LinearOptimizationService という 線形計画問題 を解くためのユーティリティサービスがあります。 特殊な目的で使用する機能なので、存在を知っている方は少ないんじゃないかと思います。 今回この LinearOptimizationService が使い物になるのかの検証を兼ねて、以前作った Python と PuLP を使って実装した数独を線形計画法で解くプログラム を Apps Script に移植してみよ…

こんにちは。レトリバのリサーチャーの木村@big_wingです。 レトリバでは、研究動向・業界動向の把握のため、リサーチャーは積極的に国内学会に参加しています。 今回は第24回情報論的学習理論ワークショップ (IBIS2021)に参加しました。

はじめに 最近，最適輸送を覚えてちょいちょい使っています． 特にSinkhorn iterationを用いることで，行列計算だけで最適輸送距離をだいたい計算でき，さらに自動微分で勾配が求まるため，色々な問題のロス関数として最適輸送を使うことができます． ところで，最適輸送の式はもともと線形計画問題なので，輸送計画の行列がコストに依存しないとすると，簡単に勾配(らしきもの)を求めることができます． 以下では，自動微分を用いたときと，この方法で求めた勾配を用いたときで，実際にどの程度の差がでるものなのか気になったので，適当なデータに対して両方の手法を適用してみて結果を比較します． 結果，どちらもそ…

10/18(月) 先週の週記のページで「が、」を検索すると、なんと70件も存在した。先週は14000文字と少しだったので、実に200文字につき1回のペースでこの接続詞を使っている。文章ごとに読み直した限り、少なくとも自分にとって不自然な言葉遣いにはなっていない一方、全体として見ればあまりにも多すぎる。というわけで、今週の週記はこの接続詞をできるだけ使わないように書いてみたいと思う。逆接なら別の接続詞を採用し、そうでない微妙な用法の場合は、その文章の語順をもう一度推敲するようにしたい。 先週の週記を投稿してからは、Kaggleのチームメイトにもらったスクリプトをぶん回し、ファンの音を感じつつ布団…