1

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

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

我正在使用带有预构建 SCIP v3.2.0 的 windows。该模型只有二进制和整数变量。

以下代码概述了我的尝试：

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

可能相关（对我来说似乎很奇怪）的事情是，在解决了原始问题（并获得了可行的解决方案）之后，检查解决方案会报告不可行的结果。IE

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

任何想法为什么会发生这种情况？谢谢！

4

2 回答 2

1

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

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

这解决了大多数问题，但以下也有助于解决一些“检查解决方案”问题：

SCIPsetIntParam(_scip, "propagating/maxrounds", 0);
SCIPsetIntParam(_scip, "propagating/maxroundsroot", 0);
于 2015-07-17T05:14:41.197 回答
1

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()。

于 2015-07-17T21:15:06.907 回答