問題タブ [linear-programming]

テストカバーの問題は、次のように定義できます。

一連のn病気と、m症状をチェックするために実行できる一連のテストがあるとします。また、次のものが与えられます。

• nxn行列A。ここで、は、th病の患者に対してthテストA[i][j]を実行した結果を表す2進値です（1は陽性の結果を示し、0は陰性を示します）。ji
• テストの実行コストj、c_j; そしてそれ
• すべての患者はちょうど1つの病気になります

nタスクは、最小限のコストで各疾患を一意に識別できる一連のテストを見つけることです。

この問題は、目的関数を最小化する整数線形計画として定式化できます。\sum_{j=1}^{m} c_j x_jここで、セットにx_jテストを含めることを選択した場合は= 1、それ以外の場合は0です。j

私の質問は：

この問題の線形制約のセットは何ですか？

ちなみに、この問題はNP困難であると思います（一般的な整数線形計画法と同様）。

特定の文の最大の重みを見つける必要があるゲームに取り組んでいます。

「the quick brown fox」という文があり、定義された重みを持つ単一単語と二重単語の両方を想定するとします。「the」-> 10、「quick」-> 5、「brown」-> 3、「fox」-> 8 、「ザ・クイック」 -> 5、「クイック・ブラウン」 -> 10、「ブラウン・フォックス」 -> 1

単一語と二重語のどの組み合わせが最大の重みを提供するかを知りたいです。この場合、「the」、「quick brown」、「fox」になります (重み = 28)

この問題は線形計画法で解決できると言われましたが、そのような方法を実装する方法がわかりません。具体的には、問題の制約を表現する方法がわかりません。この場合、一部のダブルワードは、含む単一の単語と組み合わせることができないという事実です（つまり、「クイック」はどちらとも組み合わせることができません「ザ」または「クイック」）

この問題にどのようにアプローチするかについて、誰かがガイダンスを提供できますか? 私はこの分野の専門家ではなく、Simplex がどのように機能するか (学校から戻って) について基本的な理解を持っていますが、この種の問題をモデル化する方法についての知識が不足しています。

また、他のアプローチ (線形計画法やブルート フォースを含まない) も歓迎されます。

ありがとう。

「読み取り」コマンドを使用して、CPLEX LP ファイルを CPLEX にロードしようとしています。この問題には、2次の一連の制約があると思います。しかし、私が理解していることから、CPLEX は引き続き二次計画問題を解決しようとします。

ただし、読み込もうとすると、次のエラーが発生します。

二次計画問題を読むために何か特別なことをする必要がありますか?

注: この LP ファイルを scip にロードして、次を使用して解決できます: scip -f

CPLEXJavaAPIを使用して大規模な最適化問題を解決しています。現在私はただ

これはうまく機能しますが、係数を変更するだけの場合は、このプロセスを頻繁に繰り返します。繰り返すたびに、新しいcplexオブジェクトを作成し、すべての変数を再作成します。

これを行うためのより効率的な方法はありますか？IBMのドキュメントには、「モデルをモデルのインスタンスに追加する」などの言葉があり、奇妙に聞こえますが、それは物事を再利用できることを示唆していると思いました。

より経験豊富なユーザーからの提案は素晴らしいでしょう。ありがとう。

私の問題の一部は、特定の数値の加重合計の絶対値を最小化することです。重みを見つけなければなりません。

(a1, a2 > 0), (a3, a4 < 0) となる数値 A、a1、a2、a3、a4 のセットがあるとします。

たとえば、最小の重みは 0.1 (10%)、最大は 0.4 (40%) です。加重合計がゼロになるような加重wを探しています。ゼロが不可能な場合は、可能な限りゼロに近い値。これを実現するために、単純な線形モデルを使用できます。

解を非常に高速に見つけるには、単純な線形計画で十分です。ただし、この問題の多項式アルゴリズムまたは式を見つけたいと思います。何か案は？この問題はよく知られていますか?

ありがとう！

複雑な問題があり、巡回セールスマン問題のように、既存のよく理解されているソリューションモデルが存在するか適用されるかを知りたいです。

入力：

• 開始時間と終了時間、および場所によって定義されるN回のイベントのカレンダー。
• 各待ち合わせ場所の定員（同時に収容できる最大人数）
• アテンダントがアテンダントと会うことを希望し、その招待を受け入れたこと(Ai,Aj)を示すペアのセット。AiAjAj

出力：

• アシスタントごとAに、彼が参加するすべてのイベントのクロノグラム。主な基準は、各アテンダントが、スペースの制約を満たして、招待を受け入れたアテンダントのできるだけ多くを満たす必要があるということです。

これまで、バックトラッキングを使用して解く（可能なすべての解を試す）こと、および線形計画法を使用すること（つまり、モデルを定義してシンプレックスアルゴリズムを使用して解くこと）を考えてきました。

更新：Aiあるイベントですでに会った場合Aj、彼らはもう会う必要はありません（彼らはすでに会っています）。

私はcplex Java APIを使用しています。

次のコードが使用されます。

したがって、2 つのブール値ベクトル x と y を使用するだけです。このスニペットは、たとえば inst.getSize() が 25 の小さいインスタンスでは問題なく動作します。ただし、サイズが 40 のインスタンスでは、最後の行でクラッシュします。

何かアイデアはありますか？私はそれを働かせる必要があります...

私はcplexを使用してC++でプログラムを書いています。パーセンテージを含む1つのマトリックスと、売り価格と買い価格を含む2つの配列を作成するように、ファイルから情報を読み取ることができます。：

さらに、最終的に最適化する必要がある2つのアレイを作成しました。

これは目的を作成する正しい方法ですか？

MathProgで書かれた線形プログラムがあります。私の不明なバイナリ変数は、次のように定義された 2 次元配列です。

ここで、V と L は整数の集合です。

ただし、一部の変数の値は事前にわかっているため、ILP のサイズを小さくするためにソルバーにこれを指定したいと考えています。たとえば、l=2 の場合は x[4,l] が 1 であり、l のその他の値の場合はゼロであることを知っています。現在、これを制約として指定しています。

これが、未知数のサブセットの値を事前に指定する効率的な方法であるかどうか疑問に思っていました。

理想的には、そのような情報をモデル ファイルではなく、データ セクションと一緒に別のファイルに配置したいと考えています。

与えられたHについて、次の方程式のすべての解を生成しようとしています。

H = 4の場合：

私の問題では、（他の方程式とは独立して）解くべき方程式が常に4つあります。合計2^（H-1）のソリューションがあります。前のものについては、ここに解決策があります：

これが問題を解決するRアルゴリズムです。

ただし、このアルゴリズムは必要以上の計算を行います。もっと速く行くことは可能だと確信しています。つまり、合計が>Hである順列を生成しないことを意味します

与えられたHのためのより良いアルゴリズムのアイデアはありますか？