[SCIP] Degeneracy and abs function

[Marc Pfetsch]

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.
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).

I hope this helps.

Best,

Marc