[Scip] SCIP behavior in nonlinear vs linear cases

[Ambros Gleixner]

Dear Ahmad,

the difference is that SCIP will not stop with the secant, but explore 
(a relaxation of) the feasible region completely.

The static approximation may give you a point which is infeasible (or 
suboptimal in the case where a concave objective function is the only 
nonlinearity present).  Take the example min -x*x s.t. -1 <= x <= 1, 
reformulated as

    min z s.t. z >= -x*x, -1 <= x <= 1.

If you underestimate -x*x by the secant z >= -1 going through points 
x=-1 and x=1 and solve the (MI)LP, you might get x=0, which is 
suboptimal for the original MINLP.  Of course, you can choose the static 
underestimation smart enough that this will not happen in this simple 
example (use z >= x and z >= -x), but in general there is no static 
approximation that would guarantee you getting a fully feasible and 
optimal solution.

"Dynamic approximation" is probably not a good term for what SCIP does. 
  SCIP does not build a piecewise linear approximation of the problem 
and certainly does not force the solution to be on a piecewise linear 
approximation, not even a dynamically refined one.  It encloses the 
feasible solutions in a linear relaxation and tries to fully explore 
this relaxation by branch-and-bound (branching also on continuous 
variables).  It would not introduce auxiliary binary variables to 
formulate a non-convex underestimator.

In the example above, e.g., if the relaxation yields x = 0 at the root 
node, SCIP would create two children: in the left child, z >= x is added 
to the relaxation, in the right child, z >= -x is added.  Hence, the 
point x=0,z=-1 is no longer feasible in both children.  Solving the 
relaxation of the left child would give x=-1,z=-1, which is feasible for 
the original nonlinear constraint z >= -x*x and also globally optimal.

I hope this helps,

Ambros




Am 15.05.2013 15:54, schrieb Ahmad Moradi:
> Dear all,
>
> I am working on a network design problem with concave cost function and
> linear constraints. I implemented the problem in the following two forms
>
> 1. I directly added the concave cost objective function through expression
> trees as nonlinear constraints. lets call this case "dynamic approximation".
>
> 2. I approximated the objective function with piecewise linear functions
> (with fixed number of breakpoints) and then I have given the resulting MILP
> to SCIP. lets call this case "static approximation".
>
> I know that SCIP in dynamic case, will convexify the feasible region by
> linearizing the nonlinear constraint (uses only two breakpoints and makes
> the linearization by replacing a simple secant instead of the nonlinear
> constraint ).
>
> Now, I want to know, what is essentially the different between
> SCIP's behavior on this two cases?
>
> bests, Ahmad
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner