i am using choco to solve a Virtual machine allocation problem and this is what i am trying to do:
Suppose we have 3 arrays for our physical machine properties (PMcpu, PMram, PMbw) and 3 arrays for our virtual machines (VMcpu, VMram, VMbw). Now we define a matrix with these dimensions: PM*VM so that choco will set the values (which are either 0 or 1 meaning that a specific VM is assigned to a PM or not). Based on common sense we know that the PM resources should be greater or equal to the amount of all assigned VM resources altogether, so to do this we multiply each element in our allocation matrix with the resources accordingly, for example suppose:
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
rows represent the PMs and columns represent the VMs so here:
VM2 -> PM1
VM1 -> PM2
VM3 -> PM3
so i wrote this code:
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();
}
}
I tried to ensure that all VMs are allocated by checking each column of the matrix to be filled in the line model.arithm(sum_of_col.get(i), "=", 1).post();. If i comment the constraints and the objective the matrix will be randomly allocated but when applying the constraints, choco will not solve anything (there is no output because while(model.getSolver().solve() is never true, so choco doesn't seem to solve it). I don't know where am i doing wrong. Any help is appreciated :)
Thanks in advance
EDIT: i realized that the problem is that choco only checks those constraints the first time so it checks it when everything is 0 that's why it won't continue, but after adding the constraints in the solve() loop i still get the same result, maybe i should apply these constraints in another way that choco understands them, i'm really frustrated now :(
My problem was a fundamental understanding of CSP problem solving, basically all the variables are unknown at first but they are going to be set by values when the choco solver tries to solve the problem. So it isn't possible to retrieve values and set constraints like that (not even in the while(solve()){}. Basically we should apply the whole constraints on those unknown variables before choco solves it. So i changed the whole model and got help from choco developers (check their gitter chat for help). So down below you'll see what the codes looks like:
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();
}