サブロウ丸

主にプログラミングと数学

Python モデラーとソルバーまとめ (解ける問題の比較)

Solver (May 22, 2020) [S] Solver (問題を解くアルゴリズムを内包し, それを実行して解を探索するアプリケーション) [M] Modeler (解く問題をプログラムで作成するためのアプリケーション) Nonlinear or Linear Programming NLP (Nonlinear Programming) MI…

Raspberry Pi4 ModelB 4GB を買いました

Raspberry Pi4 本体 (ModelB4GB) ¥ 6,875 www.amazon.co.jp microSDカード (32GB) ¥680 www.amazon.co.jp カードリーダー microSDカードにOSを書き込む用 ¥ 1,780 www.amazon.co.jp micro HDMI → HDMI 変換コネクタ ¥ 999 Amazon | Cable Matters Micro HDM…

pulp.GUROBI_CMD での 時間 スレッド数 制約

バージョン pulp: 2.2 python: 3.8.4 サンプルコード スレッド数 = 5, 時間制約 30s にする場合 problem = ... solver = pulp.GUROBI_CMD( options=[ ('Threads', 5), ('TimeLimit', 30) ] ) problem.solve(solver=solver) 他に入れられるオプション www.gur…

GitHub運用

Git, GitHubについての資料, ブランチ運用について, パラパラ説明をしています.

[ Python ] LP modeler と Solver 一覧

Pythonで使線形計画問題(LP)を扱える最適化アプリケーションをいくつか使用することができます. アプリケーションは大きく2種類に分類されます. Solver (ソルバー); 問題を解くアルゴリズムを内包したアプリケーション Modeler (モデラー); 最適化問題をプロ…

flopt 統合型最適化モデラーとソルバーの開発 その1

統合型最適化Pythonフレームワーク flopt をオープンソースで開発中です. floptは 最適化問題のモデリングツールであり, ソルバーであり 他ソルバーのOverwraperであり, 手法比較ベンチマーク を目標に作成しています. Github PyPI Read and Docs PuLP Pytho…

[ python ] 自作クラスをnumpy ndarrayに使用する

Subclassing ndarray — NumPy v1.18 Manual (公式)を参考にすれば良いでしょう. 以下, 簡単な実装例. class Element: def __init__(self, r, c): self.r = r self.c = c def __repr__(self): return f'Element({self.r},{self.c})' 上の自作クラスを, 2次元n…

[ Eigen ] long double 型 のMatrix, Vectorの宣言

Eigen とは C++ の行列演算ライブラリ[1] です. 暗黒通信団による Eigen メモ [2]. これさえ読めば基本機能は大体使えます. MatrixXdや, MatrixXi, VectorXd を使えば, 要素がdoubleやint型の行列やベクトルが扱えます ([2] を参照してください)が, Eigenは…

【python】 matplotlib: color をRGB, RGBAで指定した際のwarning

matplotlibのplotやscatterでcolorを (0.0, 0.0, 0.803921568627451, 1.0) のようなRGBや, RGBAで指定した場合 plt.plot(..., c=(0.0, 0.0, 0.803921568627451, 1.0)) 'c' argument looks like a single numeric RGB or RGBA sequence, which should be avoi…

Master Mind探索プログラム

MasterMind というボードゲームの 最善手探索用プログラムを公開しました. github.com policyやcode_iterに関数を追加して, master_mind.pyの上部をいじれば改良できますので, アイデアがある方はよろしくお願いします. サンプル 3色 2ピンの場合 python mas…

【Python】pulp, CPLEXで並列数指定

pulpでsolverとしてCPLEXを指定する場合, 並列数はDefault設定では使用可能なthread数を全て使用する設定になっています. 並列数を自分で指定したい場合は, 以下のようにすれば良いです. import pulp class MyCPLEX(pulp.CPLEX): def __init__(self, mpi=Tru…

【Python】pulp; 多段階最適化

まだ, pulpのdocumentに載っていない関数ですが, sequentialSolveという多段階最適化を行う関数が実装されています import pulp from pulp import LpVariable # 問題の宣言 problem = pulp.LpProblem() # 変数の宣言(連続変数, 上限2) x = LpVariable('x', u…

【Python】generatorを用いた, 二分木におけるパスの全列挙

このような番号付けで表現される二分木におけるpathの全列挙を考えます. gist.github.com を実行すると >> [[0, 1, 3, 7], [0, 1, 3, 8], [0, 1, 4, 9], [0, 1, 4, 10], [0, 2, 5, 11], [0, 2, 5, 12], [0, 2, 6, 13], [0, 2, 6, 14]] が出力されます. 深さ…

PyTorch autograd で Newton法実装

Qiitaに記事を投稿しました. PyTorchは主にニューラルネットワークの学習に使用されるライブラリですが, autogradはより幅広い使い方ができます. 今回はその機能を用いてNewton法を実装しました. qiita.com

【MacOS】Pulp ソルバー選択 / 並列計算

Pulpについて ソルバー選択 CBC オプション(並列計算など) 自分でインストールしたCBCソルバーを使用する 2-1. cbcソルバにパスを通す 2-2. PuLPの設定ファイルを書き換える 初期解の使用 GLPK SCIP SCIPのダウンロード pulpの設定ファイルへscipのパスを追…

【Python】scipy KD treeの使い方

kd treeは k dimensional treeで, k次元領域の点探索などに用いられるデータ構造です。 kd treeを取り扱うモジュールがscipyにあります。 import scipy.spatial as ss from random import random # データ数 N = 10000 # (x座標, y座標)のデータリスト data …

【Python】フラクショナルカスケーディング実装

Qiitaに記事を投稿しました。 概要 フラクショナルカスケーディングは2次元領域において, 層状領域木を用いて指定した長方形領域に含まれる点を高速に探索する技術です。問い合わせ時間は, はデータ点数, は報告される点の個数です[1]。 フラクショナルカス…

グラフィティカルモデル 定理3.2

グラフィカルモデル (機械学習プロフェッショナルシリーズ) [ 渡辺 有祐 ]価格:3024円(税込、送料無料) (2019/2/7時点)楽天で購入

レイティング・ランキングの数理

レイティング・ランキングの数理 の各章の概要をまとめたものです。 本当に概要をまとめただけなので, より詳しく知りたい方は書籍を参考にしてください。 レイティング・ランキングの数理 No.1は誰か?価格:5400円(税込、送料別) (2018/12/2時点)楽天で購…

順列と自然数の対応付け

なぜこうなるかは、実際に順列を書き出して番号をつけて眺めてみれば分かると思います。 以下は上記アルゴリズムを元にpythonで実装したものです。(少し変えています) 関数 perm2int(perm)が順列を自然数に変換し、 関数int2perm(n)が自然数を順列に変換しま…

Preflow Push-Relabel アルゴリズム 改良

Qiitaに記事を投稿しました。 qiita.com 概要 preflow-push algorithm はネットワーク G=(V, E)上の最大フローを求めるアルゴリズムです. (中略) この記事では, 計算量を削減する改良として, FIFO Preflow-Push AlgorithmとHighest-Label Preflow-Push Algor…

Matplotlib 日本語の使用

Pythonの代表的なグラフ描写モジュールmatplotlibでグラフタイトルや凡例に日本語を使う方法をメモります。 環境: OS: macOS High Sierra 10.13.3 Python: Python3.6 基本的には, 以下のサイトを参考にすれば上手くいくと思いますが /usr/local/lib/python3.…

Subgraph isomorphism (J. R. ULLMANNのアルゴリズム)

Qiitaに記事を投稿しました。 グラフ の中に が部分グラフとして存在するかどうかを判断する問題です. Subgraph isomorphismの解法として, J. R. ULLMANNのアルゴリズム [1] を紹介します. 参考文献 [1] ULLMANN, Julian R. An algorithm for subgraph isomo…

Eppstein's Algorithm (Find the K shortest paths) 解説と実装 (Python)

Qiitaに記事を投稿しました。 K Shortest Path Problem (KSP) とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です。 多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法として Eppsteinの アルゴリズムを実装し…

常微分方程式の数値解析による解軌跡の導出

Qiitaに記事を投稿しました。 一階の常微分方程式は, 一般に の形で記述されます。 は独立な変数, は既知の二変数関数であり, は求める未知関数です。 (中略) まずは, 1つの一階の常微分方程式の解軌跡を求める方法を紹介します。 また, この解法は高階の微…

雰囲気で理解する Yen's algorithm (Find the K shortest paths)

Qiitaに記事を投稿しました。 K Shortest Path Problem とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です. 色々バリエーションがあるみたいですが, 今回は多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法…

求根アルゴリズム デッカー法 ブレント法 [3/3]

さて, 求根アルゴリズム最終回はデッカー法とそれを改良したブレント法を紹介します。 ブレント法はMATLABの非線形関数の根をみつける関数fzeroにも用いられている有用なアルゴリズムになっています。 デッカー法(Dekker method) ブレント法(Brent method) …

求根アルゴリズム 挟み撃ち法 / イリノイ法 / アンダーソン・ビョーク法 [2/3]

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形である, イリノイ法, アンダーソンビューク法を紹介します。 挟み撃ち法(False position method) イリノイ法(Illinois method) アンダーソン・ビョーク法(Anderson & Björk's method) 挟み撃ち法(…

求根アルゴリズム 二分法 / 割線法 [1/3]

3回に分けて, 様々な求根アルゴリズムを紹介したいと思います。 求根とは, ある関数 の根, すなわち を満たす を求めることです。 もし が微分可能であれば微積分の知見を用いて根を見つけることは容易ですが, 今回は関数 が微分不可能, もしくは具体的な関…

【MATLAB】 fnplt カスタマイズ

MATLAB fnpltで関数をプロットできます。 このとき, メッシュ上の黒い枠線を消したいなーとか思っている人向けの記事です。(すごくニッチだ) fnpltは surfという, 関数の表面をプロットする関数をもとに作成されています。 なのでfnpltの中のsurfのオプショ…