当原始模型可行时，为什么 SCIPcopy 模型不可行？

Question

我是 SCIP 的新手，所以我不确定这是一个错误还是我只是做错了什么。

我有一个使用 SCIP 完美求解的 MIP 实例，但是当我尝试求解模型的副本时，SCIP 说它不可行。 presolve 关闭时似乎更明显。

我正在使用 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

知道为什么会发生这种情况吗？谢谢！

Answer 1

一些变量边界仍在预求解中。要解决我需要添加的问题：

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

这解决了大部分问题，但以下内容也有助于解决一些 'check solution' 问题：

SCIPsetIntParam(_scip, "propagating/maxrounds", 0);
SCIPsetIntParam(_scip, "propagating/maxroundsroot", 0);

Answer 2

SCIP 中的传播可能会考虑目前已知的最佳解决方案并进行缩减，这仅对找到比这更好的解决方案的问题有效。例如，如果您有 n 个变量 x_1,...,x_n 和 objective 系数 c_1,...,c_n >= 0 的最小化问题，并且已经找到了 x_1 = 1, x_2 = ... = x_n = 0 的解决方案，那么传播将全局修复 x_1 到 0，因为具有 x_1 = 1 的任何解决方案的 objective 将至少与您已经找到的解决方案的 objective 一样大。

这意味着到目前为止找到的解决方案对于剩余的问题（寻找严格更好的解决方案）可能不再可行。为了检查解决方案，您应该在原始问题 space 中检查它，您可以使用 SCIPcheckSolOrig() 进行检查。

禁用预求解传播可能会有所帮助，但不能保证全局预求解问题不会改变。在 LP 求解器中预求解应该不是问题，但可能已经改变了报告的最优 LP 解（如果有多个最优解），因此导致求解过程发生变化。在这种情况下，这可能避免了您的问题，但可能纯粹是运气好，该问题可能仍会在其他情况下再次出现。此外，禁用的功能越多，对性能的负面影响就越大。

但是，您的问题有一个简单的解决方案：您可以使用 SCIPcopyOrig().

复制原始未更改的问题

当原始模型可行时，为什么 SCIPcopy 模型不可行？

Why could a SCIPcopy model be infeasible a when original model is feasible?

optimization

scip