[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 14:15:25 MEST 2009


Hi Marc, thanks a million for taking the time to write a detailed reply, I really appreciate the "educated" advice to get me going in the right direction. I will start by re-wiring my .NET wrapper interface to communicate with SCIP instead of Soplex directly and hopefully get back to the solving LP problems without too much disruption before I even deal with MIP. 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
> 
> 



More information about the Scip mailing list