1. LocalSolverホーム
  2. LocalSolver製品概要
  3. LocalSolver例題集
  4. Google machine reassignment(Googleマシンの配置展開【相互排除、資源等】)

Google machine reassignment(Googleマシンの配置展開【相互排除、資源等】)

Google マシンの配置展開(2012 ROADEF/EURO CHALLENGE)

先に掲載されている7例題の成功により、フランス・オペレーションリサーチ学会(ROADEF)は、Googleと、例外的にROADEF/EURO Challenge 2012でマシンの配置展開問題に取り組んできたヨーロッパ・オペレーション・リサーチ学会(EURO)と共同参加しました。

この挑戦の狙いは、1組のマシンに対する使用量を改善することです。
例えば、マシンには、RAMやCPUなどの資源、そして、これら資源を消費する実行プロセスなど複数の資源が搭載されています。
まず最初に、マシンに各プロセスが割り当てられます。マシンの使用量を改善させるために、プロセスは、1つのマシンから他のマシンへ移動可能にします。制約で、(例えば、資源の容量制約や、そのコストなど)移動可能プロセスを制限します。この問題のソリューションは全ての制約と目的関数であるコストの最小化を十分に満たした新しい、プロセス-マシン割当てとなります。

詳細情報は http://challenge.roadef.org/2012/enを参照ください。

LocalSolver 2.0は、4GB ARMを搭載した汎用的なコンピュータ上では5分の実行時間内で集合A(100,000の意思決定まで)から10のインスタンスを解くことが可能です。下記はLocalSolverチームの詳細結果です。

instances   expressions    decisions   constraints       solutions
A1-1              6,020          400           503      44,306,501
A1-2          1,812,044      100,000       100,595     787,434,004
A1-3          1,423,438      100,000        26,097     583,014,803
A1-4            753,404       50,000         9,913     272,304,480
A1-5            229,213       12,000        13,905     727,578,410
A2-1          1,415,324      100,000       102,300       5,934,529
A2-2          3,769,381      100,000        19,770   1,163,672,839
A2-3          3,843,977      100,000        20,213   1,555,764,432
A2-4          1,537,771       50,000        13,373   2,089,185,551
A2-5          1,556,017       50,000        13,260     575,691,649

LocalSolver2.0は集合B(意思決定変数0.5Mから250Mまで、Mは100万を意味します)から複数の大規模なインスタンスを解くことが可能です。これは、RAMの容量に左右されますが、4GBのRAMを使用した場合、B1、B2を処理することが可能です。40GBのRAMを使用した場合は、B7、B9、B10を除く、全てのインスタンスを処理することが可能です。後者の場合(40GBのRAMを使用)、注目すべき点は、1千万の意思決定変数、1億1,400万の表現式、160万の制約式を持つB4インスタンスを処理することが可能なことです。

instances   machines   processes   decisions
B1               100        5000         .5M
B2               100        5000         .5M
B3               100       20000          2M
B4              1000       10000         10M
B5               100       40000          4M
B6               200       40000          8M
B7              4000       40000        160M
B8               100       50000          5M
B9              1000       50000         50M
B10             5000       50000        250M

LSP ソースファイル


/********** google_machine_reassignment.lsp **********/

/* Reads input data. */
function input() {
  
  usage = "\nUsage: localsolver google_machine_reassignment.lsp "
    + "modelPath=model.txt assignmentPath=assignment.txt "
    + "solutionPath=solution.txt\n";
    
  if (modelPath == nil) 
    error(usage + "Please set modelPath in command line.");
  if (assignmentPath == nil) 
    error(usage + "Please set assignmentPath in command line.");
  if (solutionPath == nil) 
    error(usage + "Please set solutionPath in command line.");
  
  // read instance data from model file
  modelFile = openRead(modelPath);
  assignmentFile = openRead(assignmentPath);
  
  nbResources = readInt(modelFile);
  for [r in 0..nbResources-1] {
    transient[r] = readInt(modelFile); 
    rweight[r] = readInt(modelFile);
  }
  
  nbMachines = readInt(modelFile);
  maxLocation = -1;
  for [m in 0..nbMachines-1] {
    neighborhood[m] = readInt(modelFile); 
    location[m] = readInt(modelFile);
    if (location[m] > maxLocation) maxLocation = location[m];
    capacity[m][0..nbResources-1] = readInt(modelFile);
    safety[m][0..nbResources-1] = readInt(modelFile);
    mcost[m][0..nbMachines-1] = readInt(modelFile);
  }
  
  nbServices = readInt(modelFile);
  for [s in 0..nbServices-1] {
    spread[s] = readInt(modelFile); 
    nbDepends[s] = readInt(modelFile);
    dependency[s][0..nbDepends[s]-1] = readInt(modelFile);      
  }
  
  nbProcesses = readInt(modelFile);
  for [p in 0..nbProcesses-1] {
    service[p] = readInt(modelFile);            
    require[p][0..nbResources-1] = readInt(modelFile);      
    pcost[p] = readInt(modelFile);
  }
  
  nbBalances = readInt(modelFile);
  for [b in 0..nbBalances-1] {
    resource1[b] = readInt(modelFile);            
    resource2[b] = readInt(modelFile);            
    target[b] = readInt(modelFile);
    bweight[b] = readInt(modelFile);
  }
  
  wpmc = readInt(modelFile);
  wsmc = readInt(modelFile);
  wmmc = readInt(modelFile);  
  
  // read initial assignment from assignment file
  initialMachine[0..nbProcesses-1] = readInt(assignmentFile);
}

/** 
 * Models the problem with 0-1 decisions. Constraints and objectives are 
 * introduced in the same order as in the challenge subject.
 *
 * Notations:
 *  x[p][m] = 1 if process p is assigned to machine m, and 0 otherwise.
 *  u[m][r] is the consumption of resource r on machine m.
 *  n[p] is the neighborhood of the machine assigned to process p.
 *  a[m][r] is the unconsumed capacity of resource r on machine m.
 *
**/
function model() {
  // 0-1 decisions
  x[0..nbProcesses-1][0..nbMachines-1] <- bool();
  
  // each process must be assigned to a single machine
  for [p in 0..nbProcesses-1]
    constraint sum[m in 0..nbMachines-1](x[p][m]) == 1;
  
  // capacity constraints
  for [m in 0..nbMachines-1][r in 0..nbResources-1] {
    u[m][r] <- sum[p in 0..nbProcesses-1](require[p][r] * x[p][m]);
    constraint u[m][r] <= capacity[m][r];
  }
  
  // conflict constraints
  processByService[0..nbServices-1] = {}; // assigns an empty map
  for [p in 0..nbProcesses-1] {
    s = service[p];
    processByService[s][count(processByService[s])] = p;
  }
  for [s in 0..nbServices-1][m in 0..nbMachines-1]
    constraint sum[p in processByService[s]](x[p][m]) <= 1;
  
  // spread constraints
  machineByLocation[0..maxLocation] = {}; // assigns an empty map
  for [m in 0 .. nbMachines-1] {
    l = location[m];
    machineByLocation[l][count(machineByLocation[l])] = m;
  }
  for [s in 0..nbServices-1] {
    sl[s] <- sum[l in 0..maxLocation](
      or[p in processByService[s]][m in machineByLocation[l]](x[p][m]));
    constraint sl[s] >= spread[s];
  }
  
  // dependency constraints
  n[p in 0..nbProcesses-1] <- 
    sum[m in 0..nbMachines-1](neighborhood[m] * x[p][m]);  
  for [sa in 0..nbServices-1][i in 0..nbDepends[sa]-1] {
    sb = dependency[sa][i];
    for[pa in processByService[sa]]
      constraint or[pb in processByService[sb]](n[pa] == n[pb]); 
  }
  
  // transient usage constraints
  for [m in 0..nbMachines-1][r in 0..nbResources-1 : transient[r] == 1] {
    initiallyConsumed = 0;
    for [p in 0..nbProcesses-1 : initialMachine[p] == m] 
      initiallyConsumed = initiallyConsumed + require[p][r];
    residual = capacity[m][r] - initiallyConsumed;
    constraint sum[p in 0..nbProcesses-1 : initialMachine[p] != m](
    require[p][r] * x[p][m]) <= residual;
  }
  
  // objective: load cost 
  loadCost[r in 0..nbResources-1] <- 
    sum[m in 0..nbMachines-1](max(u[m][r] - safety[m][r], 0)); 
  totalLoadCost <- sum[r in 0..nbResources-1](rweight[r] * loadCost[r]);
  
  // objective: balance cost
  a[m in 0..nbMachines-1][r in 0..nbResources-1] <- capacity[m][r] - u[m][r];  
  for [b in 0..nbBalances-1] {  
    r1 = resource1[b]; 
    r2 = resource2[b]; 
    tg = target[b];
    balanceCost[b] <- 
      sum[m in 0..nbMachines-1](max(tg * a[m][r1] - a[m][r2], 0));
  }
  if (nbBalances == 0) totalBalanceCost <- 0;
  else totalBalanceCost <- 
    sum[b in 0..nbBalances-1](bweight[b] * balanceCost[b]);
  
  // objective: process move cost
  processMoveCost <- 
    sum[p in 0..nbProcesses-1](pcost[p] * not(x[p][initialMachine[p]]));  
  
  // objective: service move cost  
  for [s in 0..nbServices-1] 
    nbMoved[s] <- sum[p in 0..nbProcesses-1 : service[p] == s](
      not(x[p][initialMachine[p]]));
  serviceMoveCost <- max[s in 0..nbServices-1](nbMoved[s]);
  
  // objective: machine move cost
  for [p in 0..nbProcesses-1] {
    m0 = initialMachine[p];
    machineMoveCost[p] <- sum[m in 0..nbMachines-1 : m != m0](
      mcost[m0][m] * x[p][m]);
  }  
  totalMachineMoveCost <- sum[p in 0..nbProcesses-1](machineMoveCost[p]);
  
  // objective: total cost
  obj <- totalLoadCost 
    + totalBalanceCost 
    + wpmc * processMoveCost 
    + wsmc * serviceMoveCost
    + wmmc * totalMachineMoveCost;
  
  // 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;
}

/* Displays the terms composing the objective function. */
function display() {
  println(
    "totalLoadCost = ", getValue(totalLoadCost), ", ", 
    "totalBalanceCost = ", getValue(totalBalanceCost), ", ", 
    "processMoveCost = ", getValue(processMoveCost), ", ", 
    "serviceMoveCost = ", getValue(serviceMoveCost), ", ", 
    "totalMachineMoveCost = ", getValue(totalMachineMoveCost));
}

/* Set lower bounds and initial solution. */
function param() {
  // lower bounds of surrogate objectives
  setObjectiveBound(0, 100);
  setObjectiveBound(1, 100);  
  setObjectiveBound(2, 100);
  setObjectiveBound(3, 100);      
  setObjectiveBound(4, 0);
  
  if (lsTimeLimit == nil) {
    println("Setting time limits to 150, 50, 40, 30, 30 (total: 300 sec)");
    lsTimeLimit = {150, 50, 40, 30, 30};
  }
  
  if (lsNbThreads == nil) {
    println("Setting nbThreads to 4");
    lsNbThreads = 4;
  }

  lsAnnealingLevel = 0; // disable simulated annealing
  
  // set initial values of decisions according to 
  // the initial assignment of processes to machines  
  for [p in 0..nbProcesses-1][m in 0..nbMachines-1]
    if (m == initialMachine[p]) setValue(x[p][m], true);
    else setValue(x[p][m], false);
}

/* Write solution file. */
function output() {
  solutionFile = openWrite(solutionPath);
  for [p in 0..nbProcesses-1][m in 0..nbMachines-1]
    if (getValue(x[p][m])) print(solutionFile, m + " ");
  println(solutionFile);
}


例題コンテンツ

  • google_machine_reassignment/
  • google_machine_reassignment/instances/
  • google_machine_reassignment/README.txt
  • google_machine_reassignment/google_machine_reassignment.lsp
  • google_machine_reassignment/instances/free_trial_model.txt
  • google_machine_reassignment/instances/assignment_a2_5.txt
  • google_machine_reassignment/instances/assignment_a1_5.txt
  • google_machine_reassignment/instances/assignment_a2_4.txt
  • google_machine_reassignment/instances/assignment_a1_4.txt
  • google_machine_reassignment/instances/assignment_a2_3.txt
  • google_machine_reassignment/instances/assignment_a1_3.txt
  • google_machine_reassignment/instances/assignment_a2_2.txt
  • google_machine_reassignment/instances/assignment_a1_2.txt
  • google_machine_reassignment/instances/assignment_a2_1.txt
  • google_machine_reassignment/instances/assignment_a1_1.txt
  • google_machine_reassignment/instances/model_a2_5.txt
  • google_machine_reassignment/instances/model_a1_5.txt
  • google_machine_reassignment/instances/model_a2_4.txt
  • google_machine_reassignment/instances/free_trial_assignment.txt
  • google_machine_reassignment/instances/model_a1_4.txt
  • (+ 6 other files)

このページの先頭へ