[Scip] some theoretical questions about SCIP

[Ambros Gleixner]

Dear Wei,


Am 20.04.2014 00:33, schrieb Wei Wang:
> Hi,
>
> I have a few questions on the theoretical part of SCIP. I skimmed over
> Dr/.Achterberg///'s dissertation. Unfortunately, theory is not my field
> of research, so I was completely lost when I read it. I hope somebody on
> this list can help with these questions. Here are my questions:
>
> First, what is the theoretical complexity of SCIP when solving an
> integer programming problem?

the worst-case running time is exponential in the size of the integer 
domains.


> Second, how is the approach used by SCIP compared to Lenstra's algorithm
> and its variants? Is SCIP's algorithm performs better than them?
> Additionally, is SCIP related to Lenstra's algorithm? It seems to me
> they are related, but Lenstra's paper was not referenced in the
> dissertation.

Except that LLL can also be used to solve IP, there is no simple 
relationship.  There are certain IPs that might be better solved by 
lattice reduction, see, e.g., the article

Aardal et al. 2000, Market Split and Basis Reduction: Towards a Solution 
of the Cornuéjols-Dawande Instances , 
http://dx.doi.org/10.1287/ijoc.12.3.192.12635

but for most cases the LP-based branch-and-cut that SCIP follows is 
state-of-the-art.


> Third, is that possible to speed up SCIP with multi-threading? Or, can
> SCIP's algorithm be partitioned into concurrent parts?

Yes, see the UG framework in the SCIP Optimization Suite that provides 
an external parallelization at ug.zib.de.


Have fun,

ambros



>
> Thank you,
> Wei
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner