[Solved]: Distribution algorithm according to weighted parameters (with a min-max constraint)

Problem Detail: 

I'm trying to solve the following problem related to distribution-

I have a list L of items (I1, I2,....In) sorted in order of importance, I1 being the most important. Each item has multiple tags assigned to it and the combination of these tags can be different on each item, so I1 may have tags T1 and T2, I2 can have tags t2, t3 and t4, and I3 can have tag T1, and so on.

Now, I have to make batches from this list L, with a distribution of items (according to the tags) subject to the following constraints-

Each batch has a fixed size B Each tag has a range of items in the batch distribution, ranging from a minimum to maximum. So, B should contain minimum x1 items with tag t1, x2 items with tag t2, and maximum y1 items of t1, y2 items of t2 and so on. We start picking items from the top of L and keep filling the batch until we reach the final distribution that satisfies the constraints. If, say, L has 300 items, and we have to make a batch size of 50, we can go until any number of items in the list and pick the items to make the desired distribution. Remember that if an item is picked from the list, count of all the tags assigned to it goes up by 1. I was thinking of a solution where in first, I make lists of items corresponding to each specific tag. I pick the minimum desired items for a particular tag from its list. So, I'd pick x1 items with tag t1 from the list of items with tags t1, irrespective of whether the items contain any other tag. This way I'd ensure that the 'minimum' criteria of all the tags are satisfied. But for the max part, each tag will most definitely go overboard. How do I recursively keep replacing items from the batch with the remaining items in L to make the final desired distribution?

Any other solution would be great. Or any existing algorithm that can get me in the right direction to approach this problem.

I know the question is a bit too wordy, and probably a bit confusing, but I'v tried to explain it as well as I can, and of course, the problem might be a lot interesting I suppose.

Asked By : user_2000

Answered By : D.W.

Let me repeat my understanding of the problem (as I understand it), then sketch a candidate solution approach. If I've misunderstood the problem, you might need to revise the question to clarify.

The problem: You have $n$ items, and want to divide them into $n/B$ batches of $B$ items. Presumably, $n$ is a multiple of $B$. Each item has some set of tags (a subset of $\mathcal{T}$, where $\mathcal{T}$ denotes the set of all possible tags). For each batch, we're given a function $f:\mathcal{T}\to \mathbb{N}$; we want to ensure that, for each candidate tag $t \in \mathcal{T}$, there are at least $f(t)$ items in the batch with tag $t$. The question is to identify a valid division into batches, if one exists.

One candidate solution: we can formulate this as an integer linear programming problem. Let $x_{i,j}$ denote a 0/1-valued variable that is $1$ if item $i$ is placed into batch $j$, and 0 otherwise. Now we can write down some constraints on the $x$'s that correspond to the problem description. We get

$$0 \le x_{i,j} \le 1$$

$$\sum_j x_{i,j} = 1$$

$$\sum_i x_{i,j} = B$$

$$\sum_{i \in S_t} x_{i,j} \ge f(t)$$

for all $i,j,t$. Here $S_t$ denotes the set of items with tag $t$. You can now use an off-the-shelf integer linear programming solver to search for a solution to this problem.

If I didn't understand your problem quite right, I hope you see the basic idea of my solution and hopefully you'll be able to come up with the appropriate tweaks to address any misunderstandings I might have had about what problem you were looking to solve.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/15001

 Ask a Question

 Download Related Notes/Documents