4
$\begingroup$

When trying to solve for assignments given a cost matrix, what is the difference between

  1. using Scipy's linear_sum_assignment function (which I think uses the Hungarian method)

  2. describing the LP problem using a objective function with many boolean variables, add in the appropriate constraints and send it to a solver, such as through scipy.optimize.linprog?

Is the later method slower than Hungarian method's O(N^3) but allows for more constraints to be added?

Improve this question
$\endgroup$
3
  • $\begingroup$ The main difference between a mathematical model and a heuristic algorithm to solve a specific problem is more likely to prove optimality rather feasibility. Now, one can decide which one to be selected in order to satisfy needs. $\endgroup$
    – A.Omidi
    Mar 20 at 7:54
  • 4
    $\begingroup$ @A.Omidi the Hungarian method is an exact algorithm $\endgroup$
    – fontanf
    Mar 20 at 8:26
  • $\begingroup$ @fontanf, you are right. What I said was to compare the exact and heuristic methods and it is not specific to Hungarian alg. Thanks for your hint. $\endgroup$
    – A.Omidi
    Mar 20 at 10:32

1 Answer 1

Reset to default
7
$\begingroup$

The main differences probably are that there is a somewhat large overhead you have to pay when solving the AP as a linear program: You have to build an LP model and ship it to a solver. In addition, an LP solver is a generalist. It solves all LP problems and focus in development is to be fast on average on all LPs and also to be fast-ish in the pathological cases.

When using the Hungarian method, you do not build a model, you just pass the cost matrix to a tailored algorithm. You will then use an algorithm developed for that specific problem to solve it. Hence, it will most likely solve it faster since it is a specialist.

So if you want to solve an AP you should probably use the tailored algorithm. If you plan on extending your model to handle other more general constraints as well, you might need the LP after all.

Edit: From a simple test in Python, my assumption is confirmed in this specific setup (which is to the advantage of the Hungarian method, I believe). The set up is as follows:

  1. A size is chosen in $n\in \{5,10,\dots,500\}$
  2. A cost matrix is generated. Each coefficient $c_{ij}$ is generated as a uniformly distributed integer in the range $[250,999]$.
  3. The instance is solved using both linear_sum_assignment and as a linear program. The solution time is measured as wall clock time and only the time spent by linear_sum_assignment and the solve function is timed (not building the LP and not not generating the instance)

For each size, I have generated and solved ten instances, and I report the average time only.

And then there is of course the "but". I am not a ninja in Python and I have used pyomo for modelling the LPs. I believe that pyomo is known to be slow-ish whenbuilding models, hence I have only timed the solver.solve(model) part of the code - not building the model. There is however possibly a hugh overhead cost coming from pyomo translating the model to "gurobian" (I use gurobi as solver).

A plot of the computation time (in seconds) as a function of the instance size is given below, and it is pretty clear, that the Hungarian algorithm implemented in linear_sum_assignment is a lot faster than the pyomo+gurobi approach: enter image description here

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Do you have some benchmark results to support this claim? Intuitively, I would have thought that the Hungarian method would be much slower in practice $\endgroup$
    – fontanf
    Mar 20 at 7:39
  • $\begingroup$ @fontanf I only have anecdotal proof from past experiments. Maybe an LP solver can work faster for repeated solves, where you exploit that the model is already build and basis info is available. But I honestly don't know. $\endgroup$
    – Sune
    Mar 20 at 9:37
  • 1
    $\begingroup$ It might be the case that the Hungarian method is faster for small problems (due to the overhead Sune mentioned for setting up an LP model) while simplex (or dual simplex, or maybe barrier) might be faster for large models because the setup cost is "amortized" better. (I'm just speculating here.) $\endgroup$
    – prubin ♦
    Mar 20 at 15:30
  • 2
    $\begingroup$ The Hungarian algorithm is, of course, O(n^3) for fully dense assignment problems. I don't know if there is a simplex bound explicitly for assignments. Simplex is exponential in the worst case and linear in variables plus constraints (n^2 + 2n here) in practice. But assignments are highly degenerate (n positive basics out of 2n rows). Dual simplex may fare better than primal. Hungarian is all integer for integer costs, whereas a standard simplex code won't be unless it knows to detect that in preprocessing. That may lead to some overhead for linear algebra. Ha, an idea for a class project! $\endgroup$
    – mjsaltzman
    Mar 20 at 17:04
  • 1
    $\begingroup$ Just for the sake of completeness, here's the same with gurobipy instead of Pyomo. On my machine, all LPs (n = 500) are solved in less than a second compared to roughly 4 seconds with Pyomo. $\endgroup$
    – joni
    Mar 21 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.