モデリング基本概念

LocalSolverは、効率的に、ユーザー定義の目的関数という観点から最適な解を探索し、ユーザーの最適化モデルで定義した探索領域を調べることができます。これは、いかなるオペレーションズ・リサーチのアプローチと同様に、「問題のモデリング」が重要な作業であることを意味します。「明確な目的関数、制約の正しい設定、適切な意思決定変数の選択」の重要性をわたしたちは強調しています。

意思決定変数と内部変数を区別する

モデリング作業の最初のステップは、意思決定変数の集合を選択します。LocalSolver 2.0では、意思決定変数はバイナリでなければなりません。バイナリ変数はboolキーワードによって代入します。
これらの変数は、取られる意思決定を表現しています。自身の意思決定変数を定義したら、これらの変数が、他の変数から予測できなかったか考察してください。

例えば、車両割当て問題を考察します。

// A BAD SET OF DECISION VARIABLES FOR THE CAR SEQUENCING PROBLEM
// cp[c][p] = 1 if class c is at position p, and 0 otherwise
cp[1..nbClasses][1..nbPositions] <- bool();


// op[o][p] = 1 if option o appears at position p, and 0 otherwise   
op[o in 1..nbOptions][p in 1..nbPositions] <- bool();

// constraints linking variables op[o][p] to cp[c][p]

for[o in 1..nbOptions][p in 1..nbPositions]  
  constraint op[o][p] = or[c in 1..nbClasses : options[c][o]](cp[c][p]);

上記のモデルの中で、ユーザーは、制約の集合でリンクした、意思決定変数の2つの族を代入しました。このモデルは、このモデルの解が車両割当て問題の解であるという意味で有効です。しかし、あまりにも意思決定変数が多いので、このモデルは狭い探索領域を定義しています:明確にcp[c][p]変数の値を知るには、十分に解の定義を行うことで、他のすべての変数をこれら変数の値から予測することができます。従って、内部表現として、op[o][p]を代入した下記のモデルがより良い表現となります。

// 0-1 decisions: 
// cp[c][p] = 1 if class c is at position p, and 0 otherwise
cp[1..nbClasses][1..nbPositions] <- bool();


// expressions: 
// op[o][p] = 1 if option o appears at position p, and 0 otherwise
op[o in 1..nbOptions][p in 1..nbPositions] <- or[c in 1..nbClasses : options[c][o]](cp[c][p]);

完全主義の読者は、nbPositions意思決定変数が、まだ、cp[0][p] <- 1 - sum[i in 2..nbClasses]cp[i][p]を定義することで排除できることに気づかれたと思います。 さらによいものが良いものの敵となるため、過度な記述は控えてください。より正確に、変数を個体としてではなく、変数の族として考えてください。

この車両割当て問題がとても簡単な問題に見えてくることでしょう。この問題よりも難解なケースは製鉄所のスラブ・デザインです。この問題では、オーダーが様々なサイズのスラブに割り当てられます。目的は、使用される原材料(少なくとも1つのオーダーを持つスラブのサイズ)を最小化することです。この問題の簡単なモデルはオーダーoがスラブsに割り当てられるならば、様々なサイズのスラブを十分に定義し、x[o][s]変数が1に等しいことを完全に定義することです。このモデル、スラブの使用法及び、(内部表現)、目的関数内で直接使用されているこがわかります。

// slab s is used if at least one order is assigned to this slab
use[s in 1..nbSlabs] <- or[o in 1..nbOrders](x[o][s]);
  
// objective function

minimize sum[s in 1..nbSlabs](use[s] * size[s]);

このモデルは、CSPLib インスタンス上で正確かつ、非常に適切に実行します。しかし、その内容からスラブのサイズが予測可能ならば、よりいっそう強靭なモデル構築ができます。各スラブ内容に対する各ムーブ後に実行し、最小かつ十分な容量のスラブに移動します。注:この問題に対する制約プログラミングモデルも同じアプローチを用います。下記はこのモデルの重要な行で。完全なモデルは例題集で入手頂けます。

for [j in 1..nbOrders] {
  slabContent[j] <- sum[i in 1..nbOrders](orders[i] * x[i][j]);
  constraint slabContent[j] <= maxSize;
  // threshold detection variables

  t[j][1] <- slabContent[j] > 0;
  t[j][k in 2..nbSlabSizes] <- slabContent[j] > slabSizes[k-1];
}


/* ... */  

obj <- sum[j in 1..nbOrders](slabSizes[1] * t[j][1] 
  + sum[k in 2..nbSlabSizes]((slabSizes[k] - slabSizes[k-1]) * t[j][k])) 
  - sumSizeOrders;

制約式と最優先の目的を区別する

自身の意思決定変数の集合の選択後、制約、すなわち、実行可能だと見なした解を満たすために、論理式を選択します。これらの表現式にキーワードconstraintを行頭に付けます。ローカル・サーチは最適化問題に適しているので、良い解を発見することが難しいと感じるユーザー問題でも、比較的安易に実行可能解を発見できます。そして、ユーザー問題内にあるいくつかの「制約」が実際、最優先目的であるため、制約条件が問題の構造属性として保たれるべきであることを意味します。

http://www.csplib.org.の車両割当て問題とその定義を考察してください。

ある工場では、膨大な数の車両製造を行っています。;
様々なオプションはベーシックモデル上の変型として使用しているためオプションは同一ではありません。組み立てラインには、様々なオプションの取り付けを行う異なった作業場が複数箇所あります。(エアコンの取り付け、サンルーフの取り付け等)これらの作業場では、組み立てラインに沿って通過している車両に対して一定のパーセンテージのみ処理するよう設計されています。(...) 各作業場の処理能力を越えないように、且つ車両を連続的に配置します。例えば、特定の作業場ではラインに沿って通過している車両の半分までの処理能力しか持ちません。オプションは1台の車両に最大2つのオプションを要求するよう生成します。

上記の定義を慎重に読んでいただくと、これが純粋な充足問題として表現されていることがわかります。
次に現実問題を考察します。:
将来的に、製造される車両の過半数以上に、制約「1台の車両に最大2つのオプションを要求する」と設定されたオプションが必要な場合、自動車メーカーは何をすればよいのでしょうか?
はっきりと、簡潔に「解が見つからない」と返答する最適化システムは全然役に立たないことでしょう。
この現実問題におけるこの例題では、他の制約(ビジネス制約と呼ぶ場合もある)が満たされるべきプロパティであり、制約のうち、いくつかが問題の構造を定義しています。
実際、それらすべてのプロパティを充足することが可能かどうか未知なため、自発的に、「するべきです」という用語を使い、「しなければなりません」という用語は使いません。
ここで、唯一の構造制約は、組み立てラインの各作業場が少なくとも1台の車両を含んでいることです。
ここで、ユーザーはいくつかの最適化モデルを定義して構いません。
例えば、作業場の制約(任意Qにおける最大P車両の)は構造であり、最小化される目的関数が組み立てライン上の使用されていない作業場の数であると考えることができます。
すなわち、組み立てラインの制約に左右される生産された車両数の最大化を行います。
この車両割当て問題は、通常、逆の観点で考えられています:
すべての車両を生産しなければならず、作業場の制約の違反を計算する違反を最小化します。
この計算はWindows上では単に、過剰設備の合計です。:

// expressions: compute the number of violations in each window
nbViolationsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1] 
  <- max(nbCarsWindows[o][p]-ratioNums[o], 0);


// objective: minimize the sum of violations for all options and all windows
obj <- sum[o in 1..nbOptions]
  [p in 1..nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);

minimize obj;

上記の通り、制約cを目的に変えることは必ずしも最大化cになるわけではありません。
実際に、制約がしばし比較の形式を取るので、多くの場合、max(0、a-b)の最小化に、または<= bの充足a == bは充足dist(a、b)の最小化に変化します。
ここで、純粋な充足モデルは最適化モデルに変り、それゆえ、目的関数は1つしかありません。
そして、自身のオリジナル問題が、表現costを最小化する必要がある最適化問題の場合、そのいくつかの「制約」が識別できるなら、最優先目的(minimize violations)として生成すべきであり、その後、予約語で最適化される複合目的関数を持つようになります。:

minimize violations;
minimize cost;

このような場合、複数の指定制限時間を処理するLocalSolverの能力が有効です。一般に、問題解決の時間が、合計60秒ある場合、設定しているlsTimeLimit={50、10}は、50秒がviolations (コストへの影響は考えない)の最小化に割かれる一方、残りの10秒で双方の目的を考慮(予約語)するために割かれます。
最適解(ここでは0)が1秒で見つかった場合、当然のことながら、LocalSolverには、2番目の目的を最適化するために59秒残っていることになります。
つまり、制約集合の選択時、上記二つの点が過剰にならないよう気を配る必要があります:

  • 多くの制約を追加することは、LocalSolverが、解(戻された解のステータスは実行不可能)を全く発見できない、または実行可能解から別の解への移動が非常に困難となり、その結果、実行不可能なムーブが高い割合で生じるモデルになることでしょう。
  • 多くの制約を目的に変えることは、構造体のないモデルを生じさせる原因となる一方、LocalSolverの強みは、実行可能性、従って「意味のある」ムーブを維持しつつ実行することです。

ユーザー定義の目的関数

LocalSolverの演算子により、条件(演算子iif)および高性能な非線形表現(product, max, square root,)で、簡単に目的関数を記述できます。ごくまれに、オリジナル関数(ユーザー定義関数)をわずかに修正することでよりいっそう良い解を得られる場合もあります。例えば、Googleマシンの配置展問題で、目的関数の最初のデジタル化に重点を置くという多様性はとても参考になります。

// Classical technique for favoring diversification of the search when the 
// objective value contains numerous digits. We iteratively optimize the most 
// significant digits, passing from millions to hundred of thousands, etc.   
minimize obj / 1000000;
minimize obj / 100000;

minimize obj / 10000;
minimize obj / 1000;
minimize obj;

注:この例題で、objを直接最小化した結果、とても良い解を得ますが、競合コンテキストはこの簡単な改良で、数%の増加を実現させました。

このページの先頭へ