Re: [Help-glpk] experiences with GLPK B&B (integer, binary) execution times?

[Jérôme Kunegis]

Hello,

Re:  Björn from 30.08.2005: 
> I am solving linear problems with integer and mostly (80%) binary variables, 
> and I am planning to use the GLPK B&B solver. I know the problem is NP-hard 
> (unfortunately).
> 
> Does anybody have experiences regarding the execution times (on whatever 
> hardware you have used) when using various matrix sizes? For example, with 
> 1000, 10000, 100000, a million, ten million elements? (Does GLPK contain any 
> optimization for binary elements?)

A month or so ago I made some tests using GLPK, with only binary
variables.  

Setup:  There a N binary variables and N^2 constraints.  The constraints
were genearted at random by a C program and output in the Cplex format. 
For each variable, the probability of a factor being 0 was set to 50%. 
If factors were not 0, they were +1 or -1 with equals probability.  GLPK
was executed on an Opteron system with 4 processors and 16GB memory. 
Both the kernel (from SuSE Linux) and GLPK were compiled as 32-bit.  

I used "time" to measure the execution time and memory usage of GLPK,
including the time to parse the input files.  The bottleneck was the
memory.  Here are the results:
     
         N         time (s)       mem (MiB)
 
        70          0.0             17.2
       100          1.0             48.9
       150          4.0            162
       200         10.0            380
       300         35.0           1270
       350         56.0           2010
       400                ENOMEM

So the biggest matrix size was 400x160,000=64,000,000 elements with
half of non-zeroes.  Using a 64-bit operating system and compiling 
GLPK as 64-bit would probably have increased the maximum matrix size.

Regards,
        Jérôme KUNEGIS



-- 
 ___________________________________________________________________ 
 Jérôme KUNEGIS                  Technische Universität Berlin         
 Fakultät Informatik, Agententechnologien in betrieblichen 
 Anwendungen und in der Telekommunikation, DAI-Labor 
 Franklinstraße 28/29   E-Mail:   address@hidden
 D-10587 Berlin        
 Sekr. GOR 1-1          Tel:      (030) 314 73600