search

ankane / or-tools-ruby

Operations research tools for Ruby
Apache License 2.0
179 stars 25 forks source link

ORTools::LinearSumAssignment not finding solution to a 20 * 16 cost matrix #35

Closed lggg123 closed 2 years ago

lggg123 commented 2 years ago

I have tried the given example of ORTools::LinearSumAssignment in the README section which works for 4 * 4 cost matrix:

costs = [
  [90, 76, 75, 70],
  [35, 85, 55, 65],
  [125, 95, 90, 105],
  [45, 110, 95, 115],
]

Now, I am trying to solve a similar problem for a slightly larger cost matrix which is *20 16 matrix** and the cost matrix is: 

cost_matrix = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0], [4, 0, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

But, solver is returning infeasible status. And, I am not sure if I am doing something wrong, or the ORTools::LinearSumAssignment is not the right solver to solve this type of cost matrix. Could you please shed some lights if I should use any other configuration with ORTools::LinearSumAssignment to solve the above 20 * 16 cost matrix?

Thank you in advance.

ankane commented 2 years ago

Hey @lggg123, for the linear sum assignment solver, the number of tasks and workers must be the same: https://github.com/google/or-tools/issues/2597