[SCIP] Questions regarding the gap with MINLP

[Stefan Vigerske]

Hi,

the gap works the same way for all problem types in SCIP. The dual and 
primal bounds should only move towards each other during the solve and 
not shift around.

For a MINLP, the dual bound is also computed by a linear relaxation. To 
get this, an outer-approximation is computed for nonlinear constraints.

A still not so old overview on the MINLP capabilities in SCIP is given 
in https://arxiv.org/abs/2301.00587
However, as an introduction to the topic, Ksenia's lecture at 
CO at work2020 could be a better choice: 
https://co-at-work.zib.de/berlin2020/  (thursday, 17.9)

All best,
Stefan

On 17/04/2024 12:27, Pavlos Bekiaris wrote:
> Hello everyone :D
> 
> I've got two questions about the gap that SCIP uses for MINLP (I hope the questions are not too silly, for which I'd like to pre-emptively apologize!). Coming from (mixed-integer) linear programming, a common definition of the gap is clear to me for (MI)LP as the current difference of the current best found optimum and the optimum of a relaxed problem. I also know that the gap in SCIP is defined in relation to the current difference of the primal and some dual optimization values (as detailed in your FAQ), but...
> 
> 1. For a non-convex MINLP, can I interpret the values of the primal and the dual value as boundaries of a region in which the ultimate optimal value lies? Or is it possible that both the dual and primal value shift further, so that the ultimate optimal value can lie somewhere out of any previous interval between primal and dual values?
> 2. Also, I'd greatly appreciate any hint (maybe some publication or slides?) where some concepts about the dualization of a MINLP in SCIP are further explained. My searches in this direction failed, I'm probably just using the wrong terminology :3
> 
> Kind regards :-)
> P.S.B.
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip