I have an assignment problem – say, I need to put a bunch of coloured balls into a bunch of bins – with the following constraints: - Each bin has a capacity
- Some bins cannot accept particular balls
So far, so good – binary min-cost-flow would do; but now I would like to - keep same-coloured balls together as much as possible – I don't really care whether that means minimizing the max number of colors per bin across all bins, or minimizing the sum of the squares of all colour cardinalities (both have pros and cons in my application; whatever is easiest will do.)
Bonus points for a method that lets me do this over and over, given bins that already contain known sets of coloured balls, while still trying to keep same-coloured balls together as much as possible. I have had some luck with CP but the problems are large enough that I'm looking for other (perhaps more basic) ideas as well. I'm grateful also for any key words I can use to start looking for literature on similar problems.
asked
sebastian_k |

I ended up sidestepping the problem by solving for the number of balls per colour and bin first, and then partitioning balls of the same colour among the bins accordingly.
answered
sebastian_k |