高速SATソルバーの原理と応用
高速SATソルバーの原理 鍋島 英知 nabesima@yamanashi.ac.jp 山梨大学 湊離散構造処理系プロジェクトERATO セミナー はじめに SAT = 命題論理式の充足可能性を判定する問題 計算機科学における最も基本的で本質的な組合せ問題 90年代末頃からSAT ソルバーの性能が飛躍的に向上 数百万変数からなる大規模な問題が求解可能に システム検証，プランニング，スケジューリング，定理証 明，制約充足問題など様々な分野で SAT が活用 2 SAT を利用した問題解決手法 3 SAT 問題 SAT の解 原問題 原問題の解 高速 SAT ソルバー 面倒 符号化 復号化 解決策の1つとして SAT 型 CSP ソルバーを利用 4 SAT 問題 SAT の解 CSP CSP の解 符号化 復号化 高速 SAT ソルバー 原問題 モデリング 原問題の解 解釈
輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
DX実現を加速する数理最適化コンサルティングの可能性
印刷する メールで送る テキスト HTML 電子書籍 PDF ダウンロード テキスト 電子書籍 PDF クリップした記事をMyページから読むことができます サマリー 数理最適化とは、問題を目的関数と制約条件の形に整理し、数理的な手法を用いて、制約条件を満たしつつ目的関数の最大化（ないし最小化）を行う営みである。まだ、マイナーな手法であるが、問題によっては機械学習や人工知能（AI）を用いるまでもなく、鮮やかに解決できる可能性を秘めている。本稿ではグループ分け問題の解決により業務負担を大きく軽減した事例に触れる 数理最適化の活用に当たっては、手法ありきで進めるのではなく、さまざまな手法の中から有効性を判断して、問題解決の枠組みを選択すべきである。同時に、現場に真に役立つ問題解決のために、現場に根差した問題を定義し、実務の制約条件を織り込んでモデル化することが重要である 開発した手法が現場の実業
数理最適化の参考書
専門家が執筆した数理最適化の書籍を紹介しています． 適当に書籍を並べただけですので内容については各自で確認をお願いします． 数理最適化全般 数理最適化の概観を知りたい人向け 穴井宏和，数理最適化の実践ガイド，講談社，2013． 数理最適化を現実問題の解決に活用するプロセスを知りたい人向け 岩永二郎，石原響太，西村直樹，田中一樹，Pythonではじめる数理最適化（第2版） ―ケーススタディでモデリングのスキルを身につけよう―，オーム社，2024． 三好大悟，Excelで手を動かしながら学ぶ数理最適化：ベストな意思決定を導く技術，インプレス，2023． 株式会社ビープラウド，PyQチーム，斎藤努，Pythonで学ぶ数理最適化による問題解決入門，翔泳社，2024． 数理最適化を初めて学ぶ人が手に取る入門書 福島雅夫，新版 数理計画入門，朝倉書店，2011． 久野誉人，繁野麻衣子，後藤順哉，数理最
Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
数理計画法テキスト
学習・研究用テキスト(最適化,線形計画法,内点法,数理計画法) このページでは最適化,線形計画法,内点法,数理計画法などの分野に関しての学習用テキストを公開しています. テキストの特徴として 定理などの証明を詳しく記述 多くの例を用いて説明 となっているため,学習しやすいテキストとなっております.
数理最適化のカレンダー | Advent Calendar 2020 - Qiita
The Qiita Advent Calendar 2020 is supported by the following companies, organizations, and services.
SoTAを総なめ！衝撃のオプティマイザー「SAM」爆誕&解説！ - Qiita
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は損失が最小かつその周りも平坦となっ
混合整数最適化でスケジューリング問題を扱うテクニック 〜カスタマーサポートのWFMを例に〜 - ZOZO TECH BLOG
はじめに こんにちは。ZOZO Researchの千代です。 ZOZO Researchでは類似アイテム検索やおすすめアイテムのレコメンドといった機能開発の他に、様々な技術を用いたバックエンド業務の効率化にも取り組んでいます。 ZOZOTOWNのカスタマーサポートで実施しているワークフォースマネジメント（以下WFM）もその1つです。WFMで必要となるタスク割当て問題を数理最適化問題の一種である混合整数最適化問題として定式化し、最適なタスク割当てを計算しています。 この記事では、カスタマーサポートのWFMでの利用を例に、混合整数最適化でスケジューリング問題を定式化するテクニックについて説明します。 目次 はじめに 目次 ワークフォースマネジメントとは スケジューリング問題とは この記事の問題設定 スケジューリング問題を解くためのアプローチ 数理最適化問題とは 混合整数最適化問題とは 混合整数
数理最適化を使った問題解決のすすめ - Qiita
数理最適化による問題解決について説明し、巡回セールスマン問題を例に実際にPythonでモデル化の例を紹介します。 数理最適化とは 数理最適化とは、問題解決の手法です。 課題を数理モデルとしてとらえ、最適解（最も良い答え）を求めます。ここでは最適解を1つだけ求めることを考えます。 数理モデルは、「変数、制約条件、目的関数」で構成されます。 変数のとりうる空間を解空間といい、1つの解は空間上の1点になります。 制約条件は、空間の中の壁になります。目的関数は、空間の中のベクトル（進行方向）になります。 すなわち、最適化とは、壁で囲まれた空間（実行可能領域）を進行方向に最も進んだ点を探すことです。 社会の最適化問題 数理最適化は、社会の問題解決に役立っています。ここでは、オペレーションズ・リサーチ学会（OR学会）の「ORを探せ！」ポスターから抜粋してみます。 避難施設の配置計画作成 エネルギーマネ
【組合せ最適化はいいぞ】デッキ編成を最適化問題として解く【逆転オセロニア】 | BLOG - DeNA Engineering
1行で 遷移を工夫した山登り法によって、強いデッキを高速に編成するアルゴリズムを構築しました。 はじめに はじめまして。9月の上旬に2週間、データサイエンティストコースのインターンに参加した長沢です。普段はKaggleや競技プログラミングにうつつを抜かしており、企業のインターンに参加したのは今回が初めてです。 この記事では、インターン中に私が取り組んだ内容について書きます。機械学習が流行ってるけど組み合わせ最適化も良いぞということが伝われば良いなと思います。 本記事の概要 デッキの良さを示す指標を作り、制約を整理して問題の定式化を行います。解の発見にMIPソルバが有効か確認をした後、山登り法を使って最適化を行い、現行手法と編成デッキの比較を行います。 取り組んだ課題 逆転オセロニア 逆転オセロニア 「逆転オセロニア（以下オセロニア）」というタイトルはどなたも聞いたことがあるのではないでしょ
物理のいらない量子アニーリング入門 - Platinum Data Blog by BrainPad
当社の社員が物理を専門としない人向けに量子アニーリングについて解説します！ こんにちは、A.I.開発部の太田です。 今回は量子アニーリングの簡単なシミュレータを作ってみたり、実際のD-Waveを使ってみた経験から、物理を専門としない人向けに量子アニーリングについて解説しようと思います。 （シミュレータのコードはgithubで公開しています。私自身、量子アニーリングについては最近勉強し始めたところなので、色々ご指摘いただけると幸いです。） さて、私の所属する部署の役割として、機械学習・人工知能関連の技術調査や社内への展開を行っており、その一環として昨年12月に早稲田大学の田中先生をお呼びして開催した量子アニーリング勉強会が社内で大変好評でした。 昨年度は量子アニーリングに関する一般書籍が発売されたり、科学雑誌「Newton」でも特集されており、物理学者以外の一般の方にも、量子アニーリングが認
Autogradという野郎が乗り込んできたのでガクブルな件 - Qiita
Autogradという野郎が乗り込んできました。はい、そりゃもういきなり。複雑な確率モデルや損失関数だとしても、パラメータに関する勾配をこれでもかというぐらい簡単に計算できちゃうので、機械学習の世界に大きな影響を与えそうです。現時点では、PythonとTorchでの実装が公開されているようですが、これからJuliaなど他の言語でも実装されていきそうですね。 （補足：この記事を書いたすぐ後にGoogleがTensorFlowなるものを出してきまして、そちらでも自動微分がしっかり実装されてるみたいです〜。機械学習関連のフレームワークは移り変わりが激しいですねー ^^; ） ちなみに始まりはこんな感じでした。 ゆるいですね。 とりあえずチュートリアルやりながら、Python版チュートリアルの前半部分にテキトーな日本語訳をつけたので、ここでシェアしておきます。英語が読める方は、僕のヘンテコな日本語
バンディットアルゴリズム入門と実践
Tokyowebmining発表用資料です。複数の選択肢がある場合に、どのように選択を行うのが効率的なのか？という問題を解決するためのアルゴリズムです。
じゃんけんグリコの最適戦略を探る
じゃんけんグリコの最適戦略を探る ある日の仕事中にふと考えました 「じゃんけんグリコ」で勝つためにはどうすればいいんだろう・・・ ・・・・春の陽気は敏腕サラリーマンの頭のネジを緩めるようです。 という訳で研究を始める事にしました。 ところで じゃんけんグリコ ってやったことありませんか？ 若い人はしらないかなあ。 昭和４０年台以前に産まれた人なら 多分やった事があると思うんですが・・・ 簡単に説明すると 場所：長めの階段 人数；二人以上 ルール ジャンケンをして勝った人が、その「出し手」によって 階段を登れる。 ・「グー」で勝った場合は「グ・リ・コ」と叫びながら３段上る ※１ ・「チー」で勝った場合は「チ・ヨ・コ・レ・イ・ト」と叫びながら６段上る ・「パー」で勝った場合は「パ・イ・ナ・ツ・プ・ル」と叫びながら６段上る んで階段の最上段に到達した速さで勝敗を競い
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
放送大学
数理最適化: Optimization Night #2 (2020/01/30 19:00〜)