Improve crate limit enforcement

[JamesBremner]

From a stackoverflow comment:

when theBudget = {20, 6, 20, 20, 20};, and when Alice's payLimit is 35? The output should be 158 (including $6 to Alice for B), but wouldn't this algorithm drop Alice's payment for B when handling crate limits, since B is the lowest amount among Alice's payments?

As predicted:

Pay Limits: Alice 35, Bob none, 
budget: 20 6 20 20 20
=============
Alice is paid 35
(  15 for crate A  20 for crate C  )
Bob is paid 25
(  5 for crate A  20 for crate D  )
Total Distance 155

Optimum is

Alice is paid 26
(  6 for crate B  20 for crate C  )
Bob is paid 40
(  20 for crate A  20 for crate D  )
Total Distance 158

[Zevgon]

The optimum is better than 158

This violates Alice's crate limit of 2. The solution shows her pushing A, B and C

As predicted: Total Distance 155

This solution isn't optimal. The best solution would be:

Alice is paid 26
(  6 for crate B  20 for crate C  )
Bob is paid 40
(  20 for crate A  20 for crate D  )
Total Distance 158

[JamesBremner]

This violates Alice's crate limit of 2.

good point

[JamesBremner]

Looks like a more sophisticated way to handle the crate limit enforcement would lie along the lines of preferentially paying the most efficient employee to push crates that cannot be pushed by anyone else.

[Zevgon]

Looks like a more sophisticated way to handle the crate limit enforcement would lie along the lines of preferentially paying the most efficient employee to push crates that cannot be pushed by anyone else.

I don't think that'll work if theBudget = {20, 4, 20, 20, 20}, since no one should push crate B in that scenario.

[Zevgon]

Seems to work fine with that budget

Pay Limits: Alice 35, Bob none,
budget: 20 4 20 20 20
=============
Alice is paid 35
(  15 for crate A  20 for crate C  )
Bob is paid 25
(  5 for crate A  20 for crate D  )
Total Distance 155

Was this output generated with the current implementation or the more sophisticated way of handling the crate limits? I'd expect it to work with the current implementation (dropping the lowest spend for handling crate limits), but not after implementing the more sophisticated approach (choosing a crate type if no other employees can push it).

[Zevgon]

discovered a much better optimum

That's using a different budget ({20, 20, 20, 20, 20}) from the one we were originally discussing in this thread ({20, 6, 20, 20, 20})

[Zevgon]

I am testing different budgets as suggested by you

That makes sense, I'm just confused by what you meant "better optimum", since the result is expected to be higher when the budgets are higher

all outputs posted from new algorithm

Among these 3 versions of the algorithm, which one is the "new algorithm"

1. Original implementation that violates crate limits
2. New implementation that respects crate limits by dropping the lowest spend and re-running the max flow
3. Sophisticated approach that respects crate limits by choosing crates based on whether there are any other employees who can push them

[JamesBremner]

I apologize for the confusion. I should not have posted results until testing was complete. My bad.

I have posted a wiki page with the current status of the project. ( https://github.com/JamesBremner/so79058180/wiki/Status ) This contains all the information I posted yesterday, but in a, hopefully, more coherent manner.

[JamesBremner]

I have fixed the bug in handling crate labels that made nonsense of the result display.

I can now see that there is a problem with the crate limit enforcement. Sometimes dropping the lowest paid crate gives the optimum result, sometimes dropping the crate with the fewest alternative pushers gives a better result.

Obvious solution would be to try both and select the better. However, I will first try to design an algorithm to select the best without having to try both and then backout the 'wrong' choice. If you have any ideas ...?

[Zevgon]

I apologize for the confusion

No worries at all! Really appreciate your interest and effort on this

try both and select the better

My concern would be that the time complexity would scale out of control. IIUC we'd have to try all possible combinations of dropped crates. For example, let's say we have a different problem setup where Alice can push crates A, B, C, D, E, F, G, H, I, and J with a crate limit of 3. We'd effectively be trying all scenarios where Alice pushes crates (A, B, C), (A, B, D), (A, B, E), ..., (A, C, D), (A, C, E), ... (B, C, D), (B, C, E), etc. That means we're back to factorial time complexity

If you have any ideas

This is exactly where I had originally gotten stuck with the whole max flow approach and given up on it. ChatGPT had suggested splitting each node with crate limits into 2 nodes, but I still couldn't figure out how to make that work

[JamesBremner]

suggested splitting each node with crate limits into 2 nodes

That sort of approach is often fruitful. However, in this case I do not see how it would be useful. The employee nodes ( after splitting ) need to link to crate nodes. Which crate is linked to which split employee? It is the same question, just expressed differently.

[Zevgon]

It is the same question, just expressed differently

Yeah exactly 😖

I have posted a wiki page

The 2nd test case (20 6 20 20 20) doesn't show the optimal solution. Alice should push crates B and C in that example, with a total distance of 158

On a different note, I won't have time to dive much more deeply into this, especially since there's a viable path forward using MILP. But I'll keep an eye out on this thread, would be very interested if there's a solution using this approach, and thanks again for all the effort!

[JamesBremner]

The 2nd test case (20 6 20 20 20) doesn't show the optimal solution. Alice should push crates B and C

Not so. B has a budget of just 6. Paying Alice to push B 'wastes' one of her two crate limit.

[JamesBremner]

We have to choose whether to drop the crate with the most alternative pushers or the lowest budget.

Usually, the best is to drop the lowest budget crate, so as not to waste a high efficiency employee's crate limit. If the budgets of all the crates being pushed by the employee who has exceeded their crate limit are the same, then the crate with the most alternative pushers should be dropped.

[JamesBremner]

All test cases in the wiki now pass.

[JamesBremner]

Please test with the v1.0.0 release https://github.com/JamesBremner/so79058180/releases/tag/v1.0.0

[Zevgon]

Not so. B has a budget of just 6. Paying Alice to push B 'wastes' one of her two crate limit.

Please refer to my earlier comment, which explains the optimum solution for that test case

[JamesBremner]

For budget 20 6 20 20 20

current result:

Pay Limits: Alice 35, Bob none,
budget: 20 6 20 20 20
=============
Alice is paid 35
(  20 for crate C  15 for crate A  )
Bob is paid 25
(  20 for crate D  5 for crate A  )
Total Distance 155

Improved optimization found by @Zevgon

Alice is paid 26
(  6 for crate B  20 for crate C  )
Bob is paid 40
(  20 for crate A  20 for crate D  )
Total Distance 158

This reduces payment to Alice by 9 units ( 'wasting' 27 distance units ) but by dropping A from Alice's assignment allows Bob's payment to be increased by 15 units, gaining 30 units ... enough to offset Alice's loss.

[JamesBremner]

I have returned to yesterday's idea of trying both crate limit enforcement methods and selecting the better ( https://github.com/JamesBremner/so79058180/issues/1#issuecomment-2402635501 )

This works well for the test setup we are using. All the tests in the wiki now pass ( including 20, 6, 20, 20, 20 giving distance of 158 )

However, this will only work for setups where only one employee's crate limit is exceeded.

[Zevgon]

trying both crate limit enforcement methods

Those 2 enforcement methods (dropping crates based on lowest spend and dropping crates based on how many other employees can push the crate) are not exhaustive. For example, in some cases, the optimal solution might be one where the correct crate to drop is neither the lowest spend nor a crate that has the highest number of alternative pushers. So even ignoring the problem of exceeding multiple employees' crate limits, there could still be issues. For a fully correct solution, the only way I can see how to make it work would be to try all possible combinations of crates for all employees, which is the same time complexity as the brute force solution: factorial

[JamesBremner]

To enable testing of larger problems I have added the option to specify the problem by reading a file. The file format is documented here https://github.com/JamesBremner/so79058180/wiki/Input-File-Format