Allocation problem identification

Question

I have a matrix. I have a list of people who have to occupy n1,n2,n3 etc cells, different number of cells in different rows. I have to place the people in the cells. Occupying the same cell across rows is considered overlap. Overlap has to be minimized.

I have people referring to this variously as an optimization problem, an allocation problem and even linear programming.

I need to first get a consensus on what is this class of problem called.

Second, I need to know what an efficient solution should look like, in terms of the big-o notation or anything else.

Here is an example:

There is a board of 4 x 4 cells. There are many pieces each of one color (R, G, B). Each color peice has to fill a number of columns in each row. A possible example:

      Row1   Row2   Row3   Row4
Red      1      2      3      2
Blue     2      2      0      0
Green    1      0      1      2

That is the input. The input arrangement could be different but it occupies the entire board... no cell is left blank.

The count of same color pieces occupying a COLUMN should be minimized. One possible (bad) arrangement based on the input is this:

    1    2    3    4
1   r    b    b    g
2   r    r    b    b
3   r    r    r    g
4   r    r    g    g

This is bad because it actually maximises the count of colors in the same column. A better arrangement is like this:

    1    2    3    4
1   r    b    b    g
2   b    r    r    b
3   g    r    r    r
4   r    g    g    r

Overlap is unavoidable, but should be minimized, and provably so. I dont know if there is only one best solution or if there could be many solutions. Even if there could be many solutions, we need to come up with just one.

As I think about it more, it looks like a loose version of eight-queens problem. I am getting worried because I keep seeing recursion and back-tracking.

EDIT 1:

I am thinking a relaxed version of sudoku puzzle generation.

Answer 1

You first need to state the constraints for valid solution. As it stands the question is too vague.

Given what you wrote, it definitely is an "optimization" problem. Any problem where you have a set of acceptable solution and are looking for best or good enough one according to some criterion is an "optimization" problem. That does not mean much, there are several types of optimization problems that need different approach to solve.

It also is an "allocation" problem, but that does not help you all that much. In general such problems may not have polynomial solution (some are NP-complete) and usable heuristics will depend on the exact constraints.

"Linear programming" is a way to formulate a class of optimization problems. It probably can't be used in your case, because linear programming requires real variables that can be varied in some interval, but you can only have someone assigned to cell or not, so only boolean variables. It can probably be formulated as "integer linear programming", but that is significantly more difficult. Integer linear programming is NP-hard, but reasonable approximate methods exist.

It might also be possible to formulate your problem as "scheduling" problem and use some algorithm used for that.

Answer 2

It is not obvious how we could associate a given arrangement with a score to know how good/bad it is. Here is one way based on your example to generate a solution, may or may not be optimal.First list colors with max. occurrences at the top. Then, pull items from top-most cell moving downwards and then to the right when a column has ended)

Answer 3

I think that a linear time solution might be possible. This is because your number of colours and the width of the matrix are fixed. It reminds me of both a packing problem and a graph colouring problem (both are NP-Complete).

Consider that the optimum arrangement for any colour looks similar to an identity matrix (where 1 represents that colour and 0 represents one of the others). Then simply arrange in this fashion. For example, place the first red in the first column. Then for each next red, simply place it in the next column (modulo 4). Then repeat this process for the other two colours. This simple rotating arrangement should yield the optimal solution, I believe, as it always minimizes the duplication for each insertion.