首页 文章

用MINLP检测SCIP不可行性

提问于
浏览 次
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集来解决问题 . 例如，如果我使用bonmin，另一个全局MINLP求解器，我可以解决这个特定K的问题，但是如果你将K扩展到15，那么bonmin检测到不可行性问题仍然可行 . 对于那个K，我还没找到一个真正有效的解算器 . 我也尝试过基于FILTER的minlp求解器 . 我还没有尝试BARON因为它只需要GAMS输入 .

integer-programming scip

2 回答

  • 2

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

    根据您想深入了解的程度，我会看到3个选项：

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

    ＃绝对值小于此值＃[type：real，range：[1e-20,0.001]，默认值：1e-09] numerics / epsilon = 1e-07

    ＃小于此值的和的绝对值被认为是零＃[type：real，range：[1e-17,0.001]，默认值：1e-06] numerics / sumepsilon = 1e-05

    ＃约束的可行性容差＃[type：real，range：[1e-17,0.001]，默认值：1e-06] numerics / feastol = 1e-05

    #pp解算器的原始可行性公差＃[类型：实际，范围：[1e-17,0.001]，默认值：1e-06]数字/ lpfeastol = 1e-05

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

    • 通过修复 x 和 y -variables保存您获得的解决方案 . 如果您将此解决方案传递给没有固定的模型，则会收到导致不可行性的消息 . 通常，您会收到一条消息，表明某个变量绑定或约束在公差范围之外略有违反 .

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

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

    并使用重新编译SCIP和SCIPAmpl

    make DBG=true

    SCIP针对每个预处理减少检查调试解决方案并输出导致故障的预分解器 .

    我希望这对你有用 .

    回复于
  • 1

    深入研究这个实例，SCIP似乎在预测中做错了 .

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

    if( nrounds == 0 )

    这样就可以在任何情况下执行SCIPexprgraphPropagateVarBounds .

    这似乎解决了这个问题 .

    回复于

相关问题