1

我正在使用 SCIPAMPL 来解决混合整数非线性规划问题 (MINLP)。在大多数情况下，它运行良好，但我发现了一个求解器错误地检测到不可行性的实例。

set K default {};

var x integer >= 0;
var y integer >= 0;
var z;
var v1{K} binary;

param yk{K} integer default 0;
param M := 300;                              
param eps := 0.5;                        

minimize upperobjf:
    16*x^2 + 9*y^2; 

subject to
    ll1: 4*x + y <= 50;
  ul1: -4*x + y <= 0; 
  vf1{k in K}: z + eps <= (x + yk[k] - 20)^4 + M*(1 - v1[k]);     
  vf2: z >= (x + y - 20)^4;
  aux1{k in K}: -(4*x + yk[k] - 50) <= M*v1[k] - eps;    
  # fix1: x = 4;
  # fix2: y = 12;

let K := {1,2,3,4,5,6,7,8,9,10,11};
for {k in K} let yk[k] := k - 1;
solve;
display x,y,z,v1;

求解器在预求解阶段检测到不可行性。但是，如果取消注释将 x 和 y 固定为 4 和 12 的两个约束，求解器将工作并输出正确的 v 和 z 值。

我很好奇为什么会发生这种情况，以及我是否可以用不同的方式来解决这个问题来避免它。我得到的一个建议是，对于非凸问题，不可行性检测通常不是很好。

编辑：我应该提到这不仅仅是一个 SCIP 问题。SCIP 只是解决了这个特定集合 K 的问题。例如，如果我使用另一个全局 MINLP 求解器 bonmin，我可以解决这个特定 K 的问题，但是如果你将 K 扩展到 15，那么当问题仍然可行。对于那个 K，我还没有找到一个真正有效的求解器。我还尝试过基于 FILTER 的 minlp 求解器。我还没有尝试 BARON，因为它只需要 GAMS 输入。

4

2 回答 2

2

在对原始问题的评论中，有关于建模问题的很好的评论，例如大 M 约束。数值问题确实会引起麻烦，尤其是在存在非线性约束时。

根据您想深入研究该问题的程度，我为您提供了 3 个选项：

  1. numerics/feastol您可以通过调整参数、numerics/epsilon和来降低数值精度numerics/lpfeastol。您可以将以下行保存在文件“scip.set”中并将其保存到您调用的工作目录中scipampl：

    # 小于这个值的绝对值被认为是零 # [type: real, range: [1e-20,0.001], default: 1e-09] numerics/epsilon = 1e-07

    # 小于这个值的和的绝对值被认为是零 # [type: real, range: [1e-17,0.001], default: 1e-06] numerics/sumepsilon = 1e-05

    # 约束的可行性容差 # [type: real, range: [1e-17,0.001], default: 1e-06] numerics/feastol = 1e-05

    # LP 求解器的原始可行性容差 # [type: real, range: [1e-17,0.001], default: 1e-06] numerics/lpfeastol = 1e-05

    您现在可以scipampl通过修改文件来测试不同的数值精度scip.set

  2. x通过修复和 -变量保存您获得的解决方案y。如果您将此解决方案传递给模型而不进行修复，您会收到一条消息，说明导致不可行的原因。通常，您会收到一条消息，指出某些变量界限或约束稍微超出了公差范围。

  3. 如果您想准确地知道解决方案通过哪个预求解器变得不可行，或者如果前一种方法没有显示任何违规，SCIP 提供了读取调试解决方案的功能；通过取消注释中的行来指定解决方案文件“debug.sol”src/scip/debug.h

    /* #define SCIP_DEBUG_SOLUTION "debug.sol" */

    并使用重新编译 SCIP 和 SCIPAmpl

    make DBG=true

    SCIP 针对每个预求解缩减检查调试解决方案，并输出导致问题的预求解器。

我希望这对你有用。

于 2014-07-17T10:15:32.577 回答
1

深入研究这个实例，SCIP 似乎在 presolve 中做错了什么。

在 cons_nonlinear.c:7816（函数 consPresolNonlinear）中，删除该行

if( nrounds == 0 )

以便在任何情况下都执行 SCIPexprgraphPropagateVarBounds。

这似乎可以解决问题。

于 2014-08-09T14:33:21.620 回答