問題タブ [bin-packing]

この質問に似たものを投稿しましたが、コードの実装に問題があります。

重量、価格、本のタイトルなどを含む HTML ファイルからデータを収集する python プログラムがあります。各パッケージが 10 ポンドを超えないように、本を「n」個のパッケージに分類したいと考えています。エラーなしでプログラムを実行でき、情報は抽出されますが、パッキングに関する結果は得られません。

これが私が持っているコードです。誰かが私に提案をしてもらえますか?

2D ビン パッキングの問題を解決するソルバーを探しています。「バイナリ ツリー アルゴリズム」を提案する投稿をいくつか見ましたが、約 200,000 個のビンがあるため、アルゴリズムがスケーラブルかどうかはわかりません。

ぐろびのことを考えていました。しかし、Gurobi で問題をモデル化する方法がわかりません。私が使用できる利用可能なモデルを知っている人はいますか? または、NPが難しいという事実を考慮して、「正確に近い」ソリューションを提供できるJavaコードはありますか?

ありがとう

/ミナ

問題: それぞれ RAM R _i、CPU C _i
を持つN 個の物理マシン (PM)それぞれRAM 要件r _iとc _iを持つ現在スケジュールされている VM のセットがあります 。ある PM から別の PM に VM を移動 (移行) するにはコストがかかります。そのラムr _iに依存する関連付けられています。VM のない PM は、電力を節約するためにシャットダウンされます。 私たちの目標は、いくつかの VM を移行することによって (N,migration cost) の加重合計を最小限に抑えることです。つまり、稼働中の PM の数を最小限に抑え、過度の移行によってサービス レベルを低下させないようにすることです。

私のアプローチ:
ブルート フォース アプローチは、負荷が最小限の PM を選択し、最初にフィット減少アルゴリズムによってその VM を他の PM に適合させようとするか、負荷レベルに基づいて被害者の PM とターゲット PM を選択し、可能であれば被害者を移動することで被害者をシャットダウンすることができます。 VM からターゲットへ。Baadalのデータ(IIT-D クラウド)
でこの貪欲なアプローチを試しましたが

動的 VM 統合のための Ant コロニーの最適化についても調べてみましたが、あまり理解できませんでした。リンクを使用しました。
http://dumas.ccsd.cnrs.fr/docs/00/72/52/15/PDF/Esnault.pdf http://hal.archives-ouvertes.fr/docs/00/72/38/56/PDF /RR-8032.pdf

誰かが解決策を明確にするか、パフォーマンスを向上させるための新しいアプローチ/リソースを提案してください。
私は基本的に、物理的な最適化ではなくアルゴリズムを探しています。また、多くの営利組織がこれらのソリューションを提供していることも知っていますが、基礎となるアルゴリズムについてもっと知りたいと思っていました.

前もって感謝します。

この質問は、プロセスの割り当てに関する別の質問に触発されています。これは、そこで議論されている問題をひねり、強化したものです。

n 個のプロセスがあり、可能な限り少数のプロセッサに割り当てる必要があります。各プロセスにはスケジュールされた開始時刻と終了時刻があり、1 から始まる時間単位で定義します。プロセスは、時間単位の連続したシーケンスで実行されます。プロセッサは、任意の数の非重複プロセスを実行するようにスケジュールできます。

明らかな貪欲なアルゴリズムは次のとおりです。

各ステップで、残りのプロセスの重複しない最大のセットを次のプロセッサにスケジュールします。

重複しない最大のセットはどのように選択されますか? アルゴリズムを非決定論的のままにします。これにより、分析が容易になり、2 つのサブ質問に分割しやすくなります。

基本的に、前の質問は、アルゴリズムが不運な場合の動作に関するものです。このアルゴリズムが最適でない割り当てを生成する可能性がある (つまり、必要以上のプロセッサが必要になる)最小のnは何ですか? 答えはn =4 であることがわかります。2 つのプロセッサで十分な場合もありますが、貪欲なアルゴリズムでは 3 つのプロセッサが必要になる場合があります (運が良ければ、2 つのステップで実行されます)。

この質問は、非決定論が常に幸運である場合に何が起こるかに関するものです。

このアルゴリズムが準最適であることが保証されている最小のnは? つまり、貪欲なアルゴリズムが必要以上のプロセスを使用しなければならない一連のプロセスを見つけることができる最小のnは?

Stack Overflowでは、自分の質問を尋ねて回答することを積極的に奨励しているので、ここでそうします。私の部分的な回答を改善できるかどうか教えてください。

私は、ビンパッキングのバリエーションである問題に取り組んでいますが、追加の制約があるもう少し一般的な形式です。問題の定義は次のとおりです。

オブジェクト クラスにグループ化できるさまざまなサイズのオブジェクトがあります。異なる容量のビンがあり、これらもビン クラスにグループ化されています (同じクラス内のすべてのビンは同じ容量です)。オブジェクト クラスには、配置できるビンに関する制約があります。たとえば、クラス「A」のオブジェクトは、ビン クラス「X」または「Y」のいずれかに配置できます。目的は、オブジェクトの特定のセットの最適なパッキングを生成できる、各クラスのビンの最小数を見つけることです。

この問題の適切な数学的定式化と、あなたが見つけた解決方法はありますか? これは、同じ方法を適用できるビンパッキング問題の拡張ですか? NPハードなのはわかります。問題に取り組む方法について多くを見つけることができなかったので、正しい方向に向けていただければ非常に助かります.