サブロウ丸

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

python

枝集合が単調増加するグラフの平均クラスタ係数更新方法

平均クラスタ係数とは 枝集合の単調増加 実装 保持情報 枝増加時の更新 テスト コード 出力 まとめ 参考 平均クラスタ係数とは グラフ構造の特徴づけ指標の一つです. ノードごとに, そのノードを含む三角形(クリーク)の割合を算出します. 具体的には グラフ,…

CBC ソルバ ログの可視化

最終的に描写するもの 暫定解値と, 下限値の時間推移 最適値 CBCログ 問題サイズなど Welcome to the CBC MILP Solver Version: 2.10.3 Build Date: Dec 15 2019 command line - xxxx At line 2 NAME MODEL At line 3 ROWS At line 2426 COLUMNS At line 145…

pulp制約の削除, 入れ替え

pulpにおける動的な制約の削除, 入れ替えのサンプルコード gist.github.com

pulpとamplifyの相互変換

Qiitaに記事を投稿しました qiita.com

Python Colorlog サンプルコード

colorlog ( https://github.com/borntyping/python-colorlog ) を用いれば ロギング(logging) を色付きで簡単に表示できます. 若干使い方が難しいと思いますので, サンプルコードを作成しました. 下記を _logginig.pyの名前で保存して, 同ディレクトリ内で以…

【python】 multiprocessing.Queue を用いた並列化 (サンプルコードあり)

multiprocessing.Poolの功罪 multiprocessing.Pool + multiprocessing.Queue による解決策 1. 変数をQueueに格納 2. 子プロセスの立ち上げ 3. 立ち上がった子プロセスはQueueから変数(i, j)を受け取り, 処理 + 子プロセスが処理を終えると, 次の変数をQueue…

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

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

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…

[ 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…

【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で実装したものです。(少し変えています) 関数 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.…

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

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

最小カットを用いたモノクロ画像のノイズ除去 その2

この記事の続きです。 今回やりたいのは, ある画像を元にノイズを付加した画像を数枚用意します。 そのノイズが付加した数枚の画像から元の画像を復元することを考えます。 前回の記事のを事後確率を用いて以下のように決定します。 ということで, 上記の考…

最小カットを用いたモノクロ画像のノイズ除去 その1

「劣モジュラ最適化と機械学習」(講談社)の4.2節 「マルコフ確率場における推論とグラフカット」で取り上げられている 劣モジュラを満たすエネルギー関数最小化による画像ノイズ除去手法を実際にプログラム実装してみました。 行いたいことに特化した簡単な…

ナップサック問題 近似アルゴリズム

言わずと知れたナップサック問題は、動的計画法を用いると最適解を商品の個数とナップサックの容量に対して1次のオーダーで計算することができます。 また、この問題については近似解法が知られています. とりあえず2通りの近似解法を知っているので, 動的計…

Python 文字と整数の相互変換

忘れやすいので, メモ。 char -> int 例えば"A"を0, "B"を1, "C"を2, ...と変換したい場合はord関数を使います。 Excelのマス目の番地を指定して読み込むときとかに便利ですね。 ord('A') >>> 65 ord('B') >>> 66 このord関数は1 文字の Unicode 文字を表す…

Python ショートコーディング Tips

Pythonはcやjavaよりも可読性が優れている言語です。 その可読性を十分に発揮する、つまり人が見て読みやすいプログラムにするには、プログラムにある程度冗長性を持たせる必要があります。 基本的には短いプログラムほど理解しやすいですが、技巧的に短くし…

【Python】順序付きビンパッキング問題

この記事の応用です。 商品とビンに順序をつけた場合のビンパッキング問題になります。 ソースコード 実行結果 入力 うさぎ0が食べるりんごの量は1.2 うさぎ1が食べるりんごの量は2.2 うさぎ2が食べるりんごの量は1.0 うさぎ3が食べるりんごの量は0.7 うさぎ…

【Python】ビンパッキング問題

離散数学の組合せ論の代表的な問題としてビンパッキング問題というのがあります。 十分に用意された品物を、複数個のビン(容器)に詰めるときの最大利益を求める問題です。 このときビンの個数が1つであればナップサック問題と呼ばれる問題になります。 この…