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

[Brady Hunsaker]

Björn wrote:
> Hello!!
> 
> 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?)
> 
> Thank you a lot for sharing any experiences.
> 
> Best regards
> Bjoern
> 

This should probably be in a FAQ somewhere.  Such times may be useful as
comparisons of different solvers, but I don't recommend using other
people's run times to predict run times for your instances.  The time
taken to solve an instance depends a great deal on the structure of the
constraints--not just on the size of the matrix or number of nonzeros.

I think you will have to test your own instances (or instances that you
believe have a similar structure of constraints) to get an accurate
sense of the size that GLPK can handle.

I don't believe that GLPK does anything special with binary variables
right now.

Brady

-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/