Example of Hungarian algorithm in C++

[Vivek Mishra]

Hi, I am trying to use Hungarian algorithm for solving an assignment problem in my C++ based program using or-tools . Is there an example of using Hungarian algorithm for solving assignment problem with cost function having real values? 

Thanks!

[Laurent Perron]

Short answer: no

Long answer: this is not a competitive implementation of the hungarian algorithm (it is n^4, the better version is is n^3, the complex versions are a bit better).

If your bipartite graph is balanced (same size on both side of the bipartite graph) or close to, you can use the linear assignment solver.

If not, you are better of using the min cost flow algorithm.

Now, these 2 algorithms require integer values. So you will need to scale up your doubles to integral values.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mar. 16 avr. 2019 à 09:31, Vivek Mishra <vkm....@gmail.com> a écrit :

Hi, I am trying to use Hungarian algorithm for solving an assignment problem in my C++ based program using or-tools . Is there an example of using Hungarian algorithm for solving assignment problem with cost function having real values? 

Thanks!

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/b872574b-1e17-400e-8667-47aa4e6f5559%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Vivek Mishra]

Thanks for the prompt reply. My application is not real time so I am not worried about the numerical optimization. Is there any other example which could help me in implementing the Hungarian algorithm?

On Tuesday, April 16, 2019 at 12:38:01 PM UTC-4, Laurent Perron wrote:

Short answer: no

Long answer: this is not a competitive implementation of the hungarian algorithm (it is n^4, the better version is is n^3, the complex versions are a bit better).

If your bipartite graph is balanced (same size on both side of the bipartite graph) or close to, you can use the linear assignment solver.

If not, you are better of using the min cost flow algorithm.

Now, these 2 algorithms require integer values. So you will need to scale up your doubles to integral values.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mar. 16 avr. 2019 à 09:31, Vivek Mishra <vkm....@gmail.com> a écrit :

Hi, I am trying to use Hungarian algorithm for solving an assignment problem in my C++ based program using or-tools . Is there an example of using Hungarian algorithm for solving assignment problem with cost function having real values? 

Thanks!

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.