Hi
@i_nth, thanks for having a look at this. You've probably seen that there have been clarifications and additions to the rule set to address issues that emerged. I'll try to summarize the problem and rules as I understand them. I visualize the problem statement like this: Suppose we have a "lot" of shoes of various sizes. As expected, each unit of shoes is a "pair". The lot size is some multiple of 18 pairs, and between 18 to 144 pairs, inclusive (I've ignored the lot size limit for testing purposes). The number of pairs of shoes of any given size is always some multiple of 3 pairs. For convenience, the shoes are arranged in order of their size, from a minimum of size 2.5 to a maximum of 12 in size increments of 0.5 (so we have a total of 20 shoe sizes).
We wish to organize the lot of shoes into bins of manageable size (i.e., quantity), so each bin is ideally filled to capacity with 12 pairs of shoes subject to certain rules. For any group of "n" pairs of shoes of one size, INT(n/12), gives the number of bins that can be readily filled completely with shoes of that size, which will require a total of 12*INT(n/12) pairs. And n-12*INT(n/12), or n(mod 12) tells us the residuals of that size. Due to the constraints above, the residuals (which I often refer to as "partials") for each shoe size will be either 0, 3, 6, or 9 pairs.
I have imagined the rule set as consisting of three phases.
Phase 1:
Determine INT(n/12) and n(mod 12) for each size, and assign each full set of 12 pairs to a bin, homogeneous in that shoe size. Any residuals form the set of partials of various sizes that will be examined in the next phases.
Phase 2:
Search the partials beginning at the left (smallest shoe size available). The first available partial (we'll call p1) is committed to a new bin. Then we need 12-p1 to fill the current bin. Begin the search again from the left, and without subdividing any partial quantity, find the next partial to commit to the current bin, p2, such that p2<=(12-p1). At this point, we need 12-p1-p2 to fill the current bin. Repeat the search algorithm to find p3 if necessary, and then repeat the algorithm again to find p4 if necessary. The two critical rules here are that searches always begin at the left and proceed to the right (small-to-large size) and that partials are not to be subdivided.
These two constraints lead to non-optimal solutions if minimizing the number of bins were the objective. The problem with the two constraints is that it can lead to certain partials becoming "trapped" or committed to a bin for which there are no complementary components...that is, there are no more partials available that can be added to the bin. Depending on the magnitude of the partials and their distribution across shoe sizes, the same set of partials could produce different results, with one distribution efficiently filling all bins, while a different distribution might produce several incomplete bins with trapped partials. This observation led to the introduction of some clean-up rules that I've dubbed Phase 3.
Phase 3:
In Phase 3, any partials in incomplete bins from Phase 2 are reinstated for consideration, and then attempts are made to form full sets of 12 following a different set of rules. Phase 3 abolishes the left-to-right search constraint, and instead looks for any combinations of reinstated partials that can be combined in any order without subdividing to form complete bins of 12. After exhausting those possibilities, any remaining partials can be subdivided and recombined to form complete bins of 12.
In the original problem statement, subdividing partials was not permitted, so I have guessed that the preference is to not subdivide the partials if at all possible. So I would augment the Phase 3 rule set to reflect that there are two objectives: 1) minimize the number of partials that need to be subdivided while forming complete bins of 12, and 2) minimize the number of sets of subdivided partials in incomplete bins. This last objective may not be clear, so an example may help:
Suppose partials available are 9-9-9-6. It would be preferred to subdivide just one partial (the 6) into 3-3 and use those components entirely to form complements for two of the 9's, which leaves just one non-subdivided partial of 9 in an incomplete bin. Another option would be to split one partial (a 9) into 6-3 and use those components entirely to form complements for the 6 and a 9, leaving just one non-subdivided partial of 9 in an incomplete bin. Another non-preferred option would be to split one partial (a 9) into 3-3-3 and use two of those components to form complements for two of the 9's, leaving a residual 3 (from the subdivided 9) and the original 6...this isn't preferred because the components of the subdivided 9 are not entirely assigned as complements. I'm not sure which of the first two options would be preferred. I think the logic in my formulas should produce the first one, but I'm not sure if that would happen consistently.
******
In the first table below, I've summarized the results of my most recent post, which is a 16 bin (not 17) solution formed according to these rules. I've added some horizontal dividing lines in the table to illustrate where the different phases occur. Phase I quickly allocates the first five bins. Then Phase II leads to the formation of eight more bins consisting of non-subdivided partials but of heterogeneous shoe sizes. If you follow the progression in the table, you'll see evidence of the smallest shoe size being committed and then the next available complement being added (in a new search conducted from left-to-right...i.e., size 2.5 to size 12). I'll call attention to box 13. You'll see at that point, that the next available partial was a 9 in size 8, but there were no other partials of 3 available, so the partial of 9 in size 8 became trapped in an incomplete bin. In Phase III, the trapped and uncommitted partials are reexamined and recombined in whole in any combination (so the partial of 9 in size 8 became part of the set considered in Phase III). In the example here, it was not possible to recombine any of partials to form a set of 12 without subdividing, so subdivision was considered next, with the objective to minimize the number of subdivided partials. Since partials available were a 9-9-9-6, the algorithm subdivided just one partial (the 6) into 3-3 to form complements for two of the 9's. If partials available were a 9-9-9-9-6, then it would be better to split a 9 into 3-3-3 to form complements for the other 9's, and the original 6 would be left. In the particular case shown in the table, two complete bins are formed and one incomplete bin of 9 remains in Phase III.
In your solution (also a 16 bin solution) shown in the second table below, there are seven splits of partials, which is probably not ideal, although
@Bala216 is the real authority on this and could weigh in on the importance of that consideration (I've shown the split, or subdivided, partials in bold red font at the top of the tables). I am very curious about how you approached this. Is your solution arrived at through a VBA optimization routine that you could post? I'm wondering if there might be some way to modify the algorithm and constraints to reflect this rather complex set of constraints and decision rules?
