[SCIP] Clarification: Unexpected behavior

[Benjamin Müller]

Dear Lorenzo and Ahmed,

SCIP solves MINLPs to global optimality even if the problem is 
non-convex. Of course, if there are several optimal solutions you might 
end up with different of those if you change the solution process (e.g., 
by using different start solutions).

Clearly, the solution value of the relaxed version of your problem 
should lead to a better objective value. It seems to be that there is a 
bug which appears when SCIP restarts the solution process. This restart 
does not happen if s is continuous and thus you end up (luckily) with 
the same solution as before.

I will send you a patch as soon as I have fixed the bug. Until then you 
could disable restarts (set limits restarts 0).


Regards,

Benny



On 01/13/2016 09:47 PM, Ahmed Ibrahim wrote:
> I meant to say, you may end up with different solutions for the 
> different instances 0<=s<=10 and for 0<=s<=9. If it is the same 
> instance and you use different initial points, you can also end up 
> with different solutions.
>
> Regards,
> Ahmed
> ------------------------------------------------------------------------
> *From:* Scip [scip-bounces at zib.de] on behalf of Ahmed Ibrahim 
> [Ahmed.Ibrahim at umanitoba.ca]
> *Sent:* Wednesday, January 13, 2016 2:08 PM
> *To:* Lorenzo Gentile
> *Cc:* scip at zib.de
> *Subject:* Re: [SCIP] Unexpected behavior
>
> Hi Lorenzo,
> It seems this is a non-convex MINLP problem. I'm not sure if such 
> problems, except for quadratic ones, are "_guaranteed_" to be solved 
> to global optimality by most solvers. I think it's more likely that 
> you are hitting the node limit or iteration limit and it returns the 
> best solution it found so far. Hence every time you solve it, you may 
> end up with different solutions.
>
> Regards,
> Ahmed
> ------------------------------------------------------------------------
> *From:* Scip [scip-bounces at zib.de] on behalf of Lorenzo Gentile 
> [lorenzo.gentile at moxoff.com]
> *Sent:* Wednesday, January 13, 2016 9:12 AM
> *To:* scip at zib.de
> *Subject:* [SCIP] Unexpected behavior
>
> Hello,
>
> I'm a new user on SCIP, and  interested in solving a non linear 
> constrained optimization problem. I would like to understand why SCIP 
> seems to return a wrong result if applied to a simplified optimization 
> problem whose solution is known a priori.
>
> Here is my first formulation:
>
> var y real >= 0;
> var x real >= 0 <= 10;
> var s integer >= 0 <= 9;
> var z binary;
>
> subto c1: y <= (1-exp(-x))*(1-z)+(1-exp(-(x-s))+1-exp(-s))*z;
> subto c2: s*z <= x;
> subto c3: x <= 10*z + s*(1-z);
>
> maximize obj: y;
>
> In this case I obtain what I expect (y almost equal to 2):
>
> objective value: 1.98652410600183
> z           1 (obj:0)
> s           5 (obj:0)
> y  1.98652410600183 (obj:1)
> x          10 (obj:0)
> @@c1_1_t_0           -5 (obj:0)
> @@c1_1_r_1  0.00673794699908548 (obj:0)
> @@c1_1_t_2           -5 (obj:0)
> @@c1_1_r_3  0.00673794699908546 (obj:0)
> @@c1_1_t_4          -10 (obj:0)
> @@c1_1_r_5 4.43999297170849e-05 (obj:0)
> prodt_z_t_s_c2_1            5 (obj:0)
> prodt_z_t_s_c3_1            5 (obj:0)
> nlreform0          -5 (obj:0)
>
> Now, If I enlarge the admissible region by writing 'var s integer >= 0 
> <= 10;' (and keeping everything else unchanged), I obtain a worse 
> solution (y almost equal to 1):
>
> objective value:  0.999955600070283
> s          10 (obj:0)
> y 0.999955600070283 (obj:1)
> x          10 (obj:0)
> @@c1_1_r_1            1 (obj:0)
> @@c1_1_t_2          -10 (obj:0)
> @@c1_1_r_3 4.53999297624415e-05 (obj:0)
> @@c1_1_t_4          -10 (obj:0)
> @@c1_1_r_5 4.43999297170849e-05 (obj:0)
>
> The solution found with the first formulation is still admissible, it 
> is better (higher y value) but it is not returned by the second 
> formulation.
>
> Finally, if I write 'var s real >= 0 <= 10;'(and keeping everything 
> else unchanged), SCIP returns again what I expect (y almost equal to 2):
>
> objective value: 1.98652491319583
> z           1 (obj:0)
> x          10 (obj:0)
> s  5.00321312966099 (obj:0)
> y  1.98652491319583 (obj:1)
> @@c1_1_t_0  -4.99678687033901 (obj:0)
> @@c1_1_r_1  0.00675919526185386 (obj:0)
> @@c1_1_t_2  -5.00321312966099 (obj:0)
> @@c1_1_r_3 0.0067158915423183 (obj:0)
> @@c1_1_t_4          -10 (obj:0)
> @@c1_1_r_5 4.43999297170849e-05 (obj:0)
> prodt_z_t_@@c1_1_t_2_c2_1  5.00321312966099 (obj:0)
> prodt_z_t_@@c1_1_t_2_c3_1  5.00321312966099 (obj:0)
> nlreform0 -4.99678687033901 (obj:0)
>
> Can you please explain me the reason of this unexpected behavior and, 
> if possible, tell me which part of the code is called by these 
> formulations.
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20160114/d694e7d2/attachment.html>