使用 SCIP 获得 MIP 的 LP 松弛的最佳方法

Question

我有一个 C++ 应用程序，可以无差别地使用 CPLEX 或 COIN，现在我想添加 SCIP 作为一个选择。作为功能的一部分，需要运行 MIP 问题的 LP 松弛。在 CPLEX 或 COIN 中很简单，我只是创建问题，然后使用以下方法解决 LP：

CPLEX: int const rval = CPXXlpopt(m_env, m_lp);
硬币: m_modelIP.solver()->getModelPtr().initialSolve(m_lpOptions);

并且该 LP 的解决方案与常规 MIP 的解决方案在同一位置，没有 “特殊” 也没有 “单独” 我需要查看的解决方案对象，只是常规的。

但是，我无法使用 SCIP 计算出等效项。到目前为止，我已经看到了实现这一目标的两种可能的解决方案：

方法一：设置所有变量为连续变量，修改部分参数，只求解根节点。主要基于 Getting LP relaxation before SCIPsolve :

    int nVars = SCIPgetNVars(m_scip);
    std::vector<SCIP_VARTYPE> varTypes(nVars, SCIP_VARTYPE_CONTINUOUS);
    SCIP_VAR **pVars = SCIPgetVars(m_scip);
    
    /* Move all binary and integral variables to continuous */
    for (size_t i = 0; i < static_cast<size_t>(nVars); i++)
    {
        SCIP_VARTYPE const varType = SCIPvarGetType(pVars[i]);
        if (varType == SCIP_VARTYPE_CONTINUOUS)
            continue;

        varTypes[i] = varType;
    
        SCIP_Bool infeasible;
        if (SCIPchgVarType(m_scip, pVars[i], SCIP_VARTYPE_CONTINUOUS, &infeasible) != SCIP_OKAY)
            throw std::runtime_error("Error changing integrality type to SCIP variable " + std::to_string(i) + " to continuos to solve LP relaxation");
    }

    /* Store parameters current value */
    SCIP_Longint oldNodes;
    if (SCIPgetLongintParam(m_scip, "limits/nodes", &oldNodes) != SCIP_OKAY)
        throw std::runtime_error("Couldn't get limits/nodes parameter in SCIP");

    int oldMaxRounds;
    if (SCIPgetIntParam(m_scip, "presolving/maxrounds", &oldMaxRounds) != SCIP_OKAY)
        throw std::runtime_error("Couldn't get presolving/maxrounds parameter in SCIP");
        
    /* Change parameters to create the "LP-like" scenario */
    if (SCIPsetLongintParam(m_scip, "limits/nodes", 1) != SCIP_OKAY)
        throw std::runtime_error("Couldn't set limits/nodes parameter in SCIP");

    if (SCIPsetIntParam(m_scip, "presolving/maxrounds", 0) != SCIP_OKAY)
        throw std::runtime_error("Couldn't set presolving/maxrounds parameter in SCIP");

    /* Solve the supposedly now LP problem */
    if (SCIPsolve(m_scip) != SCIP_OKAY)
        throw std::runtime_error("Couldn't solve LP problem in SCIP");

    /* Restore the original state of the parameters */
    if (SCIPsetLongintParam(m_scip, "limits/nodes", oldNodes) != SCIP_OKAY)
        throw std::runtime_error("Couldn't restore limits/nodes parameter in SCIP");

    if (SCIPsetIntParam(m_scip, "presolving/maxrounds", oldMaxRounds) != SCIP_OKAY)
        throw std::runtime_error("Couldn't restore presolving/maxrounds parameter in SCIP");

    /* Restore the original state of the variables */
    for (size_t i = 0; i < static_cast<size_t>(nVars); i++)
    {
        SCIP_VARTYPE const varType = varTypes[i];
        if (varType == SCIP_VARTYPE_CONTINUOUS)
            continue;

        SCIP_Bool infeasible;
        if (SCIPchgVarType(m_scip, pVars[i], varType, &infeasible) != SCIP_OKAY)
            throw std::runtime_error("Error restoring integrality type to SCIP variable " + std::to_string(i) + " from continuos after solving LP relaxation");
    }

方法二：使用SCIP的LP接口

    /* Presolve the original MIP problem. Without this step, the following SCIPgetLPI() call throws a SIGSEGV */
    if (SCIPpresolve(m_scip) != SCIP_OKAY)
        throw std::runtime_error("Couldn't presolve SCIP");

    /* Access the LP interface of SCIP */
    SCIP_LPI *pLpi = nullptr;
    if (SCIPgetLPI(m_scip, &pLpi) != SCIP_OKAY)
        throw std::runtime_error("Couldn't obtain access to LP interface of SCIP");

    /* And solve it */
    if (SCIPlpiSolvePrimal(pLpi) != SCIP_OKAY)
        throw std::runtime_error("Couldn't solve LP interface of SCIP");

虽然方法 1 似乎可行，但我有（未经证实的）感觉方法 2 更正确。但是，我不确定用于解决问题的方法 (SCIPlpiSolvePrimal()) 是否确实是正确的，或者该方法提供的解决方案是否位于我可以简单地使用 SCIPgetBestSol()（我的库没有单独的方法来获取 IP 或 LP 解决方案，因为 CPLEX 和 COIN 都不需要它）。

所以我的主要问题是：我的方法 #1 正确吗？或者它也是 slow/not 最合适的，而不是 #2 是应该使用的那个吗？如果是这样，SCIPlpiSolvePrimal() 提供的解决方案是否可以从常规 MIP 界面访问？或者，如果没有，是否有办法将其移入其中？

或者甚至还有第三种方法来解决这个问题？我读过 here，也许使用 SCIP*Dive() 是更好的方法，但我还没有找到任何相关样本。

非常感谢您的帮助。

Answer 1

如果您可以在 SCIP 插件中执行代码，那将是最 efficient/elegant 的方式。（例如，您可以添加一个事件处理程序，该处理程序在第一个 LP 求解之后执行，并且只获取 LP 解）。这也是您可以使用潜水模式更改问题的某些方面的地方，只需解决（更改的）LP，然后恢复解决原始问题。你不能不使用插件，因为你需要在解决阶段才能执行 diving mdoe。您提到的方法 2 也有同样的问题，只有在您已经处于求解模式时，LPI 才会有正确的信息。当然你可以创建一个新的 LPI 结构并基本上复制整个问题，但如果你正在解决大问题，那可能效率太低了。

如果你需要你的代码结构和现在一样（调用 LP 解决，对信息做一些事情，继续解决）你现在被选项 1 困住了（变量类型的改变不会是性能问题，但您实际上会在更改变量类型后重新开始求解）。

遗憾的是，SCIP 目前没有解决松弛问题然后停止的功能，可以选择继续整个 MIP 解决方案。

希望对您有所帮助，如果您对我的回答有任何不清楚的地方，请告诉我。

使用 SCIP 获得 MIP 的 LP 松弛的最佳方法

Best way to obtain the LP relaxation of a MIP using SCIP

linear-programming

scip