1

混合整数非線形計画問題 (MINLP) を解くために SCIAMPL を使用しています。ほとんどの場合、うまく機能していますが、ソルバーが実行不可能性を誤って検出する例を見つけました。

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 に固定する 2 つの制約のコメントを外すと、ソルバーが機能し、正しい v と z の値が出力されます。

なぜこれが起こっているのか、そしてそれを回避するために別の方法で問題を定式化できるかどうかに興味があります. 私が得た 1 つの提案は、通常、非凸の問題では実行不可能性の検出があまりうまくいかないというものでした。

編集: これは単なる SCIP の問題ではないことに注意してください。SCIP は、この特定のセット K で問題を解決するだけです。たとえば、別のグローバル MINLP ソルバーである bonmin を使用すると、この特定の K の問題を解決できますが、K を 15 まで拡張すると、bonmin は実行不可能性を検出します。問題は実行可能のままです。その K については、実際に機能するソルバーをまだ見つけていません。FILTER に基づく minlp ソルバーも試しました。BARON は GAMS 入力のみを使用するため、まだ試していません。

4

2 に答える 2

1

このインスタンスを詳しく調べてみると、SCIP は presolve で何か間違ったことをしているようです。

cons_nonlinear.c:7816 (関数 consPresolNonlinear) で、次の行を削除します。

if( nrounds == 0 )

どのような場合でも SCIPexprgraphPropagateVarBounds が実行されるようにします。

これで問題は解決したようです。

于 2014-08-09T14:33:21.620 に答える