[SCIP] Degeneracy and abs function

[Stefan Vigerske]

Hi,

On 1/21/21 11:22 AM, Marc Pfetsch wrote:
> 
> 
> Hi Jennifer!
> 
>> - What influence does degeneracy of the MINLP (A point that does not
>> satisfy LICQ) have? I imagine, that feasible, degenerate points can be
>> falsely identified as a local optimum in subproblems by NLP solvers.
>> This would give poor upper bounds and branching would take more time.
>> Are there any other consequences? Does it effect the lower bound? Can it
>> cause SCIP to give false results?
> 
> Note that SCIP tries to solve the MINLP to global optimality - I am just
> stressing this, because LICQ concerns the local optima.
> 
> The SCIP-default is to use an LP-based approach, i.e., it solves only
> LP-relaxations (see also the next point). Thus, constraint
> qualifications like the LICQ are not necessary for solving the relaxations.
> 
> However, there might be a connection between the instances in which no
> CQ holds at optimal (or any/some local) solutions and instances which
> are empirically hard to solve.
> 
> With respect to false results: This is might happen because of numerics,
> but I do not see a direct connection to CQs.
> 
>> - Does SCIP call NLP solvers after all integer variables have been
>> fixed? Or are NLP solvers already called before that?
> 
> By default, no NLP solvers are used for solving the relaxations.

Just to add, the primal heuristics that solve NLPs do not wait until the 
LP relaxation solution is no longer fractional (in the integer 
variables). There are a (big) number of heuristics that construct 
solutions that are feasible for the LP and not fractional. Some of these 
solutions are used to fix integer variables and solve the remaining NLP 
with Ipopt. And then there are a (small) number of heuristics that solve 
a sequence of NLPs, starting with integrality being relaxed and 
enforcing it more and more.

> However, the SCIP distribution contains an example that shows how to
> solve NLPs as relaxations
> (https://scipopt.org/doc-7.0.2/html/RELAXATOR_MAIN.php). In this case,
> the NLP-solver used for SCIP is used to solve the relaxations. Usually
> IPOPT is used for this. The NLPs are automatically constructed also in
> the default LP-based approach in order to compute primal solutions. In
> such an NLP-based approach it would make sense to solve the relaxation
> independently of whether all integer variables are fixed, but this might
> depend on the instance.
> 
> Just to complement the picture: SCIP-SDP
> (https://wwwopt.mathematik.tu-darmstadt.de/scipsdp/) solves SDPs at each
> node. Here the existence of a CQ (in this case of the Slater condition)
> is quite relevant for the practical (and theoretical) performance.
> 
>> - How does SCIP handle the abs function? In which form is it given to
>> the solver?
> 
> Here I am not sure. Sometimes this can be reformulated using additional
> continuous and/or binary variables - at least if your variables are
> bounded. Moreover, one can relatively easily construct lower and upper
> linear bounds (y \geq |x| is convex and y \leq |x| could be upper
> bounded using a secant cut).

SCIP should handle the abs() correctly, i.e., the LP relaxation is valid 
and as one would expect. However, it doesn't ensure to branch on 0. So 
you would probably see better performance by doing a linear 
reformulation of the abs in your model.

Stefan

> 
> I hope this helps.
> 
> Best,
> 
> Marc
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>