[Scip] some theoretical questions about SCIP

[Wei Wang]

Hi Ambros,

Thank you! I will check them out.

Wei
On 04/21/2014 05:13 AM, Ambros Gleixner wrote:
> Dear Wei,
>
> this is rather theoretical, but Grötschel Lovasz Schrijver's Geometric 
> "Algorithms and Combinatorial Optimization" or Schrijver's "Theory of 
> Linear and Integer Programming" are certainly standard references.
>
> ambros
>
>
> Am 20.04.2014 21:30, schrieb 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
>>>>
>>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>