Почему модель SCIPcopy невозможна, когда возможна оригинальная модель?
Я новичок в SCIP, поэтому я не уверен, что это ошибка или я просто делаю что-то не так.
У меня есть экземпляр MIP, который отлично решается с использованием SCIP, однако, когда я пытаюсь найти копию модели SCIP, он говорит, что это невозможно. Это кажется более заметным, когда пресольв выключен.
Я использую 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
Есть идеи, почему это может происходить? Спасибо!
2 ответа
Распространение в 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 (если имеется несколько optima) и, следовательно, привела к изменению в процессе решения. Это могло бы избежать вашей проблемы в этом случае, но, возможно, по чистой случайности, и проблема все еще может появиться снова в других случаях. Более того, чем больше функций вы отключите, тем больше это отрицательно скажется на вашей производительности.
Тем не менее, есть простое решение вашей проблемы: вы можете скопировать исходную проблему без изменений, используя SCIPcopyOrig(),
Некоторые переменные границы все еще находились в стадии разработки. Чтобы исправить проблему, мне нужно было добавить:
SCIPsetBoolParam(_scip, "lp/presolving", FALSE);
Это исправило большинство вещей, но следующее также помогло решить некоторые проблемы с "проверкой решения":
SCIPsetIntParam(_scip, "propagating/maxrounds", 0);
SCIPsetIntParam(_scip, "propagating/maxroundsroot", 0);