1

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.

wonko
  • 123
  • 1
  • 6
  • As I mentioned in the post, you can rerun the model fixing x and y to 4 and 12 and it will output an optimal solution. This alone tells me that this is a feasible solution to the original problem. I can independently verify this. You can set v1[k] to 1 if the left hand side of the inequality in aux1 is positive, and set it 0 if the left hand side is negative. Setting z to a value to enforce equality in vf2 will then produce a feasible solution. – wonko Jul 11 '14 at 18:24
  • Oh sorry I see now. Yes infeasibility detection can err but I would assume that it would err on the sadw side. Is the big M tight enough I assume? – Ioannis Jul 11 '14 at 19:34
  • What precisely do you mean by tight enough? Do you mean large enough? If so then yes it is. Can I make it smaller? I suspect the answer is also yes but I don't see how that would help. – wonko Jul 11 '14 at 20:45
  • Good practice with big M values is that they have the minimum value possible so that the resulting model is feasible. Large values might cause numerical issues. Smaller values reduce the feasible region of the linear programming relaxations and thus improve the solver performance during branch-and-bound. Your actual issue is probably due to round-off errors. [This response](http://stackoverflow.com/questions/16001462/solving-an-integer-linear-program-why-are-solvers-claiming-a-solvable-instance?rq=1) by David Nehme explains why fixing your variables makes the solver find a feasible solution. – Ioannis Jul 11 '14 at 21:24
  • I understand the point, but somehow I doubt that is the case here. Of course without knowing what's happening under the hood in the solvers, it's difficult to make the claim that it's not the issue at all. However, I did try lower values of M and found the problem persists. – wonko Jul 11 '14 at 21:32
  • In this case, I would try to increase the numerical accuracy of the solver. From a quick search it seems that [passing options to SCIP via SCIP-AMPL is complicated](http://listserv.zib.de/pipermail/scip/2013-September/001665.html). For Bonmin it [looks easier](http://www.coin-or.org/Bonmin/options_set.html#sec:opt˙nonconv). Can you give it a go? – Ioannis Jul 11 '14 at 21:46

2 Answers2

2

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.

Gregor
  • 1,333
  • 9
  • 16
  • Thanks for the suggestions. I'll try them out when I get the chance and let you know how it goes. – wonko Jul 17 '14 at 20:06
1

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.

stefan
  • 799
  • 4
  • 9