- LocalSolverホーム
- LocalSolver製品概要
- LocalSolver例題集
- 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)
