[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Huge problem.. can glpk solve it?
From: |
Oscar Gustafsson |
Subject: |
Re: [Help-glpk] Huge problem.. can glpk solve it? |
Date: |
Tue, 12 Jun 2007 10:13:31 +0200 (MEST) |
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