MIP からLSPへの移行方法

LocalSolverは算術演算子、sum、product 及び演算比較を提供しているため、いかなる線形計画ももしも、整数変数はバイナリ変数の加重和として記述されていれば、LocalSolverモデリング言語で直接、記述することができます。しかし、このようなモデルは、最大パフォーマンスを目的に自身のモデルでLocal searchおよび単一演算子を実行したい場合、適さない場合があります。
step by step exampleに掲載されている車両投入問題を熟考してみましょう。ここではこの問題を代表的な線形計画として、LocalSolverのシンタックスを使用し記述しています。全ての変数はすでに定義されていることを前提としています。

// A MIP-like MODEL FOR THE CAR SEQUENCING PROBLEM
for[c in 1..nbClasses]
  constraint sum[p in 1..nbPositions](cp[c][p]) == card[c];

for[p in 1..nbPositions]
  constraint sum[c in 1..nbClasses](cp[c][p]) == 1;

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

for[o in 1..nbOptions][j in 1..nbPositions-Q[o]+1] 
  constraint nbVehicles[o][j] == sum[k in 1..Q[o]](op[o][j+k-1]);

for[o in 1..nbOptions][j in 1..nbPositions-Q[o]+1] {
  constraint violations[o][j] >= nbVehicles[o][j] -P[o];
  constraint violations[o][j] >= 0;
}

constraint obj == sum[o in 1..nbOptions][p in 1..nbPositions-Q[o]+1](violations[o][p]);

minimize obj;

意思決定及び内部変数表現

As explained in our modeling principles , モデリング概念の解説として、最も重要なモデリングの意思決定は意思決定変数の集合を選択することです。ここでは、他の変数、すべてが、cp[c][p]の変数によるものと推測されるため、cp[c][p]の集合が最も最善な意思決定変数です。ここで、内部変数は次のように、記述します。
例えば、制約式nbVehicles[o][j] == sum[k in 1..Q[o]](op[o][j+k-1])は条件nbVehicles[o][j] <- sum[k in 1..Q[o]](op[o][j+k-1]).を定義する表現式に変わります。

線形化の代わりに非線形演算子を使用する

ここでは、このモデル内のいくつかの等式は実際に演算または論理表現の線形化であることを確認することができます。例えば制約式op[o][p] >= sum[c in 1..nbClasses : options[c][o]](cp[c][p])は単にop[o][p]は、与えられた条件の一つが1と等しいとき、1と等しいということを述べているだけです。もっとも自然な表現として、

op[o][p] <- or[c in 1..nbClasses : options[c][o]](cp[c][p])

最後に、violations[o][j]上の制約式の組がまさに、特定の数の変数の最大化を定義するための線形形式です。この表現をLocalSolverで直接記述すると下記のようになります。

violations[o][j] <- max( nbVehicles[o][j] -P[o], 0)

同様に、全ての最大化に関する線形化は、条件または論理積は演算子max, iifやandを使用し直接localSolver形式に変換されます。区分的に、線形関数は単純に、同じように記述することが可能です。自身のMIPが区分的線形関数（バイナリ変数と関連付け可能な）を含む場合、全ての間隔[c[i-1],c[i]] we have Y = a[i] * X + b[i] with i in (1..3)において、Yはf(X)に等しいとすることができます。その後すぐに、Yを下記のように定義します。

Y <- X < c[1] ? a[1]*X+b[1] : (X < c[2] ? a[2]*X+b[2] : a[3]*X+b[3]);

これらの変換後、下記のモデルを得ます。

function model() {	
  cp[1..nbClasses][1..nbPositions] <- bool();

  for [c in 1..nbClasses] 
    constraint sum[p in 1..nbPositions](cp[c][p]) == nbCars[c];

  for [p in 1..nbPositions] 
    constraint sum[c in 1..nbClasses](cp[c][p]) == 1;

  op[o in 1..nbOptions][p in 1..nbPositions] <- or[c in 1..nbClasses : options[c][o]](cp[c][p]);

  nbCarsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1] <- 
       sum[k in 1..ratioDenoms[o]](op[o][p+k-1]);

  nbViolationsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1] <-
       max(nbCarsWindows[o][p]-ratioNums[o], 0);

  obj <- sum[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);
  minimize obj;	
}

必要のない制約式を削除する

自身のモデルに有効な不等式が含まれている場合、それらを削除することが可能です。LocalSolverはモデルの緩和に頼っていないため、これらの不等式はモデルに重みを付けるだけです。同様に制約割れをしている対称性を省略する必要があります：LocalSolverはツリーをベースとした探索に頼らないため、対称性を壊すことは実行可能解から他の解への移行をより困難にします。一般的に、それはLocalSolverが付近のより良い解を考慮し難くするでしょう。

このページの先頭へ