問題タブ [linear-programming]

問題

私は、SAT 最適化問題の特別なサブセットを見ています。SAT および関連トピックに慣れていない方は、関連するウィキペディアの記事をご覧ください。

NOT はなく、接続詞の標準形です。これは簡単に解決できます。ただし、ステートメント全体を真にするために、真の割り当ての数を最小限に抑えようとしています。その問題を解決する方法が見つかりませんでした。

可能な解決策

私はそれを解決するために次の方法を思いつきました：

1. 有向グラフに変換し、頂点のサブセットのみにまたがる最小全域木を検索します。エドモンドのアルゴリズムがありますが、それは頂点のサブセットではなく完全なグラフの MST を提供します。
   • 頂点のサブセットの問題を解決する Edmond のアルゴリズムのバージョンがあるのではないでしょうか?
   • 元の問題から他のアルゴリズムで解決できるグラフを作成する方法があるのではないでしょうか?
2. SAT ソルバー、LIP ソルバー、または徹底的な検索を使用します。この問題を講義資料として使用しようとしているので、これらの解決策には興味がありません。

質問

アイデアやコメントはありますか？うまくいくかもしれない他のアプローチを考え出すことができますか?

線形計画法を解くためのシンプレックス法を学んだばかりで、双対問題が何を表しているのかを理解しようとしています。

二重の問題を解決する仕組みを理解しています - それについては助けは必要ありません。(ウィキペディアでそれについて読んだ後でも)得られないのは、 dualのy変数の実際の意味です。

主な問題の変数の意味と、双対から私が理解したことをすべて一緒に例を挙げて、双対の意味を説明するのに十分親切な人に尋ねたいと思います。

プライマル:

主問題では、x1とx2は生産される製品AとBの数量です。3と5はそれぞれの販売単価です。製品はM1 ～ M3 の3 台の機械で生産されます。最初の製品を生産するには、M1で 1 時間、 M3で 3 時間の作業が必要です。2 番目のものを作成するには、 M2とM3の両方で 2 時間の作業が必要です。マシンM1、M2、M3は最大4、12、および18で動作可能時間、それぞれ。最後に、どの製品も負の数量を生産できません。

ここで、二重の問題を設定します。

今、私が理解できると思う唯一のことは、制約が意味することです: - M1で 1 時間、 M3で3 時間の作業に対して、少なくとも 3 マネーユニットを支払わなければなりません - M2と 2で 2 時間の作業に対してM3で数時間、少なくとも 5 マネー ユニットが支払われるはずです

しかし、 y1変数とy2変数の意味を理解することはできません。最終的に最小化を行うと、zの結果は主変数で同じになります (ただし、主変数は結果の下限を増やし、双対変数は上限を減らします)、双対問題の目的関数は何で構成されますか?の？

キーと値の構造のペアを持つシステムを実装しようとしています。それらはある種の線形の方法で保持される必要があり（つまり、インデックスを付けることができます）、一度位置を指定すると移動できないため、挿入は追加することしかできません（実際には多くの並べ替えはできません）。ちょうど例として、これは心に留められていることです：

私はこのようなシステムを設計して、キーが検索されたときにそのインデックスをキャッシュして、一定の時間でアクセスできるようにしました。さて、データの順序や量を予測する方法がなく、並べ替えることもできないため、線形検索よりも優れたアルゴリズムやデータ構造に関するアイデアが必要ですが、それでも制約は維持されます。 dが好きです。

誰かアイデアがありますか？私はそれを大幅にスピードアップできるとは思えませんが、これが私のシステムのコアになるので、少しでも役に立ちます。前もって感謝します！

==編集==

2つの別々の構造（ハッシュテーブルと動的配列など）を使用するというアイデアは、実際には私の最初の意図でした。残念ながら、キーと値を分離できないため、これは機能しません。キーはエラーとメッセージに使用されるため、インデックスがキャッシュされた後でも、元のキーにアクセスする必要があります。基本的に、それらは次のような配列構造体である必要があります。

Linux で GLPK を使用して線形計画問題を解決しています。私の制限の1つに、次のものがあります。

binary_val「バイナリ」として定義されている変数はどこにありますか。

値binary_valが の場合1、その合計は になり2ますか、それとも 2 進法では、または のいずれかが返されます0か1?

私はc ++でコードを書いており、それを解決するためにCPLEXを呼び出しています。非常に優れたソリューションはすぐに見つかりますが、それを改善しようとすると非常に長い時間がかかります。したがって、コードを終了するためにギャップをより大きな値に設定したいので、これを使用します。

しかし、コンパイラEpGapは、宣言されていない識別子であるというエラーを表示します。相対ギャップのデフォルト名は?

私はmatlabで線形計画法の問題を解決しようとしています.入力は

したがって、マニュアルによると、これで問題は解決するはずmin f*x with the constraints C*x=b and 0<=x<=10です。したがって、 のエントリはすべてx正でなければなりません。ただし、取得したソリューションには否定的なエントリが含まれています (以下の問題を再現する例を参照してください)。私が返すフラグは1です。これは、ドキュメントによると、メソッドが収束したことを意味します。

私は何を間違っていますか？

ここに入力があります

と

と

結果は

関連する独立した要因の重要性を調べるために、線形モデルを実行しています。モデルの例は次のとおりです。

要約を見て、各要因の重要性を確認します。

ここで、 bgrp (1 と 2) と psex (1 と 2) の 2 つのレベルのソリューションを見てみたいと思います。

これで私を助けていただければ幸いです。

よろしくお願いします、

バズ

編集：

あなたが提案した最初のモデルを実行したところ、次の結果が得られました。

上記の係数表から、bgrp1 と bgrp2 は理にかなっているように見えます。bgrp1 は、同腹子のサイズが大きく、子孫が軽い母系を表し、その結果、子孫の直腸温度が低くなります (37.70 ℃)。一方、bgrp2 は、同腹仔のサイズが小さく、子孫が重い末期系統を表し、その結果、直腸温度が高くなります (37.98 ℃)。psex1 と psex2 についても同じことができるかどうか疑問に思っていますが、係数の表に示されているのは、あなたが以前に言ったことによるものである可能性があります。

編集：こんにちはマーク、

あなたが提案した 2 つのオプションを試してみたところ、bgrp1 と psex1 が同じ値を取っていることがわかりました。

ありがとう！

二次プログラミング ライブラリの Haskell バインディングはありますか?

そうでない場合、必要を避けることができないと仮定して、簡略化されたバインディングを作成する必要があるのはどれですか? これに対して合理的に標準的に支持されているオープン ソース ライブラリはありますか?

機械学習 (R または同様のプラットフォーム) で解決したい単純な問題を定式化します。私のアルゴリズムは3 つのパラメーター(a、b、c) を取り、範囲 [0,1] のスコアs を返します。 . パラメータはすべてカテゴリです。a には 3 つのオプション、b には 4、c には 10 のオプションがあります。したがって、私のデータセットには 3 * 4 * 10 = 120 のケースがあります。高いスコアは望ましい (1 に近い) もので、低いスコアは望ましくない (0 に近い) ものです。アルゴリズムをブラック ボックスとして扱い、a、b、c を取り、s を返します。

データセットは次のようになります。

各パラメーターの s の密度をプロットすると、非常に広い分布が得られ、パフォーマンスが非常に良い (s > .8 ) 場合もあれば、悪い (s < .2 ) 場合もあります。

s が非常に高いケースを見ると、明確なパターンは見られません。全体的にパフォーマンスが悪いパラメータ値は、特定のパラメータと組み合わせると非常に良いパフォーマンスを発揮する場合があり、その逆も同様です。

特定の値 (a1 など) のパフォーマンスを測定するために、中央値を計算します。

たとえば、中央値 (a1) = .5、中央値 (b3) = .9 ですが、それらを組み合わせると、s(a_1,b_3) = .3 という低い結果が得られます。一方、中央値(a2)=.3、中央値(b1)=.4、しかしs(a2,b1)=.7。

常にうまく機能するパラメーター値が存在しないことを考えると、統計的に有意な方法で (つまり、たまたま非常に高いスコアを持つ外れ値を除外して) 一緒にうまく機能すると思われる (2 つのパラメーターの) 組み合わせを探す必要があると思います。言い換えれば、最適なパラメーターを選択するためのポリシーを取得したいと考えています。たとえば、最高のパフォーマンスを発揮する組み合わせは (a1,b3)、(a2,b1) などです。

さて、これは機械学習を使って解ける最適化問題だと思います。

このコンテキストで推奨される標準的な手法は何ですか?

編集: 誰かがglpkを使用した線形計画法ソリューションを提案しましたが、線形計画法をこの問題に適用する方法がわかりません。

最適化問題を見ると、たくさんのオプションがあります。1つは線形計画法です。LPがどのように機能するかは抽象的な言葉で理解できますが、特定の問題がLPに適しているかどうかを確認するのは難しいと思います。この決定を導くのに役立つヒューリスティックはありますか？

たとえば、「このタイプのマイニングを行うための良い方法はありますか？」で説明されている作業です。問題を正しく構成する方法を理解するまでに数週間かかりました。最初に「言い方」を見なくても、LPで問題が解決できることを「事前に」知ることは可能でしょうか。

問題がLPに適しているかどうかを判断するために使用できるチェックリストはありますか？このトピックの標準（読み取り可能な）リファレンスはありますか？