Re: [Help-glpk] Huge problem.. can glpk solve it?

[François Galea]

Antonello Lobianco a écrit :
> Hello, I have a problem of 1-to-1 match between elements of a first set with 
> those of a second set according with the minimisation of a "distance" between 
> the various elements..
>
> I have try a simple trial matrix in Excel and it works (attached image), but
> the real problem has 375 elements in each set resulting in a matrix with 
> 375*375 decision variables and 375*2 bounds (all continuous).
>
> Can glpk handle such problem on a good pc??
>
> Cheers,
>     Antonello Lobianco

Sure, it can. But there is at least one much more efficient method than 
mixed-integer programming, known as the "Hungarian method" :

http://www.ee.oulu.fi/~mpa/matreng/ematr1_2.htm

I guess it should be possible to program it directly in an Excel macro.


--
François Galea
Equipe OPALE - Laboratoire PRiSM
Université de Versailles-Saint Quentin en Yvelines
45 av Etats-Unis F-78035 Versailles CEDEX
Tél. : +33 1 39 25 40 50