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

Marc Pfetsch m.pfetsch at tu-bs.de
Thu Jul 2 08:56:33 MEST 2009


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