問題タブ [linear-programming]

何年も何年もMatlabを使用した後、私はまだPythonに非常に慣れていません。Pulp を使用して整数線形プログラムをセットアップしようとしています。

数値の配列が与えられた場合:

私は最大化したい：

制約を受ける

および境界あり (ベクトルベースの境界)

しかし、パルプでは、ベクトル宣言を適切に行う方法がわかりません。私が使用していた：

ここでは、個々の境界のみを入力できます (したがって、1 つの数値のみ)。

制約については、本当にこの行を行ごとに実行する必要がありますか? 何かが足りないようです。助けていただければ幸いです。ドキュメントでは、短い例について説明しています。私の場合、変数の数は数千です。

この質問は、ここに投稿された私の関連する質問に続くものです。@mhumは、私の問題がカバーする問題の領域に分類されることを示唆しました。質問を最小集合被覆問題にエンコードしようとしましたが、現在、次の形式のデータセットがあります。

目的は、すべての数値をカバーし、総コストを最小化しようとする適切な集合被覆を見つけることです。私のデータセットは大きく、このように少なくとも30000セット（サイズは5〜40要素の範囲）です。これを解決するための良い貪欲な実装はありますか、それとも私自身でこれを実装しますか？私はLPの専門家ではありませんが、これを解決できるLPソルバー（numpy / scipyから）も受け入れられます。

Apache Commons Math でバイナリint、、などの決定変数タイプを設定する方法は? 以下のプログラムの出力は次のとおりです。doubleSimplexSolver

決定変数の型intを notにしたいdouble。333, 0, 8325整数の決定変数として解決された場合、出力は次のようになります。

つまり、現在、IQPをILPに変更しようとしています。古い実装では約2日かかりましたが、現在は線形ツールを使用しています。速度が上がるはずです。基本的に問題は最大化することです（約50のバイナリ変数で）：

$$ \ sum_ {g = 1} ^ {5} sum_ {p = 1} ^ {10}（S [p] x[g][p]-倦怠感[g][p]-眠気[g][p ]）$$

アップデート

デビッドは正しい方向に進んでいると思いますが、ボーナス変数を使用して式を最大化しようとすると、毎回ゼロになります。なぜですか。いくつかのコードの下では、スコアはのようになりS[1..10]=[1,2,3,4,5,6,7,8,9,10];ます。

私の質問は、古い輸送の問題についてです。一度に1つのアイテムしか転送できないボートで、川を渡って3つのアイテムを運ぶことです。制約は、ヤギとキャベツ、ヤギとオオカミなど、特定のアイテムを一緒に残すことができないことです。この問題は、整数計画法または別の最適化アプローチを使用して解決できるはずです。コスト関数は、川の反対側にあるすべてのアイテムであり、そこに到達するために必要な旅行は、さまざまな実行可能なソリューションを試すシンプレックス（？）からの出力である可能性があります。誰かがこの問題の整数計画法（または線形計画法）の定式化、および/またはすべてのパスを試しているシンプレックスのトレースを含む、プログラムでソリューションを提供できるMatlab、Octave、Pythonベースのコードを持っているかどうか疑問に思いました-私たちのボート乗り。

ここには面白いものがいくつかありました

http://www.zib.de/Publications/Reports/SC-95-27.pdf

ありがとう、

大規模な線形計画法の問題があります。「linprog」を使用してmatlab内で解決できます。ただし、ループ内にあり、2 回目の反復からループの最後までバイパスする必要があります。これは、以下の形式の単純な LP です。

a_i b_i st の合計を最小化します。...

a_is は私の変数で、b_is は係数です。各ループ反復では、b_is のみがわずかに変化します。この変更後に変数の新しい値が必要です。(matlab は大規模な問題に対してシンプレックス法を使用しないことに注意してください)。

ループで時間を節約し、LP を複数回解決しない方法はありますか?

ありがとう

特定の時間にさまざまなポイント間を移動する必要があるオブジェクトのグループがあるという問題を解決しようとしています。

線形計画法の観点から、ほとんどの制約を形式化することができました。つまり、次のようになります。

などなど、すべてのオブジェクトとすべての到着/出発について同様です。目的関数は、移動にかかる時間を最小限または最大限にすることです。

私が抱えている問題は、もう 1 つの制約があることです。特定のオブジェクトは、移動中に他のオブジェクトを同伴する必要があります。たとえば、object1 には、object2、object3、または object4 が付随する可能性があります。これらのオブジェクト自体には、特定の到着または出発の制約があります。(おそらく混合整数の) 線形プログラムに、付随するオブジェクトの選択を処理させたいと思います。しかし、これを形式化しようとしている間、それを線形に保つ方法がわかりません。次のような混合整数制約を考えました

しかし、「物体 2 が物体 1 を伴う場合、物体 1 とともに X 時刻に出発し、Y 時刻に到着する」という制約の表現方法がわかりません。これは、ブール変数 (オブジェクト 2 がオブジェクト 1 を伴う場合) に移動時間を乗算するため、非線形に見えます。

もちろん、「if...then...」ステートメントごとに異なる線形問題を作成することもできますが、60 個の付随するパスと 10 個の付随するオブジェクトを使用すると、10^60 個の線形プログラムを解決する必要があります。良い。

この線形計画法の問題を形式化して、「X は Y に付随するか?」という決定を行う方法について直感を持っている人がいるとします。問題自体で表現することができます。

宿題に R を使用して加重頂点カバー問題のインスタンスを解決しようとしていますが、正しく理解できないようです。私はROIパッケージを使用しています（を使用することもできますlinprog）。

インスタンスは次のようになります。

私のコードは次のとおりです。

その結果No solution found.、何が間違っているのかわかりませんが、明らかなことかもしれません。理解できません。たとえすべての頂点を取得したとしても (つまり、すべての変数が >= 0.5 であっても)、解は常に存在するはずです。

問題があれば、リポジトリ (ver. 2.14) から R を実行している Arch Linux を使用しており、 経由でパッケージをインストールしていますinstall.packages("...")。

ありがとう！

現在、最小化ソリューションにBLEICを使用しています。次のリンクhttp://msdn.microsoft.com/en-us/library/ff628587%28v=vs.93%29.aspxで MSDN の例からケースを実装します。

以下は私のソースコードです。

私の質問は、異なる初期点を設定すると、異なる答えが得られる場合があり、「NAN」を返す場合がありますx = "[1000.0,1000.0]"、[NAN、NAN] を返す

問題の原因は何ですか? そしてそれを修正する方法は？