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 30 Oct '17, 23:21

sebastian_k's gravatar image

accept rate: 0%

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 31 Oct '17, 20:23

sebastian_k's gravatar image

accept rate: 0%

edited 31 Oct '17, 20:23

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 30 Oct '17, 23:21

Seen: 350 times

Last updated: 31 Oct '17, 20:23

OR-Exchange! Your site for questions, answers, and announcements about operations research.