12

準最適な出力の例

区画化されたパネルの描画を生成するアプリケーションを作成しようとしています。

N 個のキュービクル (2D 長方形) があります (N <= 40)。各キュービクルには、最小の高さ (minHeight[i]) と最小の幅 (minWidth[i]) が関連付けられています。パネル自体にも MAXIMUM_HEIGHT 制約があります。

これらの N 個のキュービクルは、各キュービクルで上記の制約が満たされるように、列方向のグリッドに配置する必要があります。

また、各列の幅は、その列の各キュービクルの最大 minWidths によって決まります。

また、各列の高さは同じでなければなりません。これにより、パネルの高さが決まります

任意の列に残っている空きスペースに予備のキュービクルを追加したり、指定された最小値を超えて任意のキュービクルの高さ/幅を増やしたりできます。ただし、キュービクルを回転させることはできません。

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

現在、最適化でキュービクルの幅を無視するだけで実装しています。minHeight が最大のキュービクルを選択し、パネルに収まるようにします。ただし、最適解を保証するものではありません。

私はこれより良くなることができますか？

編集 1: パネルの MAXIMUM_HEIGHT = 2100mm、最小幅範囲 (350mm から 800mm)、最小高さ範囲 (225mm から 2100mm)

編集 2: 問題の目的: パネル幅を最小化する (パネル領域ではない)。

4

3 に答える 3

7

処方

与えられた:

  • 各セルi = 1, ..., Mの (最小) 幅W_iと (最小) 高さH_i
  • スタックの最大許容高さT

混合整数計画は次のように定式化できます。

minimize sum { CW_k | k = 1, ..., N }
with respect to

    C_i in { 1, ..., N },                        i = 1, ..., M

    CW_k >= 0,                                   k = 1, ..., N

and subject to

[1] sum { H_i | C_i = k } <= T,                  k = 1, ..., N

[2] CW_k = max { W_i | C_i = k },                k = 1, ..., N
           (or 0 when set is empty)

十分に大きな任意の整数を選択できますN(たとえば、N = M)。

アルゴリズム

この混合整数プログラムを既存の混合整数プログラム ソルバーにプラグインして、最適なC_i, i = 1, ..., M値によって与えられるセルから列へのマッピングを決定します。

これは、自分自身を再発明したくない部分です。既存のソルバーを使用してください!

ノート

混合整数プログラム ソルバー パッケージの表現力に応じて、上記の定式化を直接適用できる場合とできない場合があります。制約[1]および[2]を指定できない場合は、それらまたは の「セット ベース」の性質のために、定式化を、この表現力を必要としない同等maxの宣言的ではないが、より標準的なものに手動で変換できます。

minimize sum { CW_k | k = 1, ..., N }
with respect to

    C_i_k in { 0, 1 },                           i = 1, ..., M; k = 1, ..., N

    CW_k >= 0,                                   k = 1, ..., N

and subject to

[1] sum { H_i * C_i_k | i = 1, ..., M } <= T,    k = 1, ..., N

[2] CW_k >= W_i * C_i_k,                         i = 1, ..., M; k = 1, ..., N

[3] sum { C_i_k | k = 1, ..., N } = 1,           i = 1, ..., M

ここで、C_i以前の変数 ( で値を取得) は、関係 の下で変数 ( で値を取得{ 1, ..., N }) に置き換えられています。C_i_k{ 0, 1 }C_i = sum { C_i_k | k = 1, ..., N }

C_i_k最終的なセルから列へのマッピングは、 によって記述されiます。kC_i_k = 1

于 2013-09-03T17:05:38.417 に答える
2

VM パッキング、特に仮想マシン コロケーションの共有認識アルゴリズムを調べることができます: http://dl.acm.org/citation.cfm?id=1989554。@ http://en.m.wikipedia.org/wiki/Bin_packing_problemについても読むことができます。問題はすでに難しいですが、キュービクルは幅または高さを共有できます。したがって、検索スペースが大きくなります。

于 2013-09-03T08:00:52.873 に答える
2

解決策の 1 つは、小部屋の列の幅を最小幅で割ることです。これにより、一列に収まるキュービクルの最大数が得られます。

最初の除算の余りをキュービクルの数で割ります。これにより、すべてのキュービクルの幅を均等にするために最小幅に追加する余分な幅が得られます。

例: キュービクルの列が 63 メートルあります。各キュービクルの最小幅は 2 メートルです。キュービクルの壁の 1 つの厚さが 2 メートルに含まれていると仮定しています。また、一方の端のキュービクルが壁に接していると想定しています。

計算すると、63 / 2 = 31.5 または 31 のキュービクルが得られます。

0.5 メートルを 31 キュービクルで割ると、16 ミリになります。したがって、キュービクルの幅は 2.016 メートルです。

于 2013-08-30T17:23:50.663 に答える