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

fergal mohan fergal at mohandigital.com
Thu Jul 2 18:38:27 MEST 2009


Hi guys, thanks for helping me tease out the details. I'm actually providing (Managed) C++ interface methods so that any .NET language can use the Solvers. I suspect that I can access the Soplex LP data (like dual variables, reduced costs or basis information) directly, even if I've used SCIP to setup the LP. In terms of the optimal design I'm inclined to start using SCIP for MIP and I'll see if I can make a conditional compile to build it eaither way (SCIP or Soplex only) for LP. I might be able to answer the overhead questions if all goes according to plan. Let me know if there is any more related wisdom on this, cheers,
Fergal

--- On Thu, 7/2/09, Timo Berthold <berthold at zib.de> wrote:

> From: Timo Berthold <berthold at zib.de>
> Subject: Re: [Scip] Is using a subset of SCIP (e.g. B&B) possible to extend Soplex capabilites for limited MIP functionality?
> To: "Tobias Achterberg" <achterberg at zib.de>
> Cc: scip at zib.de, "fergal mohan" <fergal at mohandigital.com>
> Date: Thursday, July 2, 2009, 6:38 AM
> 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