Добавление ограничений в C API GUROBI занимает слишком много времени - PullRequest
Новая
       14

Добавление ограничений в C API GUROBI занимает слишком много времени

1 голос
/ 24 января 2020

У меня есть модель, которая имеет 113000 ограничений и 127940 переменных (28400 непрерывных и 99540 целых). Проблема в том, что для записи ограничений требуется слишком много времени (около 108 секунд). Решение занимает 32 секунды. Я намерен решить более серьезные проблемы, чем это, и необходимое время очень быстро растет. Я думаю, что это не должно занять много времени. Есть ли способ быстрее добавить ограничения в C API? Я использую GRBaddconstr, который добавляет ограничения по одному. В GUROBI есть еще одна функция, которая делает это через ванны, а именно GRBaddconstrs, но в документации говорится, что разница в производительности не очень велика. Кроме того, использовать GRBaddconstrs довольно сложно.

Я использую C API для GUROBI 8.1.0. Например, для записи одного набора ограничений требуется более 50 секунд. Когда я удаляю только строку, где я добавляю ограничения с помощью GRBaddconstr, для выполнения одного и того же l oop (99400 итераций) требуется меньше секунды. Моя модель слишком велика для прикрепления и сложна, но я добавляю упомянутую выше l oop на случай, если это может помочь. 

//LOGICAL
                            time ( &rawtime );
                            timeinfo = localtime ( &rawtime );
                            printf("LOGICAL %d:%d:%d\n", timeinfo->tm_hour,timeinfo->tm_min,timeinfo->tm_sec);

                            int c=0;
                            int tmp,tmp2,tmp3;
                            int tmp_sabit;
                            int week_start=wk*T;
                            int week_end=(wk+1)*T;
                            for(int i=0;i<orders_length;i++){
                                for(int t = week_start; t < week_end; t++){
                                    tmp_sabit=i*(T*no_scenarios)+(t-week_start)*no_scenarios+B_threshold;
                                    tmp2=(t-week_start)*no_of_terminals+booking[orders[i]].o;
                                    tmp3=(t-week_start+1)*no_of_terminals+booking[orders[i]].d;
                                    for(int w=0;w<no_scenarios;w++){
                                        tmp=tmp_sabit+w;
                                        val[tmp]=1;
                                        if(booking[orders[i]].o>0){

                                            val[tmp2]=-1;
                                            }
                                        else if(t+1<week_end)
                                            {                                   
                                            val[tmp3]=-1;
                                            }
                                        error = GRBaddconstr(model, no_variable, ind, val, GRB_LESS_EQUAL, 0, "LOGICAL");
                                        c++;
                                        //Initialise val to 0
                                        val[tmp]=0;
                                        if(booking[orders[i]].o>0){

                                            val[tmp2]=0;
                                            }
                                        else if(t+1<week_end)
                                            {
                                            val[tmp3]=0;
                                            }
                                        //for(int j = 0; j < no_variable; j++){val[j] = 0;}
                                        }
                                    }
                                }
                            error = GRBupdatemodel(model);

1 Ответ

3 голосов
/ 25 января 2020

Я считаю, что проблема в том, что вы даете Gurobi плотные версии своих ограничений, а не разреженные представления. Рассмотрим следующее ограничение: 

error = GRBaddconstr(model, no_variable, ind, val, GRB_LESS_EQUAL, 0, "LOGICAL");

Здесь no_variable равно 127940. Таким образом, при каждом вызове GRBaddconstr вы передаете Gurobi значения коэффициента для всех 127940 переменных , несмотря на тот факт, что не более двух переменных в этом ограничении будут иметь ненулевые значения коэффициента. Это может занять много времени, если вы делаете это для каждого ограничения. Чтобы быть более эффективным, вы должны передавать информацию индекса / значения Gurobi только для переменных с ненулевыми коэффициентами. Обратитесь к документации для GRBaddconstr для получения более подробной информации об этом.

Это можно исправить с помощью нескольких небольших изменений кода. Вне ваших for циклов определите два массива длины два, в которых будут храниться индексы и значения переменных с ненулевыми коэффициентами в конкретном «логическом» ограничении: 

lInd = (int *) malloc(sizeof(int) * 2);
lVal = (double *) malloc(sizeof(double) * 2);

Затем в самом внутреннем for l oop, установите соответствующие индексы и значения перед добавлением каждого ограничения: 

lInd[0] = tmp_sabit + w;
lVal[0] = 1;

if (booking[orders[i]].o > 0) {
    lInd[1] = tmp2;
    lVal[1] = -1;
}
else if (t+1 < week_end) {                                   
    lInd[1] = tmp3;
    lVal[1] = -1;
}
else {
    lVal[1] = 0;
}

error = GRBaddconstr(model, 2, lInd, lVal, GRB_LESS_EQUAL, 0, NULL);

Наконец, обратите внимание, что ограничения должны иметь уникальные имена. Если ограничения имеют повторяющиеся имена, вы можете столкнуться с неожиданным поведением при попытке получить доступ к ограничениям по имени, прочитать / записать файл модели и т. Д. c.

...