2
$\begingroup$

I am trying to find the minimum combination of absolute values from this matrix.

mat = 
 {{-348, -194, -191, -101, -67, 31},
  {-293, -139, -136, -46, -12, 86},
  {-261, -107, -104, -14, 20, 118},
  {-139, 15, 18, 108, 142, 240},
  {-151, 3, 6, 96, 130, 228},
  {4, 158, 161, 251, 285, 383}}

I want to find a set of 6 elements that have the smallest sum of the absolute values when taking one element per row and per column. So in this case, either {4, 3, 18, 14, 12, 31} or {4, 15, 6, 14, 12, 31}.

Improve this question
$\endgroup$
  • $\begingroup$ What do you mean by minimum combination? At least two non-equal elements? Please define. $\endgroup$ – Mauricio Fernández Aug 1 '17 at 8:03
  • $\begingroup$ If you mean two non-equal elements, try first evaluating eval = Flatten[ Table[{{i1, j1}, {i2, j2}, Abs@mat[[i1, j1]] + Abs@mat[[i2, j2]]}, {i1, 1, n}, {j1, 1, n}, {i2, DeleteCases[Range@n, i1]}, {j2, DeleteCases[Range@n, j1]}], 3]; and then extracting the minimum with min = Extract[eval, First@Position[eval[[;; , 3]], Min@eval[[;; , 3]]]] $\endgroup$ – Mauricio Fernández Aug 1 '17 at 8:10
  • 2
    $\begingroup$ @MauricioLobos He needs 6 numbers chosen such that each row/column is used exactly once, e.g. the numbers at positions {{1, 2}, {5, 6}, {6, 4}, {4, 5}, {2, 1}, {3, 3}}. There is dim! possibilities and for the matrix he mention there are two with minimal summed absolute value $\endgroup$ – Coolwater Aug 1 '17 at 8:12
  • 1
    $\begingroup$ Same problem: stackoverflow.com/questions/37949485 $\endgroup$ – Coolwater Aug 1 '17 at 8:33
  • $\begingroup$ Hey all, thank you leading me to the hungarian algorithm. That makes so much sense to tackling this problem. My issue is that my mathematica coding skills are terrible. Any hints to this would be very much appreciated. Thank you! $\endgroup$ – gweeish Aug 2 '17 at 6:43

Your Answer

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

Browse other questions tagged or ask your own question.