The problem about “some persons not be assigned” and “the value of slack”

[wangshui123]

Hello, I recently ran your program to solve my own project. I used the simplest example: 3 objects and 2 persons. The following problems will occur, so I would like to ask you, thank you!

Question 1: There will always be a problem that some persons not be assigned.( I have followed what you said: the slack benefit is lower than all other arc benefits), so how can I solve it? I want to force every person to be assigned!!

Question 2: As mentioned in the first article of the reference paper you provided, one of the conditions for the optimal assignment is : the slack<1/m , but in your program the slack is 10 , why? I can not understand it .

Thank you very much!!!

[Azmisov]

Hi, I'll take a look tomorrow to see what might be the problem.

As for question 2, the algorithm starts with a "large" slack/epsilon; once a stable assignment is found there, the slack is decreased and it goes again. It repeats until the conditions in Definition 1 are met. It should have adjusted from 10, so not sure what might be wrong at the moment.

[wangshui123]

ok，thank you! I really admire your code work and I am looking forward to getting the answer to question one，thank you!!

[wangshui123]

And in your code, b = arcs[i * n + j] - slack
Does this mean "slack "is "epsilon" （"epsilon" in Definition 1 in first article of the reference paper 2a）
thank you !!

[Azmisov]

Long work day so didn't get time. In mean time, you could try removing NDEBUG and set V to true. Just to make sure the input is valid. What is the arc matrix you are using for the 3x2 case? I'll try to find time tomorrow to find look at my old test code

Slack I believe is synonymous with epsilon if I recall correctly.

[Azmisov]

@wangshui123 I updated the repo with a better demo. I think maybe the short example pseudo-code may have led you astray. Please check the readme and try the new demo. Let me know if it is still not working for you.

Second thing I found was that setting slack_benefit to MIN_FLT was not always working. Seems it would get into an infinite loop somehow. I think in the code I do slack - arc in some places, and that wouldn't compute correctly if you used the minimum float. So I think better to use a smallish value like -1e-10 instead.

I perused through the paper again, and I'm pretty sure the artificial objects aren't actually necessary for the code to run. I think maybe it would be nice in the future to have an option to disable, or at least control how many artificial objects are used. I added a note about that in the readme.

Lastly, I was incorrect in saying slack/epsilon is scaled with each iteration. I think an alternative version of the algorithm does some epsilon scaling, but the one I implemented does not. I think this one is supposed to be faster anyways. This one we hold epsilon/slack constant, and then increment/decrement the prices (for objects) and profits (for persons). The epsilon is the amount we increment/decrement by I believe, and 10 was a constant that Bertsekas used in his code. Unfortunately its been a while since I worked on the project, so I can't really recall all the mathematical details.