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

[Oscar Gustafsson]

Hi Antonello!

> 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).
I think I understand your problem correctly, but I'm not sure where the 
2*375 bounds come in. It seems like you would like to add the constraints

\sum_{i=1}^{375} x_i_j = 1, \all j 
\sum_{j=1}^{375} x_i_j = 1, \all i

where x_i_j denotes that the combination Ai_Bj is selected. 
Almost independent of solution technique this would help the solver.

> Can glpk handle such problem on a good pc??
I believe that it would be possible. It shouldn't be too hard to try 
(except for the input of the 375*375 weights...).

An alternative would be to solve it as a Pseudo-Boolean problem. This is 
another class of solvers dedicated at solving problems with pure 
0/1-variables. Some information of the input format is available at:
http://www.cril.univ-artois.fr/PB07/solver_req.html

However, there is a PB-frontend to GLPK available at:
http://www.es.isy.liu.se/staff/oscarg/pbglp/
but it can not read MathProg files at the moment. If you write your 
problem using mathprog and want to convert it to PB in a simple way I 
can probably add support for that quickly.

If you are looking for one pure PB solver I would suggest starting with 
minisat+:
http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/MiniSat+.html

One note on PB is that integer weights are required, but it should be 
possible to scale it with a suitably large integer in most cases.

With best regards

Oscar Gustafsson