0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.StackExchange! I apologize, but I confess I'm feeling overwhelmed with the wall of text. Can I encourage you to edit the question to make it much more concise and structure it to make it easier to read? This might require some thought about how to formulate the problem. I'm particularly confused by the description of the constraints on the batches. Also, it is confusing to mix the requirements with one candidate solution; I encourage you to keep those very separate. This might help us help you with your problem. I do hope this comment is not unwelcome... $\endgroup$ – D.W. Oct 13 '13 at 5:25
  • 1
    $\begingroup$ One more thing that I'm not clear on: are you satisfied with any distribution into batches that meets the requirements, or do you also want to choose an "optimal" distribution? If so, what is the definition of "optimal"? What is the utility function (the measure of "goodness" of a particular distribution) that we are trying to maximize? $\endgroup$ – D.W. Oct 13 '13 at 5:26
  • $\begingroup$ Sorry for the confusing problem statement, I should have done better at this. But you got my question almost entirely. Thanks for putting it out in better words below. $\endgroup$ – user_2000 Oct 16 '13 at 8:08
  • $\begingroup$ An optimal distribution would be the one that is closest to the desired outcome, i.e, the batch should deviate as less as possible from satisfying the minimum-maximum items criteria for each tag. Ideal case - In a batch, we have items that have at least the minimum number of items assigned for each tag, and at most the maximum number of items assigned for that tag. Thanks. $\endgroup$ – user_2000 Oct 16 '13 at 8:08
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer @D.W. sorry for the unclear question. You got most of the question correctly. Just that there is a maximum limit for items with tag t in the batch, apart from having at least f(t) items in the batch with tag t. For each tag, there is min-max range of items of that tag to be present in a batch. Also, can you recommend me any off-the-shelf integer linear programming solver for this? $\endgroup$ – user_2000 Oct 16 '13 at 8:00
  • $\begingroup$ I'm using python and I found 'python-constraint' (labix.org/python-constraint), will look into it. $\endgroup$ – user_2000 Oct 16 '13 at 8:32
  • $\begingroup$ @user_2000, OK, it's easy to modify the above ILP to take into account the maximum limit. GNU lp_solve is one standard open-source integer linear solver that's pretty good. There are bindings for it for many languages. $\endgroup$ – D.W. Oct 18 '13 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.