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

[Ali Baharev]

Here is a C implementation of the Hungarian method:

http://www.informatik.uni-freiburg.de/~stachnis/misc.html

Good luck,

Ali

On 6/12/07, Andrew Makhorin <address@hidden> wrote:
> > \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.
>
> > An alternative would be to solve it as a Pseudo-Boolean problem.
>
> If there are no other constraints, this is the assignment problem.
> Its constraint matrix is unimodular (i.e. any basic solution is
> integer feasible), so it can be solved as pure lp. Note that there
> exist some specialized algorithms (e.g.
> http://en.wikipedia.org/wiki/Hungarian_algorithm ), which are much
> more efficient than the simplex method (and even the network simplex
> method) to solve such problems.
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk