如何让Google OR-Tools的MPSolver返回首个可行解？RELATIVE_MIP_GAP用法验证

问题背景 #

我有一个计算耗时过长的MIP（BP，最大化）问题，希望让MPSolver返回其找到的首个可行解，同时确认自己是否正确使用了RELATIVE_MIP_GAP求解器参数，尝试了两种方法：

方法1：回调函数 #

查阅文档后发现，MPSolver不支持求解迭代过程的回调机制（仅CpSolver支持），无法实现找到首个可行解即停止的逻辑。

方法2：以相对间隙作为终止准则 #

我用Kotlin代码尝试设置RELATIVE_MIP_GAP：

val mpSolverParameters = MPSolverParameters().apply {
    setDoubleParam(MPSolverParameters.DoubleParam.RELATIVE_MIP_GAP, 1.0)
}
solver.solve(mpSolverParameters)

根据文档注释，RELATIVE_MIP_GAP设为0.05代表5%的间隙，因此1.0应对应100%的间隙。按预期，设置1.0后求解器找到任意可行解就该停止（我的目标函数始终为正，不存在符号问题，整数解与连续松弛解的相对差异必然在100%范围内），但实际设置未生效：添加时间限制时，求解器会在时间结束后返回解；移除时间限制后，求解器会持续运行，远超之前时间限制的时长仍不返回结果。

可行解决方案 #

• Laurent Perron的两项建议均适用于当前场景。
• 若使用SCIP求解器，可调用solver.setSolverSpecificParametersAsString("limits/solutions = 1")获取首个可行解（解质量较差，可按需增大参数值）；同时可调用求解器对象的setTimeLimit(timeInMs)方法设置时间限制，到时间后返回当前找到的最优可行解，未找到解则返回未求解状态。
• 目前仍未明确RELATIVE_MIP_GAP参数未生效的原因，该参数属于API而非求解器特定参数。

内容的提问来源于stack exchange，提问作者Tamás Sajti