Dealing with costs on bins

[franclin]

Is there a way to specify a cost factor of each bins so that some bins are preferred to others? For instance, going back to the example that you specified, let's say on the 4 bins, we assign as a parameter to the algorithm an array of costs [10,3,30,5].

The 2nd bin has the cheapest cost so it will be assigned items until it is filled then the last bin will be assigned items until it is filled.

Basically, the assignment of items to bins is done via a cost factor.
Thanks in advance

[polo-language]

The algorithms offered so far all follow the practice of opening a new bin when one becomes needed. None of them start out with a list of bins as arguments.

If I read your scenario correctly, the absolute values of the bin weights don't matter, just their relative sizes, so the 3 bin gets filled first, then the 5 bin, then 10, and finally 30 (assuming you knew ahead of time 4 bins would be the right number - the lower bound functions can help with this). What about using First Fit Decreasing to sequentially fill bin at index 0, bin at index 1, etc. and then map the solution to your weighted bins. So here it would be solution[0]' -> 'weight 3 bin', solution[1] -> 'weight 5 bin', and so on.

Alternately, since packed first and packed last don't matter much given that the entire packing is returned all at once, maybe what you want is to sort the array of packed bins (produced by any of the algorithms) from most full to least full and then map to the weighted bins so that the 'cheapest' bin is the most fully utilized.

[franclin]

The algorithms offered so far all follow the practice of opening a new bin when one becomes needed. None of them start out with a list of bins as arguments.

If I read your scenario correctly, the absolute values of the bin weights don't matter, just their relative sizes, so the 3 bin gets filled first, then the 5 bin, then 10, and finally 30 (assuming you knew ahead of time 4 bins would be the right number - the lower bound functions can help with this). What about using First Fit Decreasing to sequentially fill bin at index 0, bin at index 1, etc. and then map the solution to your weighted bins. So here it would be solution[0]' -> 'weight 3 bin', solution[1] -> 'weight 5 bin', and so on.

Alternately, since packed first and packed last don't matter much given that the entire packing is returned all at once, maybe what you want is to sort the array of packed bins (produced by any of the algorithms) from most full to least full and then map to the weighted bins so that the 'cheapest' bin is the most fully utilized.

Thanks a lot for your prompt reply.
Here is my setting:
I have items with their respective sizes that I want to fit in as few bins as possible. Each bin has its own capacity. There is a slight twist in the tail for me. There is a cost associated too fitting in a specific bin. My goal is there twofold:

• Minimize the overall cost of fitting into bins
• Fit into as few bins as possible

Going back to example, it would be something like:
Let’s assume that I want to fit into 5 bins and the cost associated to each is [10,300,500,100,20] and the capacity vector for each is [10,20…]

What I want is to first attempt to fill the cheapest bin then move on the next cheapest until all the items have been assigned a bin. In a way, this would be kind of the minimum weighted matching problem. Can I achieve that your package?

[polo-language]

What you need is a First Fit-like algorithm that fills an ordered array of bins of differing capacities. The ordering (or 'cost') isn't the problem, as outlined in my previous message, but the algorithms here all currently accept a single fixed capacity for all bins.

[polo-language]

There is a new algorithm nextFitVarCap in pack/fit-variable-capacity: It accepts a sequence of capacities, which I believe is the key to enabling your use case. This algorithm is still beta, subject to change, and not yet available in the latest npm package, so clone and build to use.

[filipivaska]

Hello, are there any plans to implement bestFitDecreasing alternative for variable capacity of bins? That would solve exactly the problem I am tackling right now, and it would be much appreciated.
Thank you for a great work on the package!

[polo-language]

It's something I might get to in the future if I have more free capacity (pun intended), but I don't have any current plans to expand these algorithms.