[Scip] some theoretical questions about SCIP

[Wei Wang]

Hi Ambros,

Thank you for the reply.  I have one follow-up question. Do you know any 
good papers that discuss the average complexity and worst-case 
complexity of the LP-based branch-and-cut method?

Thank you,
Wei


On 04/20/2014 12:04 PM, Ambros Gleixner wrote:
> 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
>>
>