メタヒューリスティクスによる汎用整数計画ソルバーの開発 - 数理最適化・進化計算に関する雑記帳
はじめに 開発したソルバーの概要と特徴 使い方 ダウンロード インストール サンプル コンパイル オプション・パラメータ設定 スタンドアロンソルバー ドキュメント ベンチマーク ライセンス おわりに 参考文献 修正履歴 はじめに メタヒューリスティクスベースの整数計画ソルバーをC++で開発しています．性能面・機能面ともに改善の余地はまだまだあるのですが，当初自分が思い描いたものがだいぶかたちになってきたということもあり，一度ご紹介したいと思います． プログラムはオープンソースとして開発しており，ソースコード・ドキュメントは以下のGithubリポジトリで管理しています． github.com 開発したソルバーの概要と特徴 PRINTEMPS は，C++で設計・実装された線形／非線形整数計画問題を近似的に解く汎用モデラー／ソルバーです*1．アルゴリズムとしてはメタヒューリスティクス，具体的には
凸最適化の概要と主双対内点法のアルゴリズムの解説 - Qiita
はじめに 凸最適化問題に使われている主双対内点法の解説を目標に、凸最適化の概要を説明します。二次計画がメインターゲットです。 この記事は ソルバーは使ったことあるけど、もう少しアルゴリズムの中身が知りたい 凸最適を学びたいけど、最適化の章までの道のりが長すぎてつらい な方が対象です。いまどき1から凸最適アルゴリズム実装しようなんて物好きは稀だと思いますが、この記事の目的は主双対内点法を実装するための知識を全体的にふわっと理解することです。 二次計画でよく使われる 主双対内点法 と 有効制約法 を以下に可視化しました。解の求め方が全く異なることが分かります。コードはpythonです。 主双対内点法（primal dual interpoint） 内点法の系譜（有効領域の内部を進む） 徐々に相補性残差を減少させて最適解を得る 線形計画、二次計画、非線形計画まで幅広く対応可能 高次元の問題が得意
最悪計算量を最小化した Union Find – 37zigenのHP
Union Find は link by size (または link by rank) と経路圧縮を組み合わせることで、各操作をならし \(O(\alpha(n))\) にできることが知られている（\(\alpha\) はアッカーマンの逆関数、\(n\) は頂点数）。このならし計算量は理論的に最良であるが、最悪計算量は \(O(\log n)\) になる（例えば二項木の Find ：Union Find の計算量 (1)）。そこで、この記事では理論的に最良な最悪計算量 \(O(\log n/\log\log n)\) を実現する Union Find を紹介する[1]。 アイディアは、Union と Find の計算量のトレードオフを傾けることである。ただし、ここでの Union とは、Find で根を見つけた後の操作を指す。Union by Rank (Size) は Union \(
Leader election - Wikipedia
In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task has begun, all network nodes are either unaware which node will serve as the "leader" (or coordinator) of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, h
容量スケーリング法のすゝめ
要約 最小費用流問題に対する最短路反復法(Successive Shortest Path, SSP)や Primal-Dual 法1と呼ばれるアルゴリズムは, 少し弄ると弱多項式時間アルゴリズムにできる. 具体的には, $O(\U \cdot \mathrm{SP_+}(n, m, nC))$ が $O(m \log \U \cdot \mathrm{SP_+}(n, m, nC))$ になる. $\mathrm{SP_+}(n, m, nC)$ は$n$ 頂点 $m$ 辺, 費用高々 $nC$ のグラフの一点から全点への最短路問題を解くのにかかる時間. 以下では実装をサボったダイクストラ法なので $O(m \log m)$ だが, $\exists k: m = O(n^k)$ を仮定すると合計 $O(m^2 \log \U \log n)$. まえがき ぼくの考えたさいきょうのフロー
つながりをデータから解き明かしたい ~ 複雑ネットワークの世界とそれを活用した不正検知の紹介 | メルカリエンジニアリング
この記事は、Merpay Tech Openness Month 2020 の17日目の記事です。こんにちは。メルペイのMachine Learningチームのhmjです。 検知精度とオペレーション負荷のトレードオフ解消 取引の連続性に着目した検知 と不正決済の検知への機械学習の適用の内容にて投稿してきました．今回は「集団的な不正の検知」がテーマとなります． 昨今，Web不正検知やセキュリティに関わるでもECサイトでの集団による不正の手口は多様化や複雑化してきていることが報告されています[1]． メルペイでも，今後起こり得る集団的な不正決済への対策を講じる必要があると考えています． 集団的な不正は検知できたとしてもその全体像がみえにくいこともあり，ソリューションとしては「検知できること」と「すばやく全体像を把握できる」を満たすものが求められています． 両者を満たす解決方法として，グラフ理論
PRIC - 兼雑記
http://www.spoj.pl/ranks/PRIC/ oxyさんとこ で見たので解いてたんだけどお話になりませんでした。無念。 細かい話は oxyさんの方に出てるので略。 私は Wikipedia 調べたら出てきたミラーラビンとかいうヤツを使うことにしてやってました。フェルマーのヤツよりちょっぴり除算少なめになる感じかなぁと思ってたのですがあんまり変わらんかったみたい。 でまぁとにかく一個素数計算するごとに除算の数が平均 90 回程度とかとても大変なので、それを減らすのをアレコレ考えたり調べたりしてたのは似たような感じなんですが、 oxy さんがうまくいかなかったという Montgomery のなんちゃらというのは効果がありました。 めんどくさいからコードはって終わり。まぁつまりなんか 32bit 整数 k,n,r に対して (k^n)%r という計算が除算 1 回でできるらしいで
競プロerのための群論 (swapと順列と対称群) - little star's memory
お知らせ Zennに移植しました。今後こちらの記事は更新されず、Zennの方のみ更新します。 zenn.dev この記事では競技プログラミングと群論に関する解説をします。競技プログラミングの問題を群論という立場から見ることで、新たな視点を得ることができるようになると思います。また、群論の入門にもなればいいなと思っています。 swapと順列 競技プログラミングの問題に、swapと順列は多く登場します。swapとは、2つの要素を入れ替える操作のことです。例えば、次のような問題があります。 第二回全国統一プログラミング王決定戦予選 C - Swaps (問題ページ) $ N $ 要素からなる2つの整数列 $ A_1,\ldots,A_N $ および $ B_1,\ldots,B_N $ が与えられます。以下の操作を $ N-2 $ 回まで(0回でもよい)行うことで、1以上 $ N $ 以下のすべ
最小費用流についてのちょっとしたメモ - gdgdiary
恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ 最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何？)ので頑張って通すと良さそう。 Minimum cost b-flow フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました ぼくの考えたさいきょうのフローライブラリ - みさわめも みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。 b-flow というのは、各頂点に需
高速な詰将棋アルゴリズムを完全に理解したい（完成版） - コンピュータ将棋 Qhapaq
Qhapaq アドベント将棋記事10日目 今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索(depth first - proof number)による詰将棋アルゴリズムの完全理解を目指していきます。 参考文献： memo.sugyan.com 【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み(proof number)/不詰(disproof number)を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面についてはpn、dnは0になります。局面のpn、dn（厳密には非0のpn、dn
仮眠プログラマーのつぶやき : UnityでGPGPU応用編 バイトニックソートを高速化
2020年07月13日12:44 カテゴリUnityGPGPU UnityでGPGPU応用編 バイトニックソートを高速化 バイトニックソート(Bitonic Sort)の概要バイトニックソート(Bitonic Sort)は主にGPU等の並列計算器でソートを実装しようとするときに使われるソートである。 計算量のオーダーはO(n log^2 n)であり、クイックソートのO(n log n)には負けるものの並列化による高速化が勝るという感じなのでいろんなところに使われている。 対象読者キーワード「GPU」「バイトニックソート」で検索してこの記事にたどり着いただろう方が対象。 この記事では ・バイトニックソートでなぜソートできるか ・どうやったら高速化できるか という点について重点的に書いている。 高速化については OpenCLでバイトニックソートを実装している海外サイト をパクリ参考にした。 こ
有理数同士の大小比較
JAG の ICPC 模擬地区予選 2015 の最中に, ジャッジルームで思いついたこと. イントロ 誤差を避けるために有理数を使うとき, オーバーフローするボトルネックは, 多くの場合, 有理数同士の大小比較になる. (逆に, 有理数同士の大小比較がボトルネックにならないときは, 別のテクニックで誤差を避けられることがある) そこで, 有理数の分母分子自体はオーバーフローしていないときに, 有理数同士の比較を, なるべくオーバーフローさせずに行う方法を見る. つまり, 次のような sgn 関数を作りたい. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39template<class Int> struct Fraction{
MCTSの評価伝達遅延を防ぐ方法（MCTS-Solver） - inani_waonの日記
ネタバレ ぼくのかんがえたさいきょうの手法は既出で、MCTS-Solverというようです。 はじめに モンテカルロ木探索（MCTS）は、ゲーム木の各ノードを評価しながら探索を行える優秀な探索アルゴリズムです。 Wikipedia : モンテカルロ木探索 https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%9C%A8%E6%8E%A2%E7%B4%A2 しかしCodinGame*1のUltimate Tic-Tac-ToeというゲームでMCTSを使っていたところ、シミュレーション結果が優勢にも関わらず、ある瞬間に劣勢に反転して負けてしまうことが多々ありました。ある手を指されると劣勢なのに、それが評価に反映されずに優勢と勘違いしている状態ですね。 左図：シミュレーション勝
木探索についての考察2 - 水たまり
以下の続き。 木探索がそもそもどういうものであるかと考えると、状態をノード、行動をエッジとして構築されるグラフ上を遷移しつつ、ノード上の価値を更新していく作業だと思われる。モンテカルロ木探索の選択ステップに「一個親のノードへ戻る」という選択肢を加えれば、理論上は木の自由な遷移ができるので、たとえば以下のようなことができる。 ステップ1 ステップ2 ステップ3 ステップ4 結局各ステップで解きたい問題は「木の遷移履歴が与えられるので、現ノードを適切に評価し次に遷移するエッジを決定する問題」としてまとめられそうだ。ここで、木の遷移履歴は状態を訪問順に並べた単なる時系列入力として扱える。（無茶かなぁ……）。状態の分散表現取得や、状態価値の評価にはAlphaZero的なモデルの分岐直前までの部分などを使うとして、次のようなやり方を今のところ想定している。 木のような句構造を持つことが多い自然言語文
ぼくの考えたさいきょうのフローライブラリ
要約 "最小費用流" のライブラリを "最小費用最大流" ではなく "最小費用 $\vecb$-フロー" の形で書くことについて. 「さいきょう」であって「さいそく」ではない. よくある実装に少し手を加えることで, 入力として扱える問題の範囲を広くでき, ライブラリ使用毎にアドホック気味に書く部分を減らせる. イントロ 最小費用流問題と呼ばれる問題を解く際, 競技プログラミングでは, 蟻本 に記載のものをはじめ多くの場合, 最小費用最大流を解くライブラリ, 特に最短路反復法や Primal-Dual 法 1 と呼ばれる実装が用いられる. これらのアルゴリズムを使う際, 辺コストが負になりうる場合, 負サイクルがある場合, 最小流量制約がある場合, 頂点吸込みや湧出しがある場合などは, Bellman-Ford 法や SPFA 等で追加処理を行ったり, ネットワークの変形をすることで, 同値
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Leader election in distributed systems
全ての機械学習の論文は新しいアルゴリズムを提案しているのですか？
cakes（ケイクス）
pitsu on Twitter: "(Aの任意倍)mod B の最大値が B - gcd(A,B) なの直感的にはわかるけど証明できない"