[Scip] algorithm MINLP solver?

Timo Berthold berthold at zib.de
Fri Jan 25 10:10:05 MET 2013


Hi Stefan,

I don't know whether

> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1137
> http://www.math.hu-berlin.de/~stefan/diss.pdf
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1463
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1763
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1764

is the cure for

> The more I read, the less I understand...

;-)

So, @Ina: If I would have to state how SCIP works, say in a thesis, I
think it is fair to say that it is an LP-based branch-and-cut that uses
spatial branching to resolve nonconvexities over continuous variables.

This is (basically) what happens: SCIP uses an LP as relaxation (not an
NLP), it builds up a branch and bound tree, branching on integer variables
with fractional values in the LP, and at each node, potentially, cutting
planes are derived (from the nonlinear constraints) to strengthen the
relaxation.

The remaining question is what happens when all integer variables are fixed?
Well the remaining problem on the continuous problems might be:
a) an LP: easy, solving the relaxation does the job immediately
b) a convex NLP: not too bad, by separating cutting planes you can get a
solution that is feasible up to some epsilon-tolerance
c) a nonconvex NLP: hard, here branching on continuous variables is
performed, in order to reduce the convexification gap between the (convex)
LP relaxation and the actual constraints. In an extreme case, this might
continue until all variables have small (eps) enough domains that they can
be considered to be fixed.

Hope that helps.

Timo

> Hi,
>
> There is a mix of "branch-and-*" keywords out there and none of them
> exactly fits to what SCIP is doing :-).
> It's a tree search algorithm where branching is commonly done on
> variable bounds. The "spatial" indicates that it can branch also on
> continuous variables, while in the context of MIP and CIP, one usually
> branches only on discrete variables.
> The "-and-cut" comes from strengthening the linear relaxation by adding
> cutting planes.
> It's also a branch-and-reduce or branch-and-infer algorithm in the sense
> that it applies domain propagation (aka bound tightening).
>
> Some more detailed information on MINLP support in SCIP can be found at
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1137
> http://www.math.hu-berlin.de/~stefan/diss.pdf
> and
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1463
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1763
> http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1764
> and others I forgot (sorry).
>
> Stefan
>
> On 01/24/2013 08:20 PM, Liffey1986 at gmx.de wrote:
>> Dear SCIP-users,
>>
>> I am using SCIP as a solver for nonconvex MINLPs, but I don't exactly
>> understand how the algorithm works.
>>
>> As far as I know SCIP uses a spatial branch-and-bound-algorithm for
>> nonconvex MINLPs. But now I read it's also a branch-and-cut solver. Does
>> that mean, it's a spatial branch-and-cut-algorithm? Or am I mixing it up
>> now?
>> I'm a bit confused. The more I read, the less I understand...
>>
>> Many Thanks
>> Ina
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list