Gurobi долгое время строил модель для LP

Question

Я решал некоторые пластинки с gurobi, и я заметил, что для большинства случаев, с которыми я сталкиваюсь, построение модели занимает больше времени, чем фактически ее решение. Возможно, это стандартно, но для меня это кажется странным.

Один конкретный экземпляр занял 1,75 секунд, чтобы решить, но следующий участок кода для построения модели взяли 13,6 секунды:

for (int i = 0; i < numSeq2; ++i) { 
    expr = new GRBLinExpr(); 
    //expr.clear(); 
    for (int j = 0; j < numSeq1; ++j) 
     expr.addTerm(-1 * A[j][i], x[j]); 
    for (int j = 0; j < numIS2; ++j) 
     expr.addTerm(-1 * F[j][i], q[j]); 
    duals[i] = model.addConstr(expr, GRB.LESS_EQUAL, 0, ""); 
} 

В примере, описанном выше, numSeq1 = 7475, numSeq2 = 7475, numIS2 = 2517, а окончательный LP имел 9992 строки и 9992 столбца. Я знаю, что это довольно большой, но, похоже, странно, что для создания модели требуется почти 10 раз больше времени, чем для ее решения.

Я попробовал expr.clear() вместо создания нового GRBLinExpr для каждого ограничения (закомментировал), и это не помогло.

Есть ли какой-нибудь способ сделать модельную конструкцию гуроби быстрее? Будет ли cplex лучше, чем gurobi в этом отношении, если узкое место строит модель?

Спасибо!

Answer 1

Поскольку вы спрашиваете об альтернативах, я считаю, что вам лучше использовать язык алгебраического моделирования, такой как AMPL, AIMMS или альтернативы с открытым исходным кодом, такие как GLPK и AML. Эти декларативные языки позволяют кратко и изящно сформулировать вашу проблему. Эти языки генерируют MPS или NL, которые затем могут обрабатываться CPLEX или альтернативными свободными решателями. Как вы можете видеть, язык моделирования - это одно, а решатель - другой.

Answer 2

Во-первых, в блоках вашего образца кода (теперь исправлено) была большая опечатка. Это заставляет меня задаться вопросом, должна ли ваша модель иметь numSeq2 строк (7495).

Если каждый элемент в ваших матрицах A и F отличен от нуля, структура вашего кода в порядке. Однако это очень редко. в большинстве случаев подавляющее большинство матричных коэффициентов равно нулю. Если это так, вы должны вызвать GRBLinExpr.addTerm() только для ненулевых элементов в строках. Это верно независимо от того, используете ли вы Gurobi или любой другой решатель.

(. Обратите внимание, что вы можете получить быстрый ответ на Gurobi специфических вопросов на собственном дискуссионном форуме Gurobi в)

Отказ от ответственности: я работаю для Gurobi оптимизации и ранее работал ILOG, который обеспечил CPLEX.