問題タブ [operations-research]

金属製品工場の話です。長い鉄の棒を細かく切断してさまざまな製品に加工する機械があります。

たとえば、次の長さと数量のバーを製造する必要があります: 248mm を 2 本、1150mm を 5 本、2843mm を 6 本、3621mm を 3 本。

それがパーティショニング出力です。

入力側には、(例として) 2500mm のバーが 3 本、5000mm のバーが 2 本、8000mm のバーが 6 本、10000mm のバーが 3 本あります。

入力バーを最適にカットする方法を見つける必要があります。カット後の残りの部分 (小さすぎて使用できない残りの部分) は、できるだけ小さくする必要があります。

考えられるすべての組み合わせを単純に作成し、それらの中から最適なものを選択するアルゴリズムを作成しました。コードは機能しますが、入力と出力が少し大きくなるとすぐに、計算が非常に長く続く可能性があるため、問題への新しいアプローチを見つけなければなりません。

ヒントはありますか？

ここで定義されている割り当て問題の標準定義を見ています

私の質問は、2 つの制約を処理することです (ラテックス表記が続きます)。

具体的には、なぜ 2 番目の制約が必要なのですか? 最初のものはすでに x_{ij} のすべてのペアをカバーしていませんか?

Mosek に代わるオープンソースはありますか?

基本的に、大規模な凸最適化ソルバー パッケージを探しています。

ありがとう！

編集：

先に言い忘れましたが、問題は非線形です。ほとんどは 2 次ですが、場合によっては非 2 次制約 + 非 2 次目的が必要になる場合があります

モンスター（N頭）を倒すには、2丁の銃AとBを使用する必要があります。銃Aを使用すると、6つの頭をカットしますが、モンスターが死なない場合（頭の数が0より大きい場合）、3つの頭が成長します。銃Bを使用すると、4つの頭がカットされますが、モンスターが死なない場合は2つの頭が成長します。N <（ガンが切断できるヘッドの数）の場合、ガンは使用できません。そして、N = -1の場合、モンスターとハンターの両方が死にます。

問題によって、モンスターを殺すことが可能かどうか、ハンターがモンスターを殺そうとして死ぬかどうか、最短経路を見つける必要があります。

上記の問題を解決するために、次のPythonプログラムを作成しました。

サンプルデータ（質問で提供）：N = 10の場合、最短経路はAABです。

プログラムのどこで間違ったのですか？この問題を解決するためのより良い方法は何ですか？

ノード割り当ての問題

私が解決したい問題は、指定された入力ポイントとして指定されたブルー ノード (ソース ノード) で指定されたマップをテッセレーションすることです。これができたら、各セル内にいくつのブラック ノード (デマンド ノード) があるかを確認したいと思います。そのセルに関連付けられた青色ノードに割り当てます。

フォーチュンのアルゴリズムを使用せずにこれを行う簡単な方法があるかどうかを知りたいのですが、Mahotas.segmentation.gvoronoi(image) sourceと呼ばれるこの関数に出会いました。しかし、これで問題が解決するかどうかはわかりません。

また、このセグメンテーションを行うより良い方法があれば教えてください (ボロノイ テッセレーション以外)。クラスタリング アルゴリズムが適切な選択であるかどうかはわかりません。私はプログラミング初心者です。

任意のサイズのn 個の四角形を取り、それらすべてに収まる十分な大きさの四角形を計算し、その領域を最小化して無駄な領域を最小限に抑え、その中のすべての小さな四角形の位置を返す アルゴリズムが必要です。

これを実装するために必要な特定のタスクは、個々の PNG ファイルを取得し、すべての画像を含む大きな PNG を作成するスプライト シート コンパイラで実行されるため 、実行時に個々のフレームをこのサーフェスから ブリットできます。

あると便利な機能は、特定の特定の幅/高さの比率を目指していることですが、必須ではありません。

別の言語に移植できる単純で汎用的なコードを好むでしょう。

R の survreg から推定されたパラメーターを使用して逆ワイブル分布を生成しようとしています。つまり、特定の確率 (MS Excel で実装された小さなシミュレーション モデルでは乱数になります) に対して、私のパラメータを使用して失敗するまでの予想時間。逆ワイブル分布の一般的な形式は次のようになると理解しています。

ここで、a と b はそれぞれ形状とスケールのパラメーターであり、X は希望する失敗までの時間です。私の問題は、survreg からの切片と共変量パラメーターの解釈にあります。これらのパラメータがあります。時間の単位は日です:

R の係数が「極値分布」からのものであることをヘルプ ファイルで読みましたが、これが実際に何を意味し、式で直接使用されている標準スケール パラメーターに「戻る」方法がわかりません。b=7.79 と a=1.51 を使用すると、無意味な答えが得られます。基本グループと「グループ 2」の両方の時間を生成できるようにしたいと考えています。また、私は自分で分析を行っていないため、データをさらに調査することはできません.

データ内の「コミュニティ」を視覚的に識別できるように、2次元のバイナリ行列を並べ替える方法を探しています。私のデータセットは、グループメンバーシップ（つまり、人々と彼らが属するグループのリスト）に基づいています。例えば：

私はこれを与えるソートアルゴリズムを探しています：

「並べ替えられた」データの別の例は、次の場所にあります。http: //mbostock.github.com/protovis/ex/matrix.html この例では、作成者は並べ替えに使用される「コミュニティ検出アルゴリズム」を参照しています。ディメンション間にメンバーシップがないため、私のデータは異なります（つまり、最初のディメンション（人）は2番目のディメンション（グループ）のメンバーです。

これについて詳細に説明している論文を見つけました：http：//ricerca.mat.uniroma3.it/users/colanton/docs/visual.pdf（警告：PDF）

要約すると、私はメンバーシップデータを取得し、データ内の「コミュニティ」を見つけようとして、それを視覚的に表現しています。

私はここでいくつかの助けになるかもしれない同様の議論を見つけました： バイナリ2Dマトリックスのソート？ グラフでコミュニティを検出するためのアルゴリズムの実装はありますか？

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

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

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

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

ありがとう！

私はMathProgで一見単純なモデルに苦労しています。モデルは次のとおりです。

実行するとエラーが発生しますfeasibility.glp:11: b[v1,w1] out of domain。何が悪いのかわかりません。さらに奇妙なことに、関連する行を変更するとb[j,i]、まったく同じエラーが発生し続けます（b[w1,v1]予想どおりではありません）。

私はAMPLダイエットの例を注意深く調べましたが、モデルの関連部分に違いは見られませんでしたが、それでも機能しません。なにが問題ですか？