[Scip] some theoretical questions about SCIP

Ambros Gleixner gleixner at zib.de
Mon Apr 21 11:13:45 CEST 2014


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

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


More information about the Scip mailing list