CODEWITHSUNDEEP
integer-programmingscip
wonko
wonko

Reputation: 123

SCIP infeasibility detection with a MINLP

I'm using SCIPAMPL to solve mixed integer nonlinear programming problems (MINLPs). For the most part it's been working well, but I found an instance where the solver detects infeasibility erroneously. 

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;

The solver is detecting infeasibility at the presolve phase. However, if you uncomment the two constraints that fix x and y to 4 and 12, the solver works and outputs the correct v and z values.

I'm curious about why this might be happening and whether I can formulate the problem in a different way to avoid it. One suggestion I got was that infeasibility detection is usually not very good with non-convex problems.

Edit: I should mention that this isn't just a SCIP issue. SCIP just hits the issue with this particular set K. If for instance I use bonmin, another global MINLP solver, I can solve the problem for this particular K, but if you expand K to go up to 15, then bonmin detects infeasibility when the problem remains feasible. For that K, I'm yet to find a solver that actually works. I've also tried minlp solvers based on FILTER. I'm yet to try BARON since it only takes GAMS input.

Upvotes: 1

Views: 1717

Answers (2)

stefan
stefan

Reputation: 929

Looking deeper into this instance, SCIP seems to do something wrong in presolve.

In cons_nonlinear.c:7816 (function consPresolNonlinear), remove the line

if( nrounds == 0 )

so that SCIPexprgraphPropagateVarBounds is executed in any case.

That seems to fix the issue.

Upvotes: 1

Gregor
Gregor

Reputation: 1375

There are very good remarks about modeling issues regarding, e.g., big-M constraints in the comments to your original question. Numerical issues can indeed cause troubles, especially when nonlinear constraints are present.

Depending on how deep you would like to dive into that matter, I see 3 options for you:

  1. You can decrease numeric precision by tuning the parameters numerics/feastol, numerics/epsilon, and numerics/lpfeastol. You can save the following lines in a file "scip.set" and save it to the working directory from where you call scipampl:

    # absolute values smaller than this are considered zero # [type: real, range: [1e-20,0.001], default: 1e-09] numerics/epsilon = 1e-07

    # absolute values of sums smaller than this are considered zero # [type: real, range: [1e-17,0.001], default: 1e-06] numerics/sumepsilon = 1e-05

    # feasibility tolerance for constraints # [type: real, range: [1e-17,0.001], default: 1e-06] numerics/feastol = 1e-05

    # primal feasibility tolerance of LP solver # [type: real, range: [1e-17,0.001], default: 1e-06] numerics/lpfeastol = 1e-05

    You can now test different numerical precisions within scipampl by modifying the file scip.set

  2. Save the solution you obtain by fixing your x and y-variables. If you pass this solution to the model without fixings, you get a message what caused the infeasibility. Usually, you will get a message that some variable bound or constraint is violated slightly outside a tolerance.

  3. If you want to know precisely through which presolver a solution becomes infeasible, or if the former approach does not show any violation, SCIP offers the functionality to read in a debug solution; Specify the solution file "debug.sol" by uncommenting the line in src/scip/debug.h

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

    and recompile SCIP and SCIPAmpl by using

    make DBG=true

    SCIP checks the debug-solution against every presolving reduction and outputs the presolver which causes the trouble.

I hope this is useful for you.

Upvotes: 2

Related Questions