help-glpk
[Top][All Lists]

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

 From: Ali Baharev Subject: Re: [Help-glpk] Huge problem.. can glpk solve it? Date: Tue, 12 Jun 2007 12:47:40 +0200

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