Benders Decomposition(ベンダー分解)は問題を二つのmain, sub問題に分割することで問題を解きやすくするテクニックです。次のような性質がある問題に有効です。Kohji Nishimuraさんの「双対変数を直感的に理解したい」から引用しています。 決定変数にyが一…

SCIP: https://www.scipopt.org/は言わずと知れたLP、MIPソルバ。 このプロジェクトにはfscip: https://ug.zib.de/も同封されています。これはSCIPのスレッド並列版ソルバです。 Environment Ubuntu 18.04.2 LTS Build unzip scipoptsuite-8.0.3.zip cd scip…

Qiitaに記事を投稿しました。 Dev Community Medium 本稿では、最適化モデリングツールfloptの基本的な使い方やいくつかの機能の具体例を紹介します。(私も開発者の一人です) 最適化モデリングツールとは、ユーザーが解きたい問題を表現、具現化する作業をサ…

gurobipy とは GUROBI optimizerが提供するpythonインターフェイスです. pip で installできます. gurobipyをクラス内で用いるときの注意点; 下記のプログラムは2変数(x, y)からなる簡単な最適化問題を求解するもの. solve()関数で問題の定式化と求解を行な…

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

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

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

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

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

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

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

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

CBCソルバー(デフォルト)並列処理 pythonの線形計画法ソルバーpulpを並列で計算する方法です。 例えば、4スレッドで実行するなら import pulp prob = pulp.LpProblem(sense=pulp.LpMinimize) (省略) prob.solve(pulp.PULP_CBC_CMD(threads=4)) と書きます。 …

Cbcとはオープンソースの混合整数線形計画(mixed integer liner program)ソルバーです。混合整数線形計画問題とは線形計画問題の中に連続変数と、整数変数が混合している問題のことになります。 そのCbcソルバーで並列処理を行えるようにするには、下記のよ…

この記事の続きです。 inarizuuuushi.hatenablog.com この記事の中で2通りの方法を載せていますが、どちらの方が良いか調べてみたのでその報告です。 上の問題を解きます。 それぞれ制約の入れ方は 以前の記事では、2つ目のパターンでは分数の形で記述してい…

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。 バイナリ変数とは0と1の2値のみをとり得る変数のことです。 これがなかなか難しくて、いろいろ調べてみて、 2通りの定式化を行いました。 1つ目は以下の…

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回も線形計画法で解いてみたいと思います。(あえてね) ↓その1です。 inarizuuuushi.hatenablog.com が定式化となります。(とするとが続いているところは無視してください) 路の制約として、フ…

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回は線形計画法で解いてみたいと思います。(あえてね) 定式化は こうなります。 最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。 ad(j)については、jの隣接ノード…