問題タブ [linear-programming]

私は整数線形計画法の初心者です。組み合わせ最適化問題を解くために整数線形計画法ソルバーを使用する予定です。IDE での C++/オブジェクト指向プログラミングに精通しています。現在、ほとんどの場合、Cygwin で NetBeans を使用してアプリケーションを作成しています。

簡単に使用できる ILP ソルバーがあるかどうか尋ねてもよろしいですか? または、解決したい問題によって異なりますか？リソース マッピングの最適化を試みています。さらに情報が必要な場合はお知らせください。

どうもありがとう、キャシー。

誰もが図書館を推薦できますか-無料、または商用ですが手頃な価格（

ここにリストされているものがいくつかあります：http： //en.wikipedia.org/wiki/Linear_programming#Solvers_and_scripting_.28programming.29_languages

....しかし、私はLPを始めたばかりで、誰かが何かを推薦してくれることを願っています。

私は基本的に携帯電話のサブスクリプションサービスの価格を最小限に抑えようとしています。
最初の質問は次のとおりです。線形計画法はこの問題の解決にも適用できますか？

簡単な例：

基本プランオプション
プランA：200音声分、10テキストメッセージ、10MBデータ=$ 25
プランB：400音声分、25テキストメッセージ、25MBデータ=$ 40
プランC：1000音声分、50テキストメッセージ、50MBデータ= $ 65
...
プランF：2500音声分、150テキストメッセージ、150MBデータ=$ 95

計画を超えた場合の料金（すべての場合）：
音声1分あたり$.10
テキストメッセージあたり$.20MB
データあたり$1.50

オプションのアドオンパッケージ（基本プランに追加）：
無料の週末$ 15
無料の夜と週末（午後8時以降）$ 20
無料の夜と週末（午後6時以降）$ 35テキストメッセージパッケージ＃1（50テキストメッセージ）$ 5
テキストメッセージパッケージ＃2（ 150テキストメッセージ）$ 10
データパッケージ＃1（20 MBデータ）$ 20
データパッケージ＃2（50 MBデータ）$ 30
おしゃべりユーザー混合パック＃1（100分音声、100テキストメッセージ）$ 15
オタクユーザー混合パック＃1（50分音声、150 MBデータ）35ドル
など

50人のユーザーの詳細な使用状況データのセットがあり、各ユーザーがどの基本プラン（A、B、C ... F）の組み合わせを使用する必要があるか、およびどのアドオンパッケージを使用するかを把握したいと思います。彼らが持っている必要があります。

それは私の最初の質問ですので、寛大にしてください。

私はプロローグ/CLPに書く論理的な問題を抱えています:

エイプリル氏はメイ氏が嘘をついていると言います.メイ
氏はジューン氏が嘘をついていると言います.
ジューン氏はエイプリル氏とメイ氏の両方が嘘をついている
.真実。"

私は紙の問題を解決し、解決策はメイ氏が真実を語るということです。

しかし、プロローグでどのように書くのですか？私はおそらく同様の解決策を見つけました: WHO KILL - 同様の解決策

しかし、私はそれを理解していません。誰かがこれを行う方法を知っているか、別の例を持っていますか?

できれば助けてください:):):)

この素晴らしい SO の回答は、 の優れたスパース ソルバーを示しAx=bていますが、 のx各要素xが.>=0<=N

また、巨大（約2e6x2e6）ですが、行ごとの要素が非常にまばらAです。<=4

アイデア/推奨事項はありますか？MATLAB のようなものを探していますlsqlinが、巨大なスパース マトリックスがあります。

私は基本的に、スパース行列で大規模な有界変数最小二乗問題を解決しようとしています:

編集： CVXで：

ナップザック問題について勉強しています。ですから、ここで1つのことがわかりません。

利益/疑似リソース消費率

U _j = P _j / W _j W _j = R _ji * A _j

皆さんがこの式を知っていることを願っていますので、これ以上の説明は不要だと思います。
ここで Aj を計算したかったのです。そのLP緩和とは。総容量と重量（アイテムのサイズ）を使用して計算する方法。n個のアイテムとm個の容量がある場合、m個のLP緩和変数を持つ必要があることを意味します。そうですか？

のように言う誰か

妥当な乗数を得る最も簡単な方法の 1 つは、変数 x _jが区間 [0, 1] から任意の値を取得できる線形計画法 (LP) 緩和 MKP を解き、双対変数の値を代理乗数。換言すれば、ａ_ｊは、ＬＰ緩和ＭＫＰにおけるｊ番目の制約のシャドープライスに設定される。

LP 緩和 MKP の j 番目の制約のシャドー プライスをどのように計算しているか。しばらくGoogleで検索していますが、あまり明確ではありません。簡単な方法で理解できる人はいますか？

ここまで読んでくれてありがとう:)

線形計画法の問題を解決する必要がある Python スクリプトがあります。問題は、ソリューションがバイナリでなければならないことです。つまり、MATLAB のbintprog関数に相当するものが必要です。NumPy と SciPy にはそのような手順はないようです。次の3つのことのいずれかを行う方法について、誰か提案がありますか?

• そのような関数を含む Python ライブラリを見つけてください。

• より一般的な線形計画法ソルバーで解けるように問題を制限します。

• bintprogを直接使用できるように、Python と MATLAB をインターフェイスします。

ウィキペディアの記事を読みましたが、私の理解を超えているようです。最適化と書いてありますが、他の最適化方法とどう違うのですか？

初心者がアクセスしにくい資料に飛び込むことができるように、線形計画法を紹介する回答が最も役立ちます。

C＃用の線形計画法ソルバーを探しています。言い換えれば、線形計画問題を解決するC＃用のライブラリを探しています。

使いやすいライブラリが必要ですが（すばやく使用する方法を学ぶことができます）、自動絶対値変換などの機能がサポートされていると便利です（変換を自分でプログラムする必要はありません）。ライブラリは無料であることが重要です（必ずしもオープンソースである必要はありません）。

良いドキュメントは私にとって大きな利点です。私のプロジェクトでは、パフォーマンスが10％〜20％低下することは重要ではありません。

あなたの答えをありがとう

重複の可能性:
C# の優れた線形プログラミング ライブラリ ?

利用可能な無料のオープン ソース .Net 線形プログラミング ライブラリはありますか?

に関していくつかの不等式が{x,y}あり、次の方程式を満たします。

xandyは整数でなければならないことに注意してください。

グラフでは次のように表すことができます。青い領域は、上記の不等式を満たす領域です。

問題は、Matlab に許容可能なすべてのペアを見つける関数がある{x,y}かどうかです。この種のことを行うアルゴリズムがあれば、私もそれについて聞いてうれしいです.

もちろん、いつでも使用できるアプローチの 1 つは{x,y}、不等式が満たされるかどうかを確認するために、可能なすべての組み合わせをテストするブルート フォース アプローチです。しかし、これは時間がかかるため、最後の手段です。これを行う賢いアルゴリズムを探しています。または、最良の場合、すぐに使用できる既存のライブラリを探しています。

これらx^2+y^2>=100 and x^2+y^2<=200は単なる例です。実際fにgは、任意の次数の任意の多項式関数にすることができます。

編集: C# コードも歓迎されます。