[Scip] algorithm MINLP solver?

[Liffey1986@gmx.de]

Thanks a lot to both of you for your great help!

@Timo: Yes, I'm currently working on my thesis and trying to describe how SCIP works.

I'm still not sure if I got it right, so I'll describe how I think it works:

1. the MINLP is relaxed --> NLP
2. SCIP finds a linear and convex underestimator for the NLP (how is this done?, at which point?)--> LP
3. the LP is solved --> (x0,y0) is sollution
4. branching on an integer variable --> subproblems
5. SCIP adds cuts to the LP-subproblems

3-5 is done until all the yi are integer

After that SCIP branches on the continuous variables xi, until the gap is good enough.

Is that correct?

Regards,
Ina


-------- Original-Nachricht --------
> Datum: Fri, 25 Jan 2013 10:10:05 +0100 (MET)
> Von: "Timo Berthold" <berthold at zib.de>
> An: "Stefan Vigerske" <stefan at math.hu-berlin.de>
> CC: scip at zib.de, Liffey1986 at gmx.de
> Betreff: Re: [Scip] algorithm MINLP solver?

> 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
> >
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip