問題タブ [linear-programming]

「Python線形計画法」をすばやく検索すると、多くのヒットが見つかります（例：これ）。それらを見ると、古い依存関係、不十分なドキュメントなどに関するかなりの数の苦情があります。

誰もがPython用の頭痛のない（例えば、高速で、十分に文書化された、インストールが簡単で、クリーンなAPI）線形計画法ライブラリを推奨できますか？

問題: n 個の変数 (x) が合計されて const になります。x1+x2+..+xn = const で、各 x は p 個 (たとえば 5 個) の正の整数値しか取りません。x 間の差が最小になる解、つまり最も均等に分布する解を見つけたいと考えています。これは整数計画問題ですか?

dlm

次のような最適化問題があります。

たとえば、正の整数の配列が与えられた場合、(y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3)関数の値の合計を最大化することを目指しています。(は正の整数)f(x)f(x) = x if x + y <= mf(x) = 0m

たとえば、上記の特定の例 ( を使用) では、合計が になるためm = 5、最適なx値はであり、これは の他の可能な値の中で最も高くなります(暗黙的に、可能な値はから までの範囲になります) 。22 + 2 + 2 + 0 + 2 = 8xx05

もちろん、x の範囲が適度に小さい場合は、考えられるすべての x 値の合計を徹底的に計算して比較し、最大の合計を与える x を選択することができます。ただし、範囲が大きくなると、この方法は非常に高価になる可能性があります。

この問題をより一般的かつ適切に解決するために、線形計画法などから使用できるものがあるのではないかと思います。

IPM の実装をいくつか見てみたいと思います。望ましい言語は、C/C++、Java、または python、perl などのスクリプト言語です。その他も良好です。

私を助けることができる良いリソースを探しています、

1. 最適化手法の基礎、
2. 内点法の基本と他のテクニックとの違いの基本
3. IPMの種類、
4. アルゴリズムの詳細、および
5. サンプル実装。

これらのアイデア/ロジックを使用して線形または二次方程式のシステムを解くプロジェクトの一部として、これに興味があります。

上記のリソースに関する情報があればお知らせください。

シンプレックス法を実装するアルゴリズムをプログラミングする前に、実際のプログラミング作業が始まる前に問題を解決しようと考えていました。

どういうわけか、私は正しい答えを決して得ることができません。私は方法を理解しましたが、問題は行操作にあります.'1'の値を持つピボット要素を除いて、すべて0の値を持つ列を取得しようとします.

これを行うには、R1-R2、R2 + 5R1 などを実行して行をいじります。常にピボット列を 1 にし、残りを 0 にすることができますが、私の答えは決して正しいものと一致しません。行操作の問題に絞り込みました-これに関連するルールはありますか、それとも好きなだけ行をいじることができますか? また、古いタブローと現在のタブローを混在させることはできますか?

ありがとう

要約: この問題を解決するにはどうすればよいでしょうか?

やあ、

私は、変数が最小値と最大値によって制限される混合スタイルの最大化問題に取り組んでいます。私の問題の代表的な例は次のとおりです。

私の最後のプロジェクトには、上記のようなより複雑な問題が含まれています。問題の構造は変わりません。係数と入力だけが変わります。xしたがって、上記の例では、C# プログラムが、次にy、次zのようにすばやく判断できる関数のセットを探しています。

これについてあなたの考えを聞きたいです！

ありがとう！

Following instructions from http://www.coin-or.org/PuLP/main/installing_pulp_at_home.html#installation , I installed PuLP using "Windows Installation from source"

When I tried to run the test on the page ( Instructions on the page : "To test that that you pulp installation is working correctly please type the following into a python interpreter and note that the output should be similar. The output below is what you would expect if you have not installed any other solvers and the CoinMP solver bundled with pulp works.")

My Results :

import pulp pulp.pulpTestAll() Solver pulp.solvers.CPLEX_DLL unavailable. Solver pulp.solvers.CPLEX_CMD unavailable. Solver pulp.solvers.COIN_CMD unavailable. Solver pulp.solvers.COINMP_DLL unavailable. Solver pulp.solvers.GLPK_CMD unavailable. Solver pulp.solvers.XPRESS unavailable. Solver pulp.solvers.GUROBI unavailable.

According to the webpage,this should be my output :

import pulp pulp.pulpTestAll()
Solver pulp.pulp.COIN_MEM unavailable. Solver pulp.pulp.COIN_CMD unavailable. Testing continuous LP solution Testing maximize continuous LP solution Testing unbounded continuous LP solution Testing MIP solution Testing MIP relaxation Testing feasibility problem (no objective) Testing an infeasible problem Testing an integer infeasible problem (Error to be fixed) Testing column based modelling Testing column based modelling with empty constraints Testing dual variables and slacks reporting Testing resolve of problem Testing Sequential Solves Testing fractional constraints Testing elastic constraints (no change) Testing elastic constraints (freebound) Testing elastic constraints (penalty unchanged) Testing elastic constraints (penalty unbounded) * Solver pulp.pulp.COINMP_DLL passed. Solver pulp.pulp.GLPK_MEM unavailable. Solver pulp.pulp.GLPK_CMD unavailable. Solver pulp.pulp.XPRESS unavailable.

I am using Python 2.7.1, PuLP 1.4.7 on Windows 7 64 bit.

I guess it is because the CoinMP solver bundled with PuLP is not working. I just started working on Python a week back, I am just an amateur in programming.

I am having problems with linear programming solvers on a project I am working on. Firstly I tried using Ajanta, but this won't solve the class of problems I needed to solve. So I tried GLPK and lp_solve, but It seems I can't make Windows understand where the dynamic libraries are.

I put the stub (the .dll that links the code with java) and the actual code of the libraries (it seems usual that they come separated) on C:\Windows\System32 and I checked the following:
- The path variable is correctly set for searching on this directory.
- I correctly linked the java library with my program.
- I checked the dependencies with Dependency Walker and this program finds everything. (http://www.dependencywalker.com/)

I am working on Windows 7 with JRE/JDK 6 update 26. I am coding on Eclipse, also.

What I am doing wrong?

線形ディオファントス不等式のシステムを解くための適度に高速なアルゴリズムはありますか？

私は1つの問題で髪を引っ張ってきました...全体的な問題は複雑です...しかし、本当に重要な部分を説明するために最善を尽くします...

各エッジが接続された2つのノード間の相関を表すグラフがあります。各ノードはタイムコース（TC）（つまり、400の時点）であり、イベントはさまざまな時点で発生します。2つのノード間の相関は、重複するイベントのパーセンテージとして定義されます。この例を簡単にするために、各ノードで発生するイベントの総数が$tn$と同じであると仮定します。また、2つのTC（ノード）に$ on $のオーバーラップイベント（つまり、まったく同じ時点で発生したイベント）がある場合。次に、相関は単純に$ on $ / $tn$として定義できます。

今、私は11ノードのネットワークを持っています。そして私は2つのノードごとの相関関係を知っています。相関制約を満たす11ノードすべてのTCを生成するにはどうすればよいですか？

2つのノード間の相関関係がわかっている場合、2つのノードに対してこれを行うのは簡単です。TC_1とTC_2の相関値が0.6であると想定します。これは、2つのTCで60％の重複イベントがあることを意味します。また、イベントの総数は、TC_1とTC_2の両方で$tn$と同じであると想定します。2つのTCにイベントを配置する簡単なアルゴリズムは、最初に0.6 * $ tn $の時点をランダムに選択し、それらを両方のTCで重複したイベントが発生したタイムスロットと見なします。次に、TC_1で（1-0.6）* $ tn $の時点をランダムに選択して、TC_1の残りのイベントを配置します。最後に、TC_2の対応する時点でイベントが発生しなかったTC_2の（1-0.6）* $tn$時点をランダムに選択します。

ただし、生成された3つのTCが3つの相関制約すべて（つまり、3つのエッジ）を満たす必要がある3ノードネットワークを考えると、難しくなり始めます...11ノードネットワークではこれを行うことはほとんど不可能です。 ..。。

これはあなたにとって意味がありますか？そうでない場合はお知らせください...

これは単なる計算機科学のプログラミングの問題だと思っていましたが、考えれば考えるほど線形計画問題のようですね。

誰かが合理的な解決策を持っていますか？私はこれをRで行っていますが、どのコードでも問題ありません...