[Scip] Is using a subset of SCIP (e.g. B&B) possible to extend Soplex capabilites for limited MIP functionality?

Timo Berthold berthold at zib.de
Thu Jul 2 15:38:44 MEST 2009


Heyho Fergal, Tobi.



Am Thursday 02 July 2009 15:27:21 schrieb Tobias Achterberg:
> Fergal,
>
> as an additional note: if you need to access LP or simplex specific data
> like dual variables, reduced costs or basis information, then you need to
> solve your LPs directly with Soplex, because SCIP cannot (easily) provide
> this information; it is a MIP solver and for MIP such concepts do not
> exist.

That was what I was thinking of when writing
> This depends on which information (and which
> solution, see below) you are interested in.
I somehow lost this point. Thanks, Tobias. :-)

> And, of course, there is an overhead in calling SCIP to solve LPs. So, if
> you really want to solve the LP without any integrality restrictions, then
> it is faster to call Soplex directly because SCIP involves some additional
> data copying operations and presolving stuff that is not useful for LPs.
> But if you want to solve LPs and MIPs through the same interface, then the
> only way to go is to call SCIP methods because Soplex is just not able to
> deal with integrality restrictions.

That's right. Anyway, the overhead is not too bad. If you don't have memory 
problems and do not care for an additional 10% running time (wild guess), you 
should be fine with a single (SCIP) interface.
This, by the way, allows one to switch the LP solver easily by just linking 
SCIP to another LP solver like Clp, Cplex,... without writing a new 
interface!
Of course, seperate interfacing would be smarter. ;-)

Best, Timo

PS: Much action on the mailing list today
>
> Tobias
>
> Timo Berthold wrote:
> > Hi Fergal,
> >
> > My first shot answer is: This depends on which information (and which
> > solution, see below) you are interested in. ;)
> > SCIP provides several interface methods to access information of the
> > optimal / incumbent solution.
> > Have a look at the doxygen docu of scip.h:
> > http://scip.zib.de/doc/html/scip_8h.html
> > Under "Functions", there is as section "Primal Solution Methods".
> > I guess the most important for you are SCIPgetBestSol(), SCIPprintSol(),
> > SCIPgetSolVals(), SCIPgetSolOrigObj().
> > There are some more methods in pub_sol.h.
> >
> > Independent of the problem type (LP/MIP), these methods should give you
> > want The only thing, which is different in the case of MIP, is that there
> > also is information on the LP relaxation available. If you were
> > interested in the solution a variable takes in the LP relaxation of the
> > problem, you might call SCIPvarGetRootSol(), which is located in
> > pub_var.h
> >
> > Furthermore, there is some information on primal solutions and the
> > interdependance between the "transformed" and the "original" problem in
> > the SCIP FAQ, which can be found at the homepage.
> >
> > Best, Timo
> >
> > Am Thursday 02 July 2009 14:15:25 schrieb fergal mohan:
> >> As a stepping stone to get back to my current state (successful LP
> >> solving), I'm just wondering whether I can continue to call directly
> >> into Soplex for retrieving LP solution data or will I need to route all
> >> my calls through as yet undiscovered equivalent SCIP methods ? I realize
> >> that for MIP I'll need to involve SCIP methods. Any ideas on this or do
> >> I need to do some experimenting ? Fergal
> >>
> >> --- On Wed, 7/1/09, Marc Pfetsch <m.pfetsch at tu-bs.de> wrote:
> >>> From: Marc Pfetsch <m.pfetsch at tu-bs.de>
> >>> Subject: Re: [Scip] Is using a subset of SCIP (e.g. B&B) possible to
> >>> extend Soplex capabilites for limited MIP functionality? To: "fergal
> >>> mohan" <fergal at mohandigital.com>
> >>> Cc: scip at zib.de
> >>> Date: Wednesday, July 1, 2009, 11:56 PM
> >>>
> >>> Hi Fergal,
> >>>
> >>> here is a partial answer to your questions:
> >>>
> >>> 1) In principle, SCIP should work similar to Soplex when
> >>> all variables are continuous (because of some technical
> >>> constraints this is not quite true, if the problem is
> >>> unbounded). In fact, if SCIP is linked with Soplex, it uses
> >>> Soplex to solve the LP and then basically returns the
> >>> result.
> >>>
> >>> 2) If some of the variables are integer and you want to
> >>> have the real optimum, you need to use something else than
> >>> just Soplex. This is, because mathematically the problem
> >>> with or without integer variables differ significantly in
> >>> their worst case complexity.
> >>>
> >>> Here are some suggestions:
> >>>
> >>> a) You settle for an approximate solution. It is -
> >>> depending on your problem - sometimes possible to obtain a
> >>> solution in which all the variables you want to be integer
> >>> are integer, by rounding the fractional solution.
> >>>
> >>> b) If you have few variables that are integer, you might
> >>> want to implement a "lightweight" version of the process
> >>> behind SCIP. It is called branch-and-bound, which basically
> >>> enumerates all possible values for the integer variables and
> >>> each step solves the resulting linear program (using Soplex,
> >>> for example), so that the continuous variables get the
> >>> "right" values. Of course, SCIP is much more sophisticated
> >>> than that, but if you have really few variables that are
> >>> integer, this might be a possibility.
> >>>
> >>> c) You just use SCIP. This should work fine.
> >>>
> >>> d) There are many other possibilities around, which all
> >>> would require more or less implementation effort.
> >>>
> >>> 3) Thus, the answer to your question would depend on the
> >>> amount of work you are willing to invest. The easiest would
> >>> just to use SCIP in all cases (or better: in the cases in
> >>> which there are integer variables). If there a significant
> >>> amount of integer variables, this seems to absolutely
> >>> necessary.
> >>>
> >>> 4) Writing a plugin for SCIP does not seem to make sense
> >>> for your application. If you decide to use SCIP for solving
> >>> a problem with integer variables, it seems best (at least as
> >>> a first try) to just let SCIP handle the problem. Of course,
> >>> you can always think about a solution method tailored
> >>> towards you application - I do not know whether you want to
> >>> do this.
> >>>
> >>>
> >>> I hope this helps,
> >>>
> >>> Marc
> >>>
> >>> fergal mohan schrieb:
> >>>> Hi all, I'm working on a Microsoft .NET wrapper for
> >>>
> >>> Soplex but I need
> >>>
> >>>> a fairly limited MIP solving capability. It's for a
> >>>
> >>> specific project
> >>>
> >>>> to aid researchers into Power Grid modelling (an
> >>>
> >>> Academic version of
> >>>
> >>>> Plexos for Power Systems) but could be used by other
> >>>
> >>> .NET
> >>>
> >>>> Applications in the future. The LP solving is working
> >>>
> >>> fine but from
> >>>
> >>>> time to time (rarely enough) I need to specify some of
> >>>
> >>> the variables
> >>>
> >>>> as integer. I'm considering switching between calling
> >>>
> >>> SCIP and Soplex
> >>>
> >>>> depending on whether I have integer constraints to get
> >>>
> >>> the code
> >>>
> >>>> working (though there would be a lot of overhead using
> >>>
> >>> SCIP in this
> >>>
> >>>> manner). Alternatively it might make sense to rewrite
> >>>
> >>> my interface
> >>>
> >>>> methods to always use SCIP (even if I'm dealing with
> >>>
> >>> LP solving)? My
> >>>
> >>>> intuition tells me that the full SCIP package would
> >>>
> >>> probably be
> >>>
> >>>> overkill for this limited case and was wondering if I
> >>>
> >>> could hook in
> >>>
> >>>> at a lower level (maybe using a plug-in).  I'm
> >>>
> >>> really hoping for some
> >>>
> >>>> guidance that might point me in the optimum direction
> >>>
> >>> before I launch
> >>>
> >>>> into development of something that might need to be
> >>>
> >>> reworked. Any
> >>>
> >>>> suggestions would be greatly appreciated. Fergal
> >>>>
> >>>> _______________________________________________ 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




More information about the Scip mailing list