Почему модель SCIPcopy может быть невозможной, если возможна исходная модель?

Я новичок в SCIP, поэтому не уверен, ошибка ли это или я просто что-то делаю не так.

У меня есть экземпляр MIP, который отлично решает с помощью SCIP, однако, когда я пытаюсь решить копию модели, SCIP говорит, что это невозможно. Вроде бы заметнее, когда preolve выключен.

Я использую Windows со встроенным SCIP v3.2.0. В модели есть только двоичные и целочисленные переменные.

Следующий код описывает мою попытку:

SCIP* _scip, subscip;
SCIPcreate(&_scip);
SCIPincludeDefaultPlugins(_scip);
SCIPcreateProbBasic(_scip, "interval_solver"));     // create an empty problem
SCIPsetPresolving(_scip, SCIP_PARAMSETTING_OFF, true);   //disable presolving

// build model (snipped)

SCIPsolve(_scip);  // succeeds and gives feasible solution

SCIP_Bool valid = FALSE;
SCIPcreate(&subscip);
SCIPcopy(_scip, subscip, NULL, NULL, "1", TRUE, FALSE, TRUE, &valid);

SCIPsolve(subscip);  // infeasible

Что-то, что может быть связано (и кажется мне странным), заключается в том, что после решения исходной проблемы (и получения возможного решения) проверка решения сообщает о недопустимом результате. т.е.

SCIP_SOL* sol = SCIPgetBestSol(_scip);
SCIPcheckSol(_scip, sol, TRUE, TRUE, TRUE, TRUE, &valid);

дает:

solution value 1 violates bounds of <t_x71_(6,1275,6805)_(9,1275,6805)>[-0,0] by 1

Есть идеи, почему это могло происходить? Спасибо!


optimization scip
person mathgeekcoder    schedule 14.07.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Распространение в SCIP может принимать во внимание лучшее решение, известное на данный момент, и делать сокращения, которые действительны только для проблемы поиска лучшего решения, чем это. Например, если у вас есть задача минимизации с n переменными x_1,...,x_n с объективными коэффициентами c_1,...,c_n >= 0 и вы уже нашли решение с x_1 = 1, x_2 = ... = x_n = 0, то распространение глобально исправит x_1 на 0, потому что цель любого решения с x_1 = 1 будет не меньше, чем цель решения, которое вы уже нашли.

Это означает, что найденные до сих пор решения могут быть больше неосуществимы для оставшейся проблемы (которая ищет строго лучшее решение). Чтобы проверить решение, вы должны проверить его в области исходной проблемы, что вы можете сделать с помощью SCIPcheckSolOrig().

Отключение предварительного разрешения распространения может помочь, но не гарантирует, что глобальная предварительно решенная проблема не изменится. Предварительное решение в решателе LP не должно быть проблемой, но могло изменить сообщенное оптимальное решение LP (если есть несколько оптимумов) и, следовательно, вызвало изменение в процессе решения. В этом случае это могло бы избежать вашей проблемы, но, вероятно, по чистой случайности, и проблема может снова появиться в других случаях. Более того, чем больше функций вы отключите, тем больше это отрицательно скажется на вашей производительности.

Однако есть простое решение вашей проблемы: вы можете скопировать исходную неизмененную проблему с помощью SCIPcopyOrig().

person Gerald    schedule 17.07.2015

arrow_upward
1
arrow_downward

Некоторые ограничения переменных еще не решены. Чтобы решить проблему, мне нужно было добавить:

SCIPsetBoolParam(_scip, "lp/presolving", FALSE);

Это устранило большинство вещей, но следующее также помогло исправить некоторые проблемы с "проверкой решения":

SCIPsetIntParam(_scip, "propagating/maxrounds", 0);
SCIPsetIntParam(_scip, "propagating/maxroundsroot", 0);
person mathgeekcoder    schedule 17.07.2015