🚀 go-pugleaf

In article <1992Oct14.043850.4095@pslu1.psl.wisc.edu> emmel@pslu1.psl.wisc.edu (Grant Emmel) writes:
>I'm looking for available software (public domain or not) for a
>non-commercial/non-educational application (I'm helping a friend)
>that will solve the assignment problem.  That is the general idea.
>
>Any help, from theory to software would be helpful.  Post if it is
>interesting enough, email in any case.
>Grant Emmel

A simple example of the assignment problem would be: There are n jobs 
and n different candidates for these jobs. We want to assign one 
and only one candidate to each job. There is a cost square matrix that
specifies the cost that has to be paid for candidate i to perform job
j, i=1,..,n, j=1,.., n. The objective is to minimize the cost.
The method which is used usually to solve the assignment problem is 
the "Hungarian method". It is a dual algorithm. The complexity is 
O(n^3). For a full description of the algorithm you can refer to 
"Linear and combinatorial programming" by K.G. Murty. It is in 
Chapter 12: Networ Algorithms. A more sophisticated approach is 
in "Network Programming" by the same author (This book was published
a few months ago so it may be hard to find it) from Prentice Hall.
The code should not be hard to write.
-Samer

takriti@engin.umich.edu (samer Takriti) writes:

>In article <1992Oct14.043850.4095@pslu1.psl.wisc.edu> emmel@pslu1.psl.wisc.edu (Grant Emmel) writes:
>>I'm looking for available software (public domain or not) for a
>>non-commercial/non-educational application (I'm helping a friend)
>>that will solve the assignment problem.  That is the general idea.
>>
>>Any help, from theory to software would be helpful.  Post if it is
>>interesting enough, email in any case.
>>Grant Emmel

>The code should not be hard to write.
>-Samer

Why bother? Try getting the code from netlib@ornl.com (I think the address is
right). There are also a couple of public domain ones, 

one is called netflo written by Kennington and Helagason at Southern Methodist
Univ and the other is called Relax III written by Bertsekas. I have implemented
an Interior point path following version (algo by PM Vaidya) which is better
than netflo and relax III only for very large problem sizes (# edges=>128,000)
but hogs a lot more memory than the other two I mentioned.
If I am right, Grant's problem seems to be about a few hundred edges and a PC
would suffice to solve the problem. Get netflo (it is FORTRAN). It is very fast
for small problems.

Anil


-- 
Sathsangatve nissangatvam	From good company to no company
Nissangatve nirmohatvam		From no company to lack of desire
Nirmohatve  nischaltatvam	From lack of desire to concentration of mind
Nischalatatve jeevanmuktihi	From concentration of mind to death

In article <1992Oct14.232927.24873@m.cs.uiuc.edu> joshi@m.cs.uiuc.edu (Anil Joshi) writes:
>Try getting the code from netlib@ornl.com (I think the address is
>right). There are also a couple of public domain ones, 

I couldn't find this site; this isn't the famous netlib -
research.att.com.  I couldn't find anything quite relevant there.  (If
I was just not looking in the right directory, I'd love to be
corrected.  It's always more useful to be given both the site name,
and some reasonable pointer to a relevant subdirectory.)

>one is called netflo written by Kennington and Helagason at Southern
>Methodist Univ and the other is called Relax III written by
>Bertsekas. I have implemented an Interior point path following version
>(algo by PM Vaidya) which is better than netflo and relax III only
>for very large problem sizes (# edges=>128,000) but hogs a lot more
>memory than the other two I mentioned.

Netflo, by Kennington & Helgason, is available at dimacs.rutgers.edu,
in the directory /pub/netflow/mincost/solver1.

I haven't been able to find a source for Relax III thus far.  Does
anyone have any pointers to it?

-- 
Christopher Browne                |     PGP 2.0 key available
cbbrowne@csi.uottawa.ca           | <-- Finger this account
University of Ottawa              |
Master of System Science Program  |

takriti@engin.umich.edu (samer Takriti) writes:

>In article <1992Oct14.043850.4095@pslu1.psl.wisc.edu> emmel@pslu1.psl.wisc.edu (Grant Emmel) writes:
>>I'm looking for available software (public domain or not) for a
>>non-commercial/non-educational application (I'm helping a friend)
>>that will solve the assignment problem.  That is the general idea.
>>
>>Any help, from theory to software would be helpful.  Post if it is
>>interesting enough, email in any case.
>>Grant Emmel

You can also have a look to the recent book
 J.R. Evans, E. Minieka, "Optimization Algorithms for Networks and
 Graphs", 2nd edition, Marcel Dekker, 1992 (US$ 59.75)

which comes with a diskette with software (including assignment).
This just n case you don't want to code yourself (which is not too
difficult a task, following any Operations Research textbook)

-- 
+---------------------------------------------------------------------------+
| Fabio Schoen                                  e-mail:                     |
| Dipartimento di Scienze della Informazione    schoen@ghost.dsi.unimi.it   |
| via Comelico 39/41 - room    S235             schoen@imiucca.csi.unimi.it |