choco求解器中的资源分配
Resource allocation in choco solver
我正在使用 choco
来解决虚拟机分配问题,这就是我正在尝试做的事情:
假设我们有 3 个数组用于物理机属性 (PMcpu
、PMram
、PMbw
) 和 3 个数组用于虚拟机 (VMcpu
、VMram
, VMbw
).现在我们定义一个具有这些维度的矩阵:PM*VM
以便 choco 将设置值(0 或 1 表示特定 VM 是否分配给 PM)。根据常识,我们知道 PM 资源应该大于或等于所有分配的 VM 资源的总和,因此我们将分配矩阵中的每个元素与相应的资源相乘,例如假设:
PMcpu = {8000, 7000, 3000};
PMram = {7000, 4000, 5000};
PMbw = {2000, 500, 7000};
VMcpu = {2000, 3000, 1000};
VMram = {1000, 2000, 3000};
VMbw = {100, 2000, 500};
Allocation_matrix:
0 1 0
1 0 0
0 0 1
行代表 PM,列代表 VM,所以这里:
VM2 -> PM1
VM1 -> PM2
VM3 -> PM3
所以我写了这段代码:
Model model = new Model("Resource Allocation Problem");
int[] VMcpu = new int[number_of_vms];
int[] VMram = new int[number_of_vms];
int[] VMbw = new int[number_of_vms];
// some initialization here
int[] PMcpu = new int[number_of_pms];
int[] PMram = new int[number_of_pms];
int[] PMbw = new int[number_of_pms];
// some initialization here
IntVar[][] alloc_matrix = model.intVarMatrix("alloc_matrix", number_of_pms, number_of_vms, new int[] {0,1});
// ensuring all columns have only one 1 in them
ArrayList<IntVar> sum_of_col = new ArrayList<>();
for(int j=0; j<number_of_vms; j++) {
int count = 0;
for(int i=0; i<number_of_pms; i++) {
count += alloc_matrix[i][j].getValue();
}
IntVar tempInt = model.intVar(count);
sum_of_col.add(tempInt);
}
for(int i=0; i<sum_of_col.size(); i++) {
model.arithm(sum_of_col.get(i), "=", 1).post();
}
// ensuring that PMs can host that much VM (based on their resources)
for (int i=0; i<number_of_pms; i++) {
ArrayList<IntVar> pm_total_cpu = new ArrayList<>();
ArrayList<IntVar> pm_total_ram = new ArrayList<>();
ArrayList<IntVar> pm_total_bw = new ArrayList<>();
for (int j=0; j<number_of_vms; j++) {
IntVar temp_cpu = model.intVar(alloc_matrix[i][j].getValue() * VMcpu[j]);
IntVar temp_ram = model.intVar(alloc_matrix[i][j].getValue() * VMram[j]);
IntVar temp_bw = model.intVar(alloc_matrix[i][j].getValue() * VMbw[j]);
pm_total_cpu.add(temp_cpu);
pm_total_ram.add(temp_ram);
pm_total_bw.add(temp_bw);
}
model.sum(ArrayUtils.toArray(pm_total_cpu), "<", PMcpu[i]).post();
model.sum(ArrayUtils.toArray(pm_total_ram), "<", PMram[i]).post();
model.sum(ArrayUtils.toArray(pm_total_bw), "<", PMbw[i]).post();
}
// getting the number of active PMs (those that have at least one 1 in their row)
ArrayList<IntVar> pm_hostings = new ArrayList<>();
for (int i=0; i<number_of_pms; i++) {
ArrayList<IntVar> row = new ArrayList<>();
for (int j=0; j<number_of_vms; j++) {
IntVar temp_int_var = model.intVar(alloc_matrix[i][j].getValue());
row.add(temp_int_var);
}
int has_one = 0;
for(int iterator=0; iterator<row.size(); iterator++) {
if (row.get(iterator).getValue() == 1) {
has_one = 1;
break;
}
}
IntVar temp = model.intVar(has_one);
pm_hostings.add(temp);
}
// sum will be the number of active PMs
int sum = 0;
for (int i=0; i<pm_hostings.size(); i++) {
sum += pm_hostings.get(i).getValue();
}
// setting objective to minimize that number of active PMs
IntVar answer = model.intVar(sum);
model.setObjective(Model.MINIMIZE, answer);
while(model.getSolver().solve()) {
System.out.println("answer: " + answer.getValue());
for(int i=0;i<sum_of_col.size();i++) {
System.out.println("=== " + sum_of_col.get(i).getValue());
}
for(int i=0;i<number_of_pms;i++) {
for(int j=0;j<number_of_vms;j++) {
System.out.print(alloc_matrix[i][j].getValue() + " ");
}
System.out.println();
}
}
我试图通过检查要在行 model.arithm(sum_of_col.get(i), "=", 1).post();
中填充的矩阵的每一列来确保分配了所有 VM。如果我评论约束和 objective 矩阵将被随机分配但是当应用约束时,choco 将不会解决任何问题(没有输出因为 while(model.getSolver().solve()
永远不会是真的,所以 choco 似乎不是来解决)。我不知道我哪里做错了。感谢您的帮助:)
提前致谢
编辑:我意识到问题是 choco 只在第一次检查这些约束,所以当一切都为 0 时它会检查它,这就是它不会继续的原因,但是在 solve() 循环中添加约束后我仍然得到相同的结果,也许我应该以 choco 理解它们的另一种方式应用这些约束,我现在真的很沮丧:(
我的问题是对 CSP 问题求解的基本理解,基本上所有的变量一开始都是未知的,但是当 choco 求解器尝试求解问题时,它们将由值设置。所以不可能像那样检索值和设置约束(甚至在 while(solve()){}
中也不行)。基本上我们应该在 choco 解决它之前对那些未知变量应用整个约束。所以我改变了整个模型并得到了帮助来自 choco 开发人员(查看他们的 gitter chat 以获得帮助)。所以在下面你会看到代码的样子:
Model model = new Model("Resource Allocation Problem");
// here we are using number_of_sth+1 because we need to use a scalar function of choco
// that will calculate sum(arr[i] * arr2[i]) and we need to specify the lack of PM
// assignment by the 0 in them so that we can add a constraint later to prevent such
// a happening (not assigning a VM to a PM)
int[] VMcpu = new int[number_of_vms+1];
int[] VMram = new int[number_of_vms+1];
VMcpu[0] = 0;
VMram[0] = 0;
for (int i=1; i<number_of_vms+1; i++) {
VMcpu[i] = vms.get(i-1).get_cpu();
VMram[i] = vms.get(i-1).get_ram();
}
System.out.println();
int[] PMcpu = new int[number_of_pms+1];
int[] PMram = new int[number_of_pms+1];
PMcpu[0] = 0;
PMram[0] = 0;
for (int i=1; i<number_of_pms+1; i++) {
PMcpu[i] = pms.get(i-1).get_cpu();
PMram[i] = pms.get(i-1).get_ram();
}
IntVar[] VMS = model.intVarArray("VMS", number_of_vms, 0, number_of_pms);
// capacity constraints
BoolVar[][] VMi_hosted_by_PMj = model.boolVarMatrix(number_of_pms+1, number_of_vms+1);
for (int i=0; i<number_of_vms; i++) {
model.arithm(VMS[i], "!=", 0).post();
}
for (int pm_i=1; pm_i<number_of_pms+1; pm_i++) {
for (int vm_i=1; vm_i<number_of_vms+1; vm_i++) {
// below is the functionality for 2 lines below
// reifyXeqC(X, C, A) => (X == C) ? A=1 : A=0;
model.reifyXeqC(VMS[vm_i-1], pm_i, VMi_hosted_by_PMj[pm_i][vm_i]);
}
}
// here is the constraint to make sure the total VMs assigned to a PM
// demand less that the PM's resources
for (int i=1; i<number_of_pms+1; i++) {
model.scalar(VMi_hosted_by_PMj[i], VMcpu, "<=", PMcpu[i]).post();
model.scalar(VMi_hosted_by_PMj[i], VMram, "<=", PMram[i]).post();
}
// a constraint to have a number of PMs
IntVar no_of_PM = model.intVar("#PM", 0, number_of_pms+1);
// here we link the no_of_PM to the count of unique values in VMS (basically we
// get a number of used PMs)
model.nValues(VMS, no_of_PM).post();
model.setObjective(false, no_of_PM); //false => model.MINIMIZE
// here we define the array that will hold the final allocation vector (basically
// we get a copy of VMS' values so that we have it later)
int[] vm_alloc = new int[number_of_vms];
int no_of_allocated_pms = number_of_pms;
while(model.getSolver().solve()) {
for (int i = 0; i < number_of_vms; i++) {
vm_alloc[i] = VMS[i].getValue();
}
System.out.println("Number of used PMs: " + (no_of_PM.getValue()));
no_of_allocated_pms = no_of_PM.getValue();
}
我正在使用 choco
来解决虚拟机分配问题,这就是我正在尝试做的事情:
假设我们有 3 个数组用于物理机属性 (PMcpu
、PMram
、PMbw
) 和 3 个数组用于虚拟机 (VMcpu
、VMram
, VMbw
).现在我们定义一个具有这些维度的矩阵:PM*VM
以便 choco 将设置值(0 或 1 表示特定 VM 是否分配给 PM)。根据常识,我们知道 PM 资源应该大于或等于所有分配的 VM 资源的总和,因此我们将分配矩阵中的每个元素与相应的资源相乘,例如假设:
PMcpu = {8000, 7000, 3000};
PMram = {7000, 4000, 5000};
PMbw = {2000, 500, 7000};
VMcpu = {2000, 3000, 1000};
VMram = {1000, 2000, 3000};
VMbw = {100, 2000, 500};
Allocation_matrix:
0 1 0
1 0 0
0 0 1
行代表 PM,列代表 VM,所以这里:
VM2 -> PM1
VM1 -> PM2
VM3 -> PM3
所以我写了这段代码:
Model model = new Model("Resource Allocation Problem");
int[] VMcpu = new int[number_of_vms];
int[] VMram = new int[number_of_vms];
int[] VMbw = new int[number_of_vms];
// some initialization here
int[] PMcpu = new int[number_of_pms];
int[] PMram = new int[number_of_pms];
int[] PMbw = new int[number_of_pms];
// some initialization here
IntVar[][] alloc_matrix = model.intVarMatrix("alloc_matrix", number_of_pms, number_of_vms, new int[] {0,1});
// ensuring all columns have only one 1 in them
ArrayList<IntVar> sum_of_col = new ArrayList<>();
for(int j=0; j<number_of_vms; j++) {
int count = 0;
for(int i=0; i<number_of_pms; i++) {
count += alloc_matrix[i][j].getValue();
}
IntVar tempInt = model.intVar(count);
sum_of_col.add(tempInt);
}
for(int i=0; i<sum_of_col.size(); i++) {
model.arithm(sum_of_col.get(i), "=", 1).post();
}
// ensuring that PMs can host that much VM (based on their resources)
for (int i=0; i<number_of_pms; i++) {
ArrayList<IntVar> pm_total_cpu = new ArrayList<>();
ArrayList<IntVar> pm_total_ram = new ArrayList<>();
ArrayList<IntVar> pm_total_bw = new ArrayList<>();
for (int j=0; j<number_of_vms; j++) {
IntVar temp_cpu = model.intVar(alloc_matrix[i][j].getValue() * VMcpu[j]);
IntVar temp_ram = model.intVar(alloc_matrix[i][j].getValue() * VMram[j]);
IntVar temp_bw = model.intVar(alloc_matrix[i][j].getValue() * VMbw[j]);
pm_total_cpu.add(temp_cpu);
pm_total_ram.add(temp_ram);
pm_total_bw.add(temp_bw);
}
model.sum(ArrayUtils.toArray(pm_total_cpu), "<", PMcpu[i]).post();
model.sum(ArrayUtils.toArray(pm_total_ram), "<", PMram[i]).post();
model.sum(ArrayUtils.toArray(pm_total_bw), "<", PMbw[i]).post();
}
// getting the number of active PMs (those that have at least one 1 in their row)
ArrayList<IntVar> pm_hostings = new ArrayList<>();
for (int i=0; i<number_of_pms; i++) {
ArrayList<IntVar> row = new ArrayList<>();
for (int j=0; j<number_of_vms; j++) {
IntVar temp_int_var = model.intVar(alloc_matrix[i][j].getValue());
row.add(temp_int_var);
}
int has_one = 0;
for(int iterator=0; iterator<row.size(); iterator++) {
if (row.get(iterator).getValue() == 1) {
has_one = 1;
break;
}
}
IntVar temp = model.intVar(has_one);
pm_hostings.add(temp);
}
// sum will be the number of active PMs
int sum = 0;
for (int i=0; i<pm_hostings.size(); i++) {
sum += pm_hostings.get(i).getValue();
}
// setting objective to minimize that number of active PMs
IntVar answer = model.intVar(sum);
model.setObjective(Model.MINIMIZE, answer);
while(model.getSolver().solve()) {
System.out.println("answer: " + answer.getValue());
for(int i=0;i<sum_of_col.size();i++) {
System.out.println("=== " + sum_of_col.get(i).getValue());
}
for(int i=0;i<number_of_pms;i++) {
for(int j=0;j<number_of_vms;j++) {
System.out.print(alloc_matrix[i][j].getValue() + " ");
}
System.out.println();
}
}
我试图通过检查要在行 model.arithm(sum_of_col.get(i), "=", 1).post();
中填充的矩阵的每一列来确保分配了所有 VM。如果我评论约束和 objective 矩阵将被随机分配但是当应用约束时,choco 将不会解决任何问题(没有输出因为 while(model.getSolver().solve()
永远不会是真的,所以 choco 似乎不是来解决)。我不知道我哪里做错了。感谢您的帮助:)
提前致谢
编辑:我意识到问题是 choco 只在第一次检查这些约束,所以当一切都为 0 时它会检查它,这就是它不会继续的原因,但是在 solve() 循环中添加约束后我仍然得到相同的结果,也许我应该以 choco 理解它们的另一种方式应用这些约束,我现在真的很沮丧:(
我的问题是对 CSP 问题求解的基本理解,基本上所有的变量一开始都是未知的,但是当 choco 求解器尝试求解问题时,它们将由值设置。所以不可能像那样检索值和设置约束(甚至在 while(solve()){}
中也不行)。基本上我们应该在 choco 解决它之前对那些未知变量应用整个约束。所以我改变了整个模型并得到了帮助来自 choco 开发人员(查看他们的 gitter chat 以获得帮助)。所以在下面你会看到代码的样子:
Model model = new Model("Resource Allocation Problem");
// here we are using number_of_sth+1 because we need to use a scalar function of choco
// that will calculate sum(arr[i] * arr2[i]) and we need to specify the lack of PM
// assignment by the 0 in them so that we can add a constraint later to prevent such
// a happening (not assigning a VM to a PM)
int[] VMcpu = new int[number_of_vms+1];
int[] VMram = new int[number_of_vms+1];
VMcpu[0] = 0;
VMram[0] = 0;
for (int i=1; i<number_of_vms+1; i++) {
VMcpu[i] = vms.get(i-1).get_cpu();
VMram[i] = vms.get(i-1).get_ram();
}
System.out.println();
int[] PMcpu = new int[number_of_pms+1];
int[] PMram = new int[number_of_pms+1];
PMcpu[0] = 0;
PMram[0] = 0;
for (int i=1; i<number_of_pms+1; i++) {
PMcpu[i] = pms.get(i-1).get_cpu();
PMram[i] = pms.get(i-1).get_ram();
}
IntVar[] VMS = model.intVarArray("VMS", number_of_vms, 0, number_of_pms);
// capacity constraints
BoolVar[][] VMi_hosted_by_PMj = model.boolVarMatrix(number_of_pms+1, number_of_vms+1);
for (int i=0; i<number_of_vms; i++) {
model.arithm(VMS[i], "!=", 0).post();
}
for (int pm_i=1; pm_i<number_of_pms+1; pm_i++) {
for (int vm_i=1; vm_i<number_of_vms+1; vm_i++) {
// below is the functionality for 2 lines below
// reifyXeqC(X, C, A) => (X == C) ? A=1 : A=0;
model.reifyXeqC(VMS[vm_i-1], pm_i, VMi_hosted_by_PMj[pm_i][vm_i]);
}
}
// here is the constraint to make sure the total VMs assigned to a PM
// demand less that the PM's resources
for (int i=1; i<number_of_pms+1; i++) {
model.scalar(VMi_hosted_by_PMj[i], VMcpu, "<=", PMcpu[i]).post();
model.scalar(VMi_hosted_by_PMj[i], VMram, "<=", PMram[i]).post();
}
// a constraint to have a number of PMs
IntVar no_of_PM = model.intVar("#PM", 0, number_of_pms+1);
// here we link the no_of_PM to the count of unique values in VMS (basically we
// get a number of used PMs)
model.nValues(VMS, no_of_PM).post();
model.setObjective(false, no_of_PM); //false => model.MINIMIZE
// here we define the array that will hold the final allocation vector (basically
// we get a copy of VMS' values so that we have it later)
int[] vm_alloc = new int[number_of_vms];
int no_of_allocated_pms = number_of_pms;
while(model.getSolver().solve()) {
for (int i = 0; i < number_of_vms; i++) {
vm_alloc[i] = VMS[i].getValue();
}
System.out.println("Number of used PMs: " + (no_of_PM.getValue()));
no_of_allocated_pms = no_of_PM.getValue();
}