指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
はじめに 本書は，筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである． 本書は，Jupyter Laboで記述されたものを自動的に変換したものであり，以下のサポートページで公開している． コードも一部公開しているが，ソースコードを保管した Github 自体はプライベートである． 本を購入した人は，サポートページで公開していないプログラムを 圧縮ファイル でダウンロードすることができる． ダウンロードしたファイルの解凍パスワードは<本に記述>である． 作者のページ My HP 本書のサポートページ Support Page 出版社のページ Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待― Pythonによる実務で役立つ最適化問題100+ (2) ―割当・施設配置・在庫最適化・巡回セールスマン― Pythonによる実務で役立つ
こんにちは、クックパッドマート流通基盤アプリケーション開発グループのオサ（@s_osa_）です。 生鮮食品の EC サービスであるクックパッドマートでは、「1品から送料無料」をはじめとするサービスの特徴を実現するために、商品の流通網を自分たちでつくっています。 このエントリでは、商品をユーザーに届けるための配送ルートを自動生成している仕組みについて紹介します。 解決したい問題 配送ルートとは クックパッドマートにはいくつかの流通方法がありますが、ここでは「ステーション便」と呼ばれるものについて解説します。他の流通方法などを含む全体像が気になる方は以下のエントリがオススメです。 クックパッド生鮮 EC お届けの裏側 2022 年版 - クックパッド開発者ブログ ステーション便では、ハブと呼ばれる流通拠点からユーザーが商品を受け取りに行く場所であるステーションへと商品を運びます。東京都、神奈川
数理最適化案件とAI/機械学習案件とのアナロジー 「やってみなければわからない」中で僕たちDSはどうするか本記事では表題に関して、脳筋系ゆるふわVTuberこと入社2年目DSの岡部がお送りいたします。（DS=データサイエンティスト） 発... ◆【理論・実践】（2021年時点で）オススメの参考書 最大のアップデートはこちらの2冊です。参考書は時代の流れに合わせていいものが出てくるものですね。もちろん過去の参考書にもいいものはたくさんありますが、日進月歩の分野である以上、新しいものに軍配が上がりやすい構図はあると思います。 しっかり学ぶ数理最適化 モデルからアルゴリズムまで Pythonではじめる数理最適化： ケーススタディでモデリングのスキルを身につけよう 以下それぞれの所感です 【理論】「最適化分野全般を知るための『最適解』」とも言われている教科書 僕が最適化にハマっていた当時は様々な本
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
数理最適化ことはじめ / Introduction to Mathematical Optimization
本スライドでは、数理最適化を概観し、基本的な問題とその解き方を分かりやすく解説することを目標にしています。数理最適化に興味を持っていただければ嬉しいです。 【目次】 1 章 数理最適化とは（p.2～20） 2 章 連続最適化問題（p.21～133） 3 章 離散最適化問題（p.134～238） 4 章 まとめ（p.239～248）
何でも微分する
IBIS 2023 企画セッション『最適輸送』 https://ibisml.org/ibis2023/os/#os3 で発表した内容です。 講演概要: 最適輸送が機械学習コミュニティーで人気を博している要因として、最適輸送には微分可能な変種が存在することが挙げられる。微分可能な最適輸送は様々な機械学習モデルに構成要素として簡単に組み入れることができる点が便利である。本講演では、最適輸送の微分可能な変種とその求め方であるシンクホーンアルゴリズムを紹介する。また、この考え方を応用し、ソーティングなどの操作や他の最適化問題を微分可能にする方法を紹介するとともに、これらの微分可能な操作が機械学習においてどのように役立つかを議論する。 シンクホーンアルゴリズムのソースコード：https://colab.research.google.com/drive/1RrQhsS52B-Q8ZvBeo57vK
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
こんにちは。数理最適化ギルドでエンジニアをしている加藤です。 ある自社プロダクトの開発を通じて因果推論について勉強する機会がありました。因果推論は統計の分野ですが、その中で数理最適化の技術が使えることを知り、とても面白かったのでその内容をシェアしようと思います。具体的には組合せ最適化問題のひとつである最小カット問題が、因果推論のタスクの一部である識別可能性に利用できるという話をします。 前半は因果推論についての概説で特に予備知識は仮定していないです。後半は計算時間やネットワークフローなどのアルゴリズムを知っていると読みやすいと思います。 因果推論とは 因果推論の目的 統計的因果推論とは事象の間の因果効果を実験データや観測データから推定することを目的とした統計学の一分野です。単に因果推論といった場合は統計的因果推論を含むより広い概念を指すことがありますが、簡単のため以下では因果推論といえば統
数理最適化 Advent Calendar 2022 の記事です。 何の話かと言うと Pythonではじめる数理最適化 ―ケーススタディでモデリングのスキルを身につけよう― 作者:岩永二郎,石原響太,西村直樹,田中一樹オーム社Amazon 上記の書籍の第7章では、次のような問題を取り扱っています。 細かい点は書籍に譲りますが、まず、生データとして次のようなデータが与えられます。 これは、あるショッピングサイトの利用履歴を集計して得られたもので、あるユーザーが同じ商品を閲覧した回数（freq）と、その商品を最後に閲覧したのが何日前か（rcen）の2つの値から、そのユーザーが次にサイトにやってきた時に、再度、その商品を閲覧する確率（prob）を実績ベースで計算したものです。実績ベースのデータなので、ガタガタしたグラフになっていますが、理論的には、 ・freq が大きいほど prob は大きくな
本講演では，数理最適化の基本的な枠組みを概観することで，数理最適化を本格的に学習するきっかけを与えることを目的にしています． このスライドでは，双対問題をはじめとする多くの重要な概念の説明を省略しています．もし，このスライドを読み終えて数理最適化を深く理解できたと感じたなら，それはたぶん気のせいです． （追記2020/9/5）本スライドの元ネタとなる「しっかり学ぶ数理最適化」が10月下旬に講談社より出版されます．
これはどんな記事? 本記事は、私がヒューリスティック関連の知識をまとめることになった際に作成したJupyter Notebookを、Qiitaの記事へと改変したものです。 前提としてこれは梅谷俊治先生の「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」という本(以下、教科書と表記)の内容に準拠しています。 そしてその内容の多くは、ありがたいことにネット上の様々な形で公開されており、梅谷先生によるスライド1やスライド2、日本オペレーションズ・リサーチ学会(以下、ORと表記)での記事1や記事2、そしてORの他の方の記事1や記事2などでも類似した内容を見ることが可能です。 (そしてそれ故に、本記事を公開させて頂いています。流石に本家の方がネット上で公開されていない内容を書くのは、例え権利的に問題がないとしても気が引けるので……) また、この記事は、それらの内容を踏まえた上で、私がネット上の様
グラフ最適化をマスターしよう！ - Qiita
はじめに グラフ最適化（Graph Optimization）は、パラメータをグラフ構造で表現し、最適化問題を解決する手法です。特にロボティクスなどの領域で広く活用されています。 以下に、グラフ最適化の応用例をいくつか挙げます。 Visual SLAMやSFMのバンドル調整（Bundle Adjustment）問題 Graph SLAMのループクロージング問題 経路計画問題(TEB, ebandなど) 実際のアプリケーションでは、ceresやgtsam、g2oなどのグラフ最適化ライブラリを利用することで、グラフ最適化問題を解決することができます。しかし、グラフ最適化の内部原理を理解していないと、性能の向上や課題の解決が困難になることが多いです。 筆者自身は、グラフ最適化の理解を深めるため、独自のグラフ最適化ライブラリをPythonで実装したことがあります。g2oなどの大規模なOSSと比較し
実務につなげる数理最適化
はじめに はじめまして、2023年10月にシニアリサーチャーとして入社したアドバンスドテクノロジーラボ（ATL）の梅谷俊治です。2023年9月まで、大阪大学大学院情報科学研究科にて数理最適化寄附講座教授を務めていました。 本記事では、リクルートのデータ推進室における数理最適化を活用した問題解決の取り組みをご紹介します。 数理最適化は、与えられた制約条件の下で、目的関数を最小（もしくは最大）にする最適化問題を通じて、現代社会における意思決定や問題解決を実現する数理技術の一つです。 近年では、機械学習によるデータ分析や予測の技術開発が進み次々と実用化されています。数理最適化は、それらのデータ分析や予測の結果を踏まえた上で意思決定や計画策定を実現する問題解決における出口を担当する技術です。例えば、オンライン広告などカスタマーに商品を推薦するレコメンデーションでは、機械学習を活用してカスタマーの商
数理最適化の参考書
専門家が執筆した数理最適化の書籍を紹介しています． 適当に書籍を並べただけですので内容については各自で確認をお願いします． 数理最適化全般 数理最適化の概観を知りたい人向け 穴井宏和，数理最適化の実践ガイド，講談社，2013． 数理最適化を現実問題の解決に活用するプロセスを知りたい人向け 岩永二郎，石原響太，西村直樹，田中一樹，Pythonではじめる数理最適化（第2版） ―ケーススタディでモデリングのスキルを身につけよう―，オーム社，2024． 三好大悟，Excelで手を動かしながら学ぶ数理最適化：ベストな意思決定を導く技術，インプレス，2023． 株式会社ビープラウド，PyQチーム，斎藤努，Pythonで学ぶ数理最適化による問題解決入門，翔泳社，2024． 数理最適化を初めて学ぶ人が手に取る入門書 福島雅夫，新版 数理計画入門，朝倉書店，2011． 久野誉人，繁野麻衣子，後藤順哉，数理最
エンジニアからデータサイエンティストへのキャリアチェンジのお供に「Pythonではじめる数理最適化」は良い教科書になるかもしれない - Lean Baseball
良い本良い魚良いお酒でした 秋も深まり, 緊急事態宣言が解除された今日このごろ, お酒を片手に読書がだいぶ捗るようになりました📖 酒と魚の話はさておき*1, 長いこと友人かつRetty時代の元同僚である岩永さん（とその仲間たち）*2が, 「Pythonではじめる数理最適化」なる書籍を出しました*3. Pythonではじめる数理最適化 ―ケーススタディでモデリングのスキルを身につけよう― 作者:岩永二郎,石原響太,西村直樹,田中一樹オーム社Amazon エンジニアな自分が読んだ感想として, 数理最適化でモデリングをする人だけでなく, エンジニアからデータサイエンティストへのキャリアチェンジを考えている人も必読なのでは? と思ったので, メモ代わりに感想（とちょっとしたコンテンツ）を残したいと思います. TL;DR 現実の課題・問題（主に仕事）をデータサイエンティストとして解きたい方の参考書
「数理最適化」とは――4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方：リクルート事例で分かる数理最適化入門（1） リクルートにおける数理最適化の応用事例の紹介を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介する連載。初回は、数理最適化の概要、リクルートにおける4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方などについて。 近年多くの企業で、ビジネスでのデータ活用が当たり前になっています。中でも機械学習を用いた成功事例については、耳にしている読者の方も多いと思います。一方で、同じくデータ活用の技術である「数理最適化」は、さまざまな領域で成果を上げているにもかかわらず、その実態について知っている人はあまり多くないようです。 本連載ではリクルートにおける数理最適化の応用事例の紹介を通じて、数理最適化とは何か、どのようにビジネスに応用できるの
みるか on Twitter: "先日話題に上がった数理最適化のとんでもないサイト、豊富な組み合わせ最適化問題に対する概略およびコードのみならず、解説動画まで公開されていて脱帽。 Python言語による実務で使える100+の最適化問題 https://t.co/QttWNhxZZD"
先日話題に上がった数理最適化のとんでもないサイト、豊富な組み合わせ最適化問題に対する概略およびコードのみならず、解説動画まで公開されていて脱帽。 Python言語による実務で使える100+の最適化問題 https://t.co/QttWNhxZZD
今回テックブログを書くにあたり、以下の記事を参考にしました。 qiita.com こちらの記事では、マクドナルドのメニューを対象に組み合わせ最適化問題を扱っており、内容も非常に面白く読ませて頂きました。 今回、弊社askenでも自社データを使用して食事の組み合わせ最適化問題をやってみたのでご紹介します。 はじめに こんにちは！ askenで機械学習エンジニアとして働いているyumaです。 shoku_panという名前でTwitterをやってます。 さてみなさん、弊社ダイエットアプリ「あすけん」をご存知ですか？ www.asken.jp あすけんでは、その日の食事内容を記録すると栄養士の未来（みき）さんからアドバイスをもらえます。点数も出るので、高得点をとることがモチベーションになっている方もいらっしゃると思います。 もちろん僕も使っています。ちなみに今年のお正月はこのような結果になりました
0. 忙しい方へ SAMは損失が最小かつその周辺が平坦であるようなパラメータを目指すよ SAMは次の3ステップだよ パラメータ$\mathbf{w}$の周辺で最大の損失をとる$\mathbf{w+\hat{\epsilon}(w)}$を求めるよ $\mathbf{w+\hat{\epsilon}(w)}$における損失を求めるよ 2.の損失に対する勾配でパラメータ$\mathbf{w}$を更新するよ SAMは一言で言ってしまえば、「パラメータ周辺での最大の損失を求めて、それが下がる方向でパラメータを更新する」ものだよ ImageNetやCIFARを含む9つの画像分類データセットでSoTAを更新したよ ラベルへのロバスト性も高いよ 1. SAMの説明 SAMは至ってシンプルです。というのも、今までは損失が最小になるパラメータを学習させていました。ただ、SAMは損失が最小かつその周りも平坦となっ
1. はじめに 最初に、本記事ではどのようなトピックを扱うのかについて、少し説明したいと思います。 1-1. 本記事で扱うトピック 21 世紀になり、IT 化が急速に進む今、現実社会ではいろいろなものが最適化されて動いています。これを形作るプログラミングの現場でも、例えば以下のような問題を考えたり、あるいは実際に使ったりすることもあるのではないでしょうか1。いくつか例を挙げてみましょう。 例 1. コイン問題：特定の金額をぴったり支払うために、最小で何枚の硬貨が必要か？ 例 2. 最短経路問題：地図上の A 地点から B 地点までに行くのに、最短で何メートル歩く必要があるか？ 例 3. 箱詰め問題：長方形の箱に、できるだけ多くの荷物を敷き詰めたい 例 4. 数分割問題：「できるだけ合計の値が近くなるように」2 つのグループに分割したい このように、いろいろな問題があります（もちろん名前を覚
最適輸送と自然言語処理
2022-03-14, 言語処理学会 第28回年次大会でのチュートリアル「最適輸送と自然言語処理」のスライドです。当日利用版から増補改訂しました。 講演動画 (YouTube)
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Python言語による実務で使える100+の最適化問題 | opt100
Python言語による実務で使える100+の最適化問題 | opt100
クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ
「そうだ、数理最適化、やろう。」ってなった時にめっちゃ参考になったリンク集＆参考書｜CO-WRITE
輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
因果推論とグラフ理論 - エクサウィザーズ Engineer Blog
数理最適化と機械学習を比較してみる - めもめも
Mathematical Optimization in 60 minutes
しっかり学ぶ数理最適化 ヒューリスティック編 - Qiita
「数理最適化」とは――4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方
線形計画法使ってあすけんで100点とってみた - asken テックブログ
SoTAを総なめ！衝撃のオプティマイザー「SAM」爆誕&解説！ - Qiita
直感でわかる、ヒューリスティック問題の羅針盤 ～貪欲法から山登り法まで～ - Qiita