数理最適化による問題解決の実践的なアプローチ
本稿はRAMP数理最適化シンポジウム(2020/10/26)の講演の一部をまとめたものです．研究者に向けた講演内容ですが，数理最適化を活用したいエンジニアやコンサルタントの皆様の参考になれば幸いです．また，数理最適化に関わらず，研究者との共同研究を検討している方も一読いただけると役に立つかも知れません． はじめに 数理最適化は現実社会における意思決定や問題解決を実現するための有用な手段です．数理最適化は，下図に示すように，(1)最適化問題のモデリング，(2)アルゴリズムによる求解，(3)結果の分析・検証，(4)最適化問題とアルゴリズムの再検討という一連の手続きからなります． 数理最適化を用いて現実問題を解決するためには，まず，代表的な最適化問題とそれらに対する効率的なアルゴリズムを良く知ることが必要です．しかし，数理最適化の理論やアルゴリズムの専門的な知識があれば，それだけで現実問題を上手
3000万以上のユーザーに未経験サービスを促すギフト券配信の割当問題、数理最適化と機械学習でどう解決したか
本連載「リクルート事例で分かる数理最適化入門」では、リクルートでの数理最適化の応用事例の紹介を通して、数理最適化がどのようにビジネス応用できるのかを紹介します。連載第3回の今回と次回の第4回では、前回に引き続き、リクルート各サービスにおける数理最適化の応用事例を紹介します。 今回は2つの応用事例を紹介しますが、アルゴリズム観点では、それぞれ次のような難しさがありました。 ホットペッパービューティーでのギフト券配信対象者の決定：問題の構造は平易だが、大規模なので難しい CMの出稿割り当ての決定：問題の構造が複雑で、定式化が難しい 上記の課題は、本事例に限らず、数理最適化をビジネス応用する際に頻繁に現れます。今回紹介するアプローチが、読者の皆さんが数理最適化を用いる際の一助になれば幸いです。 ホットペッパービューティーでのギフト券配信対象者の決定 「ホットペッパービューティー」は美容関連サービ
【組み合わせ最適化入門】カンファレンスのタイムテーブル決めをマッチング問題としてGoogle OR-Tools/Pulp/munkresで解く - フリーランチ食べたい
PyCon JPの運営メンバーとして自分は、昨年度のPyCon JP 2018のタイムテーブル決めに組み合わせ最適化問題を用いました。ちなみに最終的なタイムテーブルはアルゴリズムで算出された結果を人間がレビューして調整しています。 昨年度は時間の制約があり、いくつか反省点があったので今年は改善したいと考えています。 pyconjp.blogspot.com そういうわけで事前調査も兼ねて、カンファレンスのタイムテーブル決めを組み合わせ最適化問題として考え、それをPythonのライブラリを使って解く方法を書きたいと思います。 解きたい問題 カンファレンスのタイムテーブル決めでは下図のように部屋と時間が決まっていて、そこのトークを割り当てていくことが一般的です。 このとき、部屋の大きさ、時間帯やトークの内容が全く同一であれば何も考えずに隅から配置していけば良いのですが、現実には以下のような条件
しばらく更新していない間にいいね/ブックマークがじわじわ増えててとても励みになります(*´ω`*)。 最近は研究関連の勉強をしているので、ブログに書けないネタばかりで…。 月1くらいで投稿できるようにしたいですね。 さて。このブログでは以前、数理最適化の勉強メモとして最適性条件, 最急降下法, ニュートン法についてまとめました。 数理最適化の勉強メモ − 解析的な解法 / 最適性条件 / 勾配法がうまくいかない条件 - かみのメモ 数理最適化の勉強メモ − 最急降下法 / ニュートン法の原理と特徴 - かみのメモ 今回の記事では問題設定を少し変えて、微分可能な制約なし非線形最小二乗問題の解法であるLevenberg-Marquardt法についてまとめてみます。 いつもの注意書きですが、筆者はコンピュータビジョンが専門で、数学や数値計算の専門家ではありません。 間違いがある可能性も割と高いの
本連載「リクルート事例で分かる数理最適化入門」ではリクルートでの数理最適化の応用事例の紹介を通して、数理最適化がどのようにビジネスに応用できるのかを紹介します。連載初回の前回は、数理最適化の概要、リクルートにおける4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方などを解説しました。 連載第2回の本稿では、数理「最適化のビジネス応用事例の一つとして、リクルートの製品「Airレジオーダー」の「キッチンモニター」で利用されている調理順並べ替えによる提供遅れ防止機能を紹介します。 なお記載している内容は公開可能な範囲で簡略化しており、一部ロジックは現実のAirレジオーダーと異なる点があることをご了承ください。 Airレジオーダーのキッチンモニターとは Airレジオーダーは弊社リクルートで提供している、飲食店の煩雑になりがちな注文を一元管理し、最適なタイミングでの調理、提供をサポート
研究開発部の浅野です。普段は画像やヘルスケアデータを扱うことが多いのですが、最近シフトスケジューリング問題に興味をもって学び始めたので、その内容を少しご紹介したいと思います。シフトスケジューリング問題とは、人員の配置基準や働く人の希望、能力、相性、業務負荷などを加味しながらある一定期間(1ヶ月など)の勤務シフト表を作成する問題です。看護師のナーススケジューリングが有名ですが、保育士のシフト作成も多くの園長先生が頭を悩ませていることの一つです。今回はこの問題を最適化問題としてモデル化・定式化して実際に解いてみたいと思います。 最適化問題は、制約条件を満たす解の中で、目的関数を最小（最大）にする解を求めるもので、次のように定義されます。 \begin{align} minimize \quad &f(x): &目的関数\\ subject \; to \\ &g(x)>= 0: &不等式制約条
【連載】ブレインパッドの数理最適化ブログ（目次） - Platinum Data Blog by BrainPad
本記事は、当社オウンドメディア「Doors」に移転しました。 約5秒後に自動的にリダイレクトします。 数理最適化技術は、「データ活用の促進を通じて持続可能な未来をつくる」を企業ミッションとするブレインパッドにとって、必須の注力技術の1つです。 2020年10月1日、大阪大学に、ブレインパッドほかから寄付を受けた「大阪大学数理最適化寄附講座」が開設されました。同講座の教授を務められるのは、数理最適化技術の研究で大変著名な梅谷 俊治先生です。 これを機に、ブレインパッドも数理最適化技術に関するナレッジをさらに＆どんどん高めていこうということで、この公式ブログでも数理最適化に関する連載をスタートします！ こんにちは。CDTO（Chief Data Technology Officer） の太田です。 大阪大学にブレインパッドが寄付を実施し、「大阪大学数理最適化寄附講座」が開設されました。 それを
The Qiita Advent Calendar 2020 is supported by the following companies, organizations, and services.
2023/09/12実施の、大阪大学 大学院情報科学研究科 数理最適化寄附講座 最終報告シンポジウムにおける、西村の資料です。
PuLPによるモデル作成方法
PuLPによるモデル作成方法¶ Pythonで線形最適化を行うには、PuLPライブラリーを使用します。 PuLPは、COIN-ORプロジェクトで開発されたものです。 参考：COIN-OR PuLPのインストール¶ コマンドプロンプトで、pip install -U pulpでできます（macOSではpip3 install -U pulp）。 モデル作成の手順¶ モデル（LpProblem）の作成 変数（LpVariable）の作成 目的関数の設定 制約条件の追加 ※ 1と2の順番は逆でも構いません。3と4の順番も逆でも構いません。また、3と4はなくても構いません。 問題とモデルの違い¶ 問題には、2種類の意味があります。 解決したいと思っている課題。目標と現実の違い。 答えを想定している問い。試験の問題など。最短路問題のように名前がついている問題の多くは、この問題。 「数理的アプローチに
リクルートが取り組む「競技プログラミング」「数理最適化技術」プロジェクトの舞台裏──RECRUIT TECH MEETUP #4 - TECH PLAY Magazine
リクルートが取り組んでいるテーマや技術の最先端を紹介する「RECRUIT TECH MEETUP」。4回目となる今回のテーマは、競技プログラミング・数理最適化技術だ。各プロジェクトを率いたエンジニアが舞台裏、技術や組織体制などについて語った。 ■登壇者プロフィール 株式会社リクルート データ推進室 シニアデータアプリケーションエンジニア 田中 伸明氏 2016年リクルートコミュニケーションズ（当時）に中途入社。様々なデータ活用系のアプリケーションに、インフラからフロントエンドまで幅広く関わっている。2021年より、人材採用サービスでのレコメンド基盤構築に従事。 株式会社リクルート データ推進室 シニアデータサイエンティスト 西村 直樹氏 2015年リクルートに新卒入社。じゃらん、ホットペッパーグルメなどのサービスにおけるデータ活用プロジェクトの推進、分析などを担当。2021年に書籍「Pyt
機械学習で予測したり、分類したりという分析手法が大流行している中で数理最適化は今となってはかゆいところに手が届く技術です。一時期は強化学習があるからいらないんじゃないか、と考えたこともあったのですが、実用性を考えると即座に実装できたり、運用のしやすさといった点で数理最適化の強さが活きる局面はまだまだ多いでしょう。特に最近では量子コンピュータの実用化の研究がされており、もし普及した場合には間違いなく再注目される技術です。 今回は数理最適化をする上で知っておきたい定式化テクニックをまとめました。たぶん数式は間違ってないですが、もしかしたら間違っている可能性もあります。 論理積 バイナリ変数$x, y$の積は線形な式のみで$xy$と等価な式を作れます。 z \geq x + y - 1 \\ x \geq z \\ y \geq z \\ x, y, z \in \left\{0, 1\righ
数理最適化: Optimization Night #1 https://connpass.com/event/148735/ の発表資料です。 デモで用いた Jupyter Notebook は https://gist.github.com/AseiSugiyama/1fa1e4a2c3e90e1393f4ff398c473143
今度こそ？使い物になるフリーの数理最適化（混合整数最適化）ソルバー（付きインターフェース） Python-MIP - Qiita
Input generation Instance generation Optimization Welcome to the CBC MILP Solver Version: devel Build Date: Nov 15 2020 Starting solution of the Linear programming relaxation problem using Primal Simplex Coin0506I Presolve 90001 (-299) rows, 178802 (-299) columns and 536107 (-598) elements Clp0030I 13 infeas 3936.1919, obj 0.73453941 - mu 111.08889, its 52, 82471 interior Clp0030I 23 infeas 336.48
最適化問題の「P」と「NP」をちゃんと理解したい
問題のクラス \rm P と \rm NP についての理解が曖昧なことに気づいたので、ちょっと勉強しました。忘れてもいいようにメモしておきます。 計算量の話 計算量には大きく時間と空間の2通りの評価基準があります。 時間計算量 / 時間量 計算を終えるまでに要する基本演算の回数。 空間計算量 / 領域量 計算の途中経過を一時保存するのに要する記憶領域。 計算量の増加の「速さ」 アルゴリズムの「良さ」を評価する指標の一つに、入力されたデータの長さ N が大きくなるとき、要求される時間 (または領域) がどれほどの速さで増加していくかというものがあります。 微分積分学における「極限」の概念によれば、多項式は平方根よりも速く、指数関数は多項式よりも速く、階乗は指数関数よりも速く発散します: {}^\forall k, a \in \mathbb R_+, {}^\exists \bar N: \
人工知能（AI）というと機械学習や深層学習が注目されがちだが、実はそれはAIの半分にすぎない。あとの半分、いわば「アナザーAI」は企業の生産計画や物流などで重要な役割を果たす「最適化AI」だ。最適化AIを実現するための技術が、「焼きなまし法」や「ビームサーチ」などの「ヒューリスティックアルゴリズム（メタヒューリスティクス）」である。この連載では、競技プログラミングサービスを提供しているAtCoderの高橋直大社長が、アルゴリズムに対する深い知識を生かし、最適化AIを活用している企業を訪ねて取り組みを探っていく。 今回は趣向を変え、最適化AI（数理最適化）による産学連携を進める大阪大学大学院数理最適化寄付講座の梅谷俊治教授に、数理最適化の意義やその活用などについて聞いた。（聞き手は高橋 直大＝AtCoder）。
書籍「Pythonではじめる数理最適化」の改訂版のお知らせ-数理最適化問題の行列表現の実装に入門- - Qiita
数理最適化Advent Calender 2023の1日目の記事です。 本記事は、書籍Pythonではじめる数理最適化の改訂版の発行についてお知らせするとともに、執筆陣が最終原稿のチェックを頑張るぞ！という決意表明をするものです。前半では、本書の簡単な紹介と読者からのフィードバックを紹介し、なぜ改訂するのかについてお伝えします。 技術的な内容だけに興味がある人は、7章から数理最適化問題の行列表現の実装の紹介から読み進めてください。 書籍「Pythonではじめる数理最適化」とは 4人の実務家（岩永二郎、西村直樹、田中一樹、石原響太）によって執筆されており、オーム社から2021年に出版されました。 本書は、Pythonを用いた数理最適化の入門書です。数理最適化の書籍は数多くありますが、ほとんどが理論書であるため、初学者にとっては数学の壁があり、実務家にとっては社会実装のイメージがしにくく、挫折
はじめに ※私は数理最適化で某社内の課題解決に取り組んでいる者ですが、本稿の内容は私の所属している会社での仕事に関連するものではありません ※ChatGPTに会社の機密情報は尋ねないようにしましょう！ 数理最適化ってデータ分析タスクと比べてコモディティ化が進んでいないので、専門家でないとまだまだ大変ですよね？ 本稿ではChatGPTを用いて数理最適化プロジェクトのタスクの一部を補助してもらえないか、検討してみました。 ヒアリングと定式化をChatGPTにお願いする 梅谷先生の著書「しっかり学ぶ数理最適化」では、課題解決の手順を４つのステップに分けています。 現実問題を最適化問題に定式化する アルゴリズムによって求解する 計算結果を分析・検証する 最適化問題とアルゴリズムを再検討する 一般的な実務を考えると、１つ目のステップは以下の3つに分解できると思います。 担当者へのヒアリング データ収
機械学習と数理最適化 - Qiita
#機械学習と数理最適化 「コンビニのお店×商品ごとに需要予測がしたいんです」 → 機械学習/統計モデリングっぽい話 現象の予測・解明 「コンビニのお店×商品ごとに需要予測に基づいて利益の最大化をしたいんです」 → 数理最適化っぽい話 利益の最大化(現象が解明した後にKPIの最大化・最小化) 機械学習と数理最適化の間：バンビット問題（強化学習）というのもある #意思決定のステップとアナリティクスの到達段階 データサイエンス/AI/アナリティクスといってもレベルは様々である 意思決定のステップ ①集計（何が起きるのか） ②説明（何故起きたのか） ③予測（何が起きるのか） ④意思決定（何をすればいいのか） ⑤行動（実際の行動） アナリティクスの到達段階 ①記述的アナリティクス ②診断的アナリティクス ③予測的アナリティクス ④処方的アナリティクス（AIによる意思決定支援） ⑤処方的アナリティクス
/リンク集
GROWI 4.5.23 -/ Shortcuts × Global shortcuts Open/Close shortcut help: + / Create Page: C Edit Page: E Search: / Show Contributors: Konami Code ↑ ↑ ↓ ↓ ← → ← → B A Mirror Mode: Konami Code X X B B A Y A Y ↓ ← Editor shortcuts Indent: Tab Outdent: Shift + Tab Save Page: + S Delete Line: + D Comment Form shortcuts Post: + Delete Line: + D
リクルート事例で分かる数理最適化入門
リクルートにおける数理最適化の応用事例を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介する連載。最終回は趣向を変え、リクルートのデータサイエンティストが大阪大学の梅谷俊治教授に数理最適化を活用する上でのポイントを聞いた。
はじめに 逐次更新による最適化 大枠 勾配法 数式 勾配法コード例 ニュートン法 数式 ニュートン法のコード例 はじめに 最近、しっかり学ぶ数理最適化を購入しました。 しっかり学ぶ数理最適化 モデルからアルゴリズムまで (KS情報科学専門書) 作者:梅谷 俊治発売日: 2020/10/26メディア: 単行本（ソフトカバー） 1章→3章と読んでいく中で、元々馴染みの深い連続最適化の極々基本的な手法である勾配法とニュートン法を試してみました。実装はJAXを使っています。こいつは現状、最高の自動微分ライブラリだと思っております（深層学習ライブラリという観点ではPyTorchの方が今の所使いやすい）。 普通、機械学習では二次微分なんてパラメータが多すぎてまともに計算できる見込みがないので、純粋なニュートン法なんて絶対に使わないのですが、その圧倒的な性能の高さを確認し、兎にも角にも勾配法の弱さを確認
DX実現を加速する数理最適化コンサルティングの可能性
印刷する メールで送る テキスト HTML 電子書籍 PDF ダウンロード テキスト 電子書籍 PDF クリップした記事をMyページから読むことができます サマリー 数理最適化とは、問題を目的関数と制約条件の形に整理し、数理的な手法を用いて、制約条件を満たしつつ目的関数の最大化（ないし最小化）を行う営みである。まだ、マイナーな手法であるが、問題によっては機械学習や人工知能（AI）を用いるまでもなく、鮮やかに解決できる可能性を秘めている。本稿ではグループ分け問題の解決により業務負担を大きく軽減した事例に触れる 数理最適化の活用に当たっては、手法ありきで進めるのではなく、さまざまな手法の中から有効性を判断して、問題解決の枠組みを選択すべきである。同時に、現場に真に役立つ問題解決のために、現場に根差した問題を定義し、実務の制約条件を織り込んでモデル化することが重要である 開発した手法が現場の実業
メタデータをダウンロード RIS形式 (EndNote、Reference Manager、ProCite、RefWorksとの互換性あり)
第3回：はじめての配送計画の列生成法【ブレインパッドの数理最適化ブログ】 - Platinum Data Blog by BrainPad
本記事は、当社オウンドメディア「Doors」に移転しました。 約5秒後に自動的にリダイレクトします。 ブレインパッドの社員が「数理最適化技術」に関して連載するこの企画。 第3回は、当社のデータサイエンティストが、与えられた条件を満たしつつトラックの移動距離が最小になるような配送計画の問題を題材に、列生成法をご紹介します。 こんにちは。アナリティクスサービス部の岡﨑です。 この記事では 【連載】ブレインパッドの数理最適化ブログ（目次） - Platinum Data Blog by BrainPadの第3弾として、配送計画問題を題材にして列生成法をご紹介いたします。数理最適化に若干の心得があるが列生成法を知らない読者*1が「自分でも列生成を試してみたい！」と感じていただくことを目標に、本記事を執筆しています。 はじめに 容量制約付き配送計画問題 問題設定 方針 定式化 全ルート列挙 列生成法
整数計画法メモ トップページへ戻る 本ページのURLが https://www.tuat.ac.jp/~miya/ipmemo.html から https://web.tuat.ac.jp/~miya/ipmemo.html へ変更になりました． それに応じて，本ページからリンクされているダウンロード可能なファイルについても，URLが変更になっています． はじめに このページには，整数最適化問題（整数計画問題）をソルバーで解く際に，知っていると役に立つかもしれない情報を雑多に記しています． 整数最適化（整数計画法）は強力な最適化手法の一つなのですが，「実際に解きたい時に日本語の情報があまり無い」と耳にしたのがこのページを作ったきっかけです． おことわり このページに書いてある情報は無保証であり，筆者は一切の責任を持ちません． 自己責任でご利用ください． もちろん，なるべく正しいことを書くよ
When training machine learning models, and deep networks in particular, we typically use gradient-based methods. But if we require the weights to satisfy some constraints, things quickly get more complicated. Some of the most popular strategies for handling constraints, while seemingly very different at first sight, are deeply connected. In this post, we will explore these connections and demonstr
はじめに 整数計画問題における実行可能間の距離とProximate Optimality Principle 可視化方法 インスタンス ソルバ 可視化結果 考察 おわりに 参考文献 はじめに 組合せ最適化問題に対するメタヒューリスティクスの設計では，解くべき問題に対して「良い解同士は似通った構造をもっている」という仮定をしばしばおきます[1]．この仮定はProximate Optimality Principle（以降，本文ではPOPと略記）とよばれ，メタヒューリスティクスの基本戦略である「探索の集中化」の前提になっています．多くのメタヒューリスティクスは探索の集中化に加え「探索の多様化」とよばれる戦略を適切に組み込むことで高い探索性能の実現を図っています[1][2]． 本記事では，私がとくに興味をもっている整数計画問題に話を限定し，実行可能解の分布の可視化を通して，POPの成立性とメタヒ
最近は，多くの企業が数理最適化の活用に興味を持つようになり，産学連携の機会が急増しています．一方で，企業に数理最適化の専門家は少なく，大学から輩出できる人材にも限りがあるため，実務における数理最適化の活用はごく限定された範囲にとどまっているのが現状です．本講演では，多くの企業が抱える実務の各段階における問題解決の支援を通じて，企業において数理最適化の専門家を育成し，基幹事業において数理最適化を活用する枠組みの創出を目指す，数理最適化寄附講座の取り組みを紹介します．
blue2718 on Twitter: "東工大の数理最適化の学習用テキストが公開されている。 https://t.co/dFzttd6Oe8"
東工大の数理最適化の学習用テキストが公開されている。 https://t.co/dFzttd6Oe8
latest update: 2022.05.30 2022.05.30 空間計算量をなぜあまり考えないのかの理由の説明が間違っていたので修正しました \[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \] 力任せ探索 卵の問題 力任せ探索より効率的に 二分探索 判定・探索・最適化 バーの喧嘩抑制問題 グラフ理論 判定問題の重要性 自己リダクション 探索問題への帰着 判定問題への帰着 計算量 ビッグオー記法 P NPとco-NP オンライン最適化問題 組合わせゲーム的な問題 NPの定義
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
数理最適化の勉強メモ − Levenberg-Marquardt法 - かみのメモ
料理来るの遅いなぁ――数理最適化で飲食店のビジネス課題「調理遅れ」を解決できるのか
シフトスケジューリング問題 (入門) - ユニファ開発者ブログ
数理最適化のカレンダー | Advent Calendar 2020 - Qiita
リクルートにおける数理最適化の 活用事例と産学連携の取り組み
意外と役に立つ最適化問題の定式化手法 - Qiita
Google OR Tools で数理最適化に入門する
最適化AIは機械学習の次のステージ、普及のために大学ができることとは
ChatGPT(GPT-4)と数理最適化に関するヒアリングのロールプレイをしてみた - Qiita
数理最適化でベストな意思決定を。『Excelで手を動かしながら学ぶ数理最適化 ベストな意思決定を導く技術』発売／データサイエンス入門としても使える一冊【Book Watch/ニュース】
JAXとPyTorchで勾配法とニュートン法を試す - HELLO CYBERNETICS
説明可能な機械学習のための数理最適化―混合整数線形最適化に基づく反実仮想説明法―
https://twitter.com/developer_quant/status/1527643067804942337
宮代 隆平 の web ページ（整数計画法メモ）
Optimizing with constraints: reparametrization and geometry.
https://www.ism.ac.jp/~mirai/opta/tsukuba19keynote.pdf
整数計画問題における実行可能解の分布の可視化 - 数理最適化・進化計算に関する雑記帳
Mathematical Optimization for Real Applications
離散最適化とはどんな分野か - パンの木を植えて