[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: 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:

Good luck,


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. ), which are much
more efficient than the simplex method (and even the network simplex
method) to solve such problems.

Help-glpk mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]