Is the methodology used in "sdRemoveImpossibles" a heuristic or is it derived from an academic publication?

Hello,

I am working on the S-D assignment problem solved using the Lagrangian relaxation method. Matlab provides the assignsd method for this purpose. Within assignsd, the method fusion.internal.assignment.sdRemoveImpossibles is called, which includes the statement:

"Feasible assignment: cost(4,5,6,7,8) - cost(4,1,1,1,1) - cost(1,5,1,1,1) - cost(1,1,6,1,1) - cost(1,1,1,7,1) - cost(1,1,1,1,8) must be less than 0."

I am wondering whether this example equation is used as a heuristic or if it is derived from an academic publication. If it is derived from an academic paper, what is the reference? I could not find any citation for this approach in the reference [1] of the assignsd method documentation.

[1] Deb, S., Yeddanapudi, M., Pattipati, K., and Bar-Shalom, Y. (1997). A generalized SD assignment algorithm for multisensor-multitarget state estimation. IEEE Transactions on Aerospace and Electronic Systems, 33(2), 523-538.

Answer 1

[Prashant Arora]

Hi Said,

This helps in improving the performance of the algorithm by removing sub-optimal solutions from the input cost matrix. I am not sure if this is picked from any paper talking about S-D assignment, but this is commonly used in 2-D assignment algorithms.

If the cost of assignment is greater than the cost of unassignment, then the assignment should not exist in the solution. For example in a 3-D assignment, costMatrix(i,j,k) represents the cost of assigning i-1th, j-1th, k-1th entity from three lists. If that cost if higher than leaving all those entities unassigned (costMatrix(i,1,1) + costMatrix(1,j,1) + costMatrix(1,1,k)), then those entities should never be assigned in the solution. This is because you can always replace that assignment and get a better cost by just leaving them unassigned.

Hope this helps.

Prashant

Answer 2

[John D'Errico]

Note that just because something is found in a paper, does not make it even necessarily good mathematics. The lack of any requirement for referees for many journal articles is deplorable these days. And much crap can get past referees. Sorry, but it does. Even in an IEEE journal. Don't make the mistake of thinking that every paper you read is word handed down from god, written on stone tablets. Except for my own published body of work, which is obviously perfect and cannot be questioned. ;-)

Next, much of what you see in a paper could easily be described as a heuristic. Do you really expect rigorous derivations for every equation from every paper?

In this case however, the line in question is a simple one, just a sum of costs (negative costs are entirely valid). And cost would be surely be additive, assuming each cost is framed in the same set of units, and is equally as important as the rest. So this is just a linear constraint on some set of costs. Of course, that is itself likely an approximation.

So is the equation shown truly exact, a true picture of the system? Again, surely no. It is implicitly based on a model, one that assumes a set of costs, and one that assumes there are no other hidden costs in the system, that assumes additivity., etc. And there are always some ignored or hidden costs in any such model, though they may be of little significance, so they can be safely ignored.