Распределение ресурсов в chocosolver

я использую choco для решения проблемы выделения виртуальной машины, и это то, что я пытаюсь сделать:

Предположим, у нас есть 3 массива для свойств нашей физической машины (PMcpu, PMram, PMbw) и 3 массива для наших виртуальных машин (VMcpu, VMram, VMbw). Теперь мы определяем матрицу со следующими размерами: PM*VM, так что choco будет устанавливать значения (которые равны 0 или 1, что означает, что конкретная виртуальная машина назначена 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};

Распределение_матрица:

0 1 0
1 0 0
0 0 1

строки представляют PM, а столбцы представляют виртуальные машины, поэтому здесь:

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();. Если я прокомментирую ограничения и цель, матрица будет распределена случайным образом, но при применении ограничений choco ничего не решит (нет вывода, потому что while(model.getSolver().solve() никогда не бывает истинным, поэтому choco, похоже, не решает эту проблему). Я не знаю, где я делаю неправильно. Любая помощь приветствуется :)

заранее спасибо

РЕДАКТИРОВАТЬ: я понял, что проблема в том, что choco проверяет эти ограничения только в первый раз, поэтому он проверяет их, когда все равно 0, поэтому он не будет продолжаться, но после добавления ограничений в цикле решения () я все еще получаю тот же результат , может быть, мне следует применить эти ограничения по-другому, чтобы choco их понимал, я сейчас очень расстроен :(


person Mazhar Zandsalimi    schedule 07.09.2018    source источник


Ответы (1)


Моя проблема заключалась в фундаментальном понимании решения проблем CSP, в основном все переменные сначала неизвестны, но они будут установлены значениями, когда решатель choco попытается решить проблему. Таким образом, невозможно получить значения и установить такие ограничения (даже в while(solve()){}. По сути, мы должны применить все ограничения к этим неизвестным переменным до того, как choco решит их. Поэтому я изменил всю модель и получил помощь от разработчиков choco ( проверьте их чат Gitter для помощи). Итак, ниже вы увидите, как выглядят коды:

    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();

    }
person Mazhar Zandsalimi    schedule 13.09.2018