Optimal way of assigning items throughout "bins"

user_10873155 0
Viewed 252

I was asked to research possible solutions to a problem that is as follows: We have a certain number of "bins" (~50 of them). Every bin has its own capacity. Every bin can only take items from some specific types. Items have the type and their weight (which lowers the bin's capacity after being stored). What I'm aiming to achieve is a situation in which all the items are assigned "evenly" (I will discuss it in a second) over the bins. It might happen though, that bins won't be able of storing all the items in them because sum of the item's weights will be greater than sum of the bins' capacities. In such a situation I want the script to be able of going over the bins' limit.

What I meant by "evenly" is to, when comparing between bins, take percentage of bin's filled space rather than the amount of items stored in each bin. So, even though that bin 1 has only one item and bin 2 has 10 items then we call it evenly, because in both situations bins were filled to 60% of their capacity. This also applies when bins are overfilled.

At first this seemed as a multiple knapsack problem to me, but those custom constraints (and the overfilling aspect) make me think that this might not be the best approach. Is it even possible to find an exact solution to this (or an algorithm) or does it need some approach like using ML and hoping to find somehow-optimal solutions?

@Edit: I was asked to, if possible, add a sample, anonymized data, so I'll do my best to somehow show the problem.

Let's say, that we have a set of bins as follows:

  • A: capacity: 1, types: a, b,
  • B: capacity: 0.5, types: b,
  • C: capacity: 0.5, types: a,
  • D: capacity: 0.75, types: c
  • E: capacity: 0.4, types: a, b, c

The thing is - capacity is always a number between 0 and 1 and there are multiple types of things that can get to a bin: a bin can either take one type of items to it or multiple.

Now, let's say we have some sample set of items:

  • a: weight: 0.1, type: a,
  • b: weight: 0.75, type: b,
  • c: weight: 0.5, type: a,
  • d: weight: 0.1, type: c,
  • e: weight: 0.25, type: a,
  • f: weight: 0.1, type: b

You can easily see that every item has its weight and type (only one per item).

Now, what we want to achieve is to create a set of bin:set_of_items (like, A -> {a, b}) in which the the distribution of items over bins create a situation in which every bin is, possibly, full to the same percentage of it's capacity (so like, every bin would be full to ~60%) but most importantly all items are distributed - even if this means that we will overfill bins.

Few things to notice from that - there are situations in which bins' capacity is really small, however it is almost certain that the granularity of data is such that every bin will hold at least one item. There can be a situation in which sum_of_bins_capacities<sum_of_items_weights and we will have to overfill the bins - that's fine.

It's really hard for me to provide some reasonable dummy data set but I hope this will make a problem a little bit clearer.

algorithm
2 Answers

This is a variant on the Fair subset sum problem. It is NP-complete, and with a large number of bins (let alone type restrictions) you can't even use dynamic programming to solve it.

I would therefore suggest using an approximation algorithm to solve it.

First assign some reasonable cost function per bin. For example:

cost_of_bin = weight * percent_to_capacity * (1 if percent_to_capacity <= 1 else 2)

What this means is that moving an item from a fuller bin to an emptier one will reduce cost. It also means that adding to a bin past capacity is possible, but severely penalized.

You can then try a simple greedy approach. Sort the items from largest to smallest. Add each item to the available bin with lowest cost. Then cycle through the list and attempt to see if you can gain anything by moving it. When nothing wants to move, you've got a solution.

If you want to get better results, you can experiment with something like Simulated Annealing.

You can also play with different cost functions. For example squaring percent_to_capacity will more severely penalize the most full bin, while making it OK for light ones to be lighter. Just make sure that moving an item from a more full bin to a less full one always improves maximum cost.

user_5854110

I have implemented an algorithm based on the Monte Carlo strategy. A cost function seeks to fill the bins as evenly as possible by minimizing a variance defined as the sum of the squared bin costs. The cost of a bin is the difference between its fill-adjusted capacity and the combined weight of its items.

In each iteration, the algorithm selects an item and a bin at random. It then moves the item into the bin if this decreases the cost function, but with a small probability also if it increases. That helps avoid getting stuck in local minima. In this way, the algorithm roams the solution space in the general direction of a minimum. It is up to the user to decide when enough is enough and time to stop.

The algorithm is in C++ but is fairly C-ish to make it easier to port. The core algorithm is not extensive. A large part of the code is print statements for tracing. I post the code and its output as it stands. The best solution came after 315 iterations, and another almost 100.000 iterations did not change that.

Code:

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <random>

void binitem() {

    const int N = 100000;   // number of iterations in simulation
    const int TL = 100; // trace limit. Tracing stops at TL but "winners" are always printed.
                        // TL=0 (no trace), TL=N (trace all).
        
    const int SEED = 31; // Seed to the random number generator (change for another random sequence)

    const double fairness_capacity = 0.6; // (60%) The evenness of the bins.
    const double another_chance = 0.1; // (10%) The acceptance chance of a rejected move

    using BinID = int;
    using ItemID = int;

    enum class TypeID {a,b,c};

    struct Item {
        std::string symbol;
        double weight;
        TypeID type;
    };
    std::vector<Item> items = { // item definitions
        {"a",   0.1,    TypeID::a},
        {"b",   0.75,   TypeID::b},
        {"c",   0.5,    TypeID::a},
        {"d",   0.1,    TypeID::c},
        {"e",   0.25,   TypeID::a},
        {"f",   0.1,    TypeID::b}
    };
    const int ITEMS = static_cast<ItemID>(items.size());

    struct Bin {
        std::string symbol;
        double capacity;
        HashSet<TypeID> allowed_types;
    };
    std::vector<Bin> bins = {   // bin definitions
        {"A",   1.0,    {TypeID::a, TypeID::b}}, 
        {"B",   0.5,    {TypeID::b}}, 
        {"C",   0.5,    {TypeID::a}}, 
        {"D",   0.75,   {TypeID::c}},
        {"E",   0.4,    {TypeID::a, TypeID::b, TypeID::c}}
    };
    const int BINS = static_cast<BinID>(bins.size());

    struct ItemState {
        BinID is_in_bin = -1; // this item is in this bin (-1 means no bin)
    };
    std::vector<ItemState> itemStates(ITEMS);

    struct BinState {
        std::unordered_set<ItemID> items_in_bin; // items in this bin
        double cost = 0.0;  // bin cost
    };
    std::vector<BinState> binStates(BINS);

        // cost of a bin (squared difference between fairness adjusted capacity and total weight of items)
    auto square_cost_of_bin = [&](BinID binID) { 
            double cost = fairness_capacity * bins[binID].capacity; // adjusted capacity
            for (int itemID : binStates[binID].items_in_bin) { 
                cost -= items[itemID].weight; // minus weight of all items
            }
            return cost * cost; // squared
    };          

    auto square_cost_of_all_bins = [&]() { // sum up costs of all bins
        double sum = 0.0;
        for (BinID binID = 0; binID<BINS; ++binID) sum += binStates[binID].cost;
        return sum;
    };

    for (BinID binID = 0; binID<BINS; ++binID) {     // initialize bin costs
        binStates[binID].cost = square_cost_of_bin(binID);
    }

    auto print_bins = [&] (int i) {
        for (BinID binID = 0; binID<BINS; ++binID) {
            std::string s = "";
            for (ItemID itemID : binStates[binID].items_in_bin) {
                s += items[itemID].symbol + ",";
            }
            if (s.empty()) s = "-"; else s.pop_back();

            if (i>=0) std::cout << i;
            std::cout << ": *** Bin=" << bins[binID].symbol << 
                " holds items=[" << s << "] (bin cost=" << binStates[binID].cost << ")" << std::endl;
        }
    };

    std::mt19937 rng(SEED); // Mersenne Twister random number generator
    std::uniform_int_distribution<int> rnd_item(0, ITEMS-1);
    std::uniform_int_distribution<int> rnd_bin(0, BINS-1);
    std::uniform_real_distribution<double> rnd_real(0.0, 1.0);

    std::cout << ": *** Binitem - a Monte Carlo solution to an assignment probleM" << std::endl;

    double total_cost = square_cost_of_all_bins();
    std::cout << ": *** Ititial total cost with all bins empty=" << total_cost << std::endl;

    for (ItemID itemID=0; itemID<ITEMS; ++itemID) { // insert all items into bins
        bool ok=false;
        BinID rnd_binID = rnd_bin(rng);
        for (BinID binID=0; binID<BINS; ++binID)  {
            if (bins[rnd_binID].allowed_types.contains(items[itemID].type)) {
                binStates[rnd_binID].items_in_bin.insert(itemID); // add item to bin    
                itemStates[itemID].is_in_bin = rnd_binID;   // mark item as present in bin
                binStates[rnd_binID].cost = square_cost_of_bin(rnd_binID); // update bin cost
                ok=true;
                break;
            }
            rnd_binID = (rnd_binID + 1) % BINS;
        }
        if (!ok) {
            std::cout << ": *** Fatal error: No bin accepts item=" << items[itemID].symbol << std::endl;
            return;
        }
    }

    total_cost = square_cost_of_all_bins();
    std::cout << ": *** Ititial total cost with all items inserted=" << total_cost << std::endl;
    print_bins(-1);

    for (int i=0; i<N; ++i) {

        if (i==TL) std::cout << ": *** Tracing ends." << std::endl;

        const ItemID rnd_itemID = rnd_item(rng); // get a random item
        const BinID rnd_binID = rnd_bin(rng);   // and try it out with a random bin

        double new_total_cost = total_cost;

        const bool allowed = bins[rnd_binID].allowed_types.contains(items[rnd_itemID].type);
        if (allowed) { // random item is allowed in random bin

            const BinID old_binID = itemStates[rnd_itemID].is_in_bin;
            if (old_binID != rnd_binID) { // the random item is not in the random bin - move it there

                    // current costs
                const double cur_rnd_bin_cost = binStates[rnd_binID].cost;
                const double cur_old_bin_cost = binStates[old_binID].cost;

                    // make move
                binStates[rnd_binID].items_in_bin.insert(rnd_itemID); // add item to random bin 
                binStates[old_binID].items_in_bin.erase(rnd_itemID);    // remove item from old bin
                itemStates[rnd_itemID].is_in_bin = rnd_binID;   // mark item as present in bin

                    // new costs
                const double new_rnd_bin_cost = square_cost_of_bin(rnd_binID);
                binStates[rnd_binID].cost = new_rnd_bin_cost;
                const double new_old_bin_cost = square_cost_of_bin(old_binID);
                binStates[old_binID].cost = new_old_bin_cost;


                bool accept = new_rnd_bin_cost+new_old_bin_cost <= cur_rnd_bin_cost+cur_old_bin_cost;
                bool second_chance = false;
                if (!accept) {
                    second_chance = (rnd_real(rng) < another_chance); // a second chance
                    accept = second_chance;
                }
                
                if (accept) {
                    new_total_cost = square_cost_of_all_bins();
                } else {
                        // restore move and costs
                    binStates[rnd_binID].items_in_bin.erase(rnd_itemID); // add item to random bin  
                    binStates[old_binID].items_in_bin.insert(rnd_itemID);   // remove it from old bin
                    itemStates[rnd_itemID].is_in_bin = old_binID;   // mark item as present in bin
                    binStates[rnd_binID].cost = cur_rnd_bin_cost;
                    binStates[old_binID].cost = cur_old_bin_cost;
                }

                if (i<TL) {
                    std::cout << i << ": Try move item=" <<  items[rnd_itemID].symbol << 
                    " to bin:" << bins[rnd_binID].symbol << 
                    " : " << ((accept) ? "accepted" : "rejected");
                    if (second_chance) std::cout << " (on second chance)";
                    std::cout << std::endl;
                }

                
            } else { // random item is already in random bin - better luck next time

                if (i<TL) std::cout << i << ": Item=" <<  items[rnd_itemID].symbol << 
                    " already present in bin=" << bins[rnd_binID].symbol << std::endl;

            }

        }  else { // random item is not allowed in random bin - better luck next time

            if (i<TL) std::cout << i << ": Item=" <<  items[rnd_itemID].symbol << 
                " not allowed in bin=" << bins[rnd_binID].symbol << std::endl;
        }

        if (new_total_cost < total_cost) {  // a new winner
            std::cout << i << ": *** New winner:" << std::endl;
            std::cout << i << ": *** New total cost=" << new_total_cost << 
                ", old cost=" << total_cost << std::endl;
            total_cost = new_total_cost;

            print_bins(i);
        }

    }

    std::cout << ": *** Exit after " << N << " iterations." << std::endl;


}   // binitem

Output:

: *** Binitem - a Monte Carlo solution to an assignment probleM
: *** Ititial total cost with all bins empty=0.8001
: *** Ititial total cost with all items inserted=0.6251
: *** Bin=A holds items=[b,c] (bin cost=0.4225)
: *** Bin=B holds items=[f] (bin cost=0.04)
: *** Bin=C holds items=[a] (bin cost=0.04)
: *** Bin=D holds items=[d] (bin cost=0.1225)
: *** Bin=E holds items=[e] (bin cost=0.0001)
0: Try move item=e to bin:C : rejected
1: Item=a not allowed in bin=D
2: Try move item=a to bin:A : rejected
3: Try move item=e to bin:C : rejected
4: Try move item=b to bin:E : rejected
5: Item=d not allowed in bin=A
6: Try move item=f to bin:E : rejected
7: Item=f not allowed in bin=D
8: Try move item=e to bin:C : rejected
9: Item=e not allowed in bin=B
10: Item=b not allowed in bin=D
11: Item=d not allowed in bin=B
12: Item=a already present in bin=C
13: Item=a not allowed in bin=D
14: Item=d already present in bin=D
15: Item=a not allowed in bin=D
16: Try move item=b to bin:E : accepted (on second chance)
17: Item=f not allowed in bin=C
18: Item=c not allowed in bin=D
19: Item=c not allowed in bin=B
20: Try move item=e to bin:A : accepted
20: *** New winner:
20: *** New total cost=0.4851, old cost=0.6251
20: *** Bin=A holds items=[c,e] (bin cost=0.0225)
20: *** Bin=B holds items=[f] (bin cost=0.04)
20: *** Bin=C holds items=[a] (bin cost=0.04)
20: *** Bin=D holds items=[d] (bin cost=0.1225)
20: *** Bin=E holds items=[b] (bin cost=0.2601)
21: Item=c already present in bin=A
22: Item=e not allowed in bin=B
23: Item=e not allowed in bin=B
24: Item=b not allowed in bin=D
25: Item=d not allowed in bin=B
26: Try move item=a to bin:E : rejected
27: Try move item=a to bin:E : rejected
28: Item=c not allowed in bin=D
29: Try move item=a to bin:A : rejected
30: Item=c already present in bin=A
31: Item=f not allowed in bin=C
32: Item=b not allowed in bin=D
33: Item=a already present in bin=C
34: Item=a not allowed in bin=B
35: Try move item=a to bin:A : rejected
36: Item=e not allowed in bin=B
37: Item=a not allowed in bin=D
38: Item=d not allowed in bin=A
39: Try move item=b to bin:A : rejected
40: Try move item=c to bin:C : rejected
41: Item=c already present in bin=A
42: Try move item=a to bin:A : rejected
43: Try move item=a to bin:A : accepted (on second chance)
44: Try move item=c to bin:C : accepted
45: Item=e already present in bin=A
46: Item=e not allowed in bin=D
47: Item=b not allowed in bin=D
48: Try move item=a to bin:E : rejected
49: Try move item=f to bin:E : rejected
50: Item=b not allowed in bin=D
51: Try move item=a to bin:E : accepted (on second chance)
52: Try move item=c to bin:A : accepted
53: Item=b not allowed in bin=D
54: Item=b already present in bin=E
55: Item=c already present in bin=A
56: Item=a not allowed in bin=D
57: Try move item=c to bin:C : rejected
58: Item=a already present in bin=E
59: Try move item=f to bin:A : rejected
60: Item=d not allowed in bin=B
61: Try move item=f to bin:E : rejected
62: Item=e not allowed in bin=B
63: Item=d already present in bin=D
64: Try move item=b to bin:A : rejected
65: Item=c not allowed in bin=B
66: Item=e already present in bin=A
67: Try move item=e to bin:E : rejected
68: Item=a not allowed in bin=B
69: Item=c already present in bin=A
70: Item=f not allowed in bin=D
71: Item=c already present in bin=A
72: Try move item=c to bin:C : rejected
73: Item=d already present in bin=D
74: Item=a not allowed in bin=B
75: Item=f not allowed in bin=D
76: Item=d not allowed in bin=B
77: Item=f not allowed in bin=C
78: Item=d not allowed in bin=B
79: Try move item=b to bin:B : accepted
80: Try move item=a to bin:C : accepted
81: Item=e not allowed in bin=B
82: Try move item=b to bin:E : accepted
83: Item=b not allowed in bin=C
84: Item=f not allowed in bin=D
85: Item=f not allowed in bin=C
86: Item=a already present in bin=C
87: Item=d not allowed in bin=C
88: Try move item=c to bin:C : rejected
89: Item=b not allowed in bin=D
90: Item=f not allowed in bin=D
91: Try move item=a to bin:A : accepted (on second chance)
92: Item=b already present in bin=E
93: Item=f already present in bin=B
94: Try move item=a to bin:C : accepted
95: Item=e already present in bin=A
96: Item=a not allowed in bin=D
97: Try move item=d to bin:E : rejected
98: Try move item=e to bin:C : accepted
98: *** New winner:
98: *** New total cost=0.4351, old cost=0.4851
98: *** Bin=A holds items=[c] (bin cost=0.01)
98: *** Bin=B holds items=[f] (bin cost=0.04)
98: *** Bin=C holds items=[a,e] (bin cost=0.0025)
98: *** Bin=D holds items=[d] (bin cost=0.1225)
98: *** Bin=E holds items=[b] (bin cost=0.2601)
99: Item=f not allowed in bin=D
: *** Tracing ends.
153: *** New winner:
153: *** New total cost=0.3171, old cost=0.4351
153: *** Bin=A holds items=[b] (bin cost=0.0225)
153: *** Bin=B holds items=[f] (bin cost=0.04)
153: *** Bin=C holds items=[e] (bin cost=0.0025)
153: *** Bin=D holds items=[d] (bin cost=0.1225)
153: *** Bin=E holds items=[a,c] (bin cost=0.1296)
173: *** New winner:
173: *** New total cost=0.2551, old cost=0.3171
173: *** Bin=A holds items=[b] (bin cost=0.0225)
173: *** Bin=B holds items=[f] (bin cost=0.04)
173: *** Bin=C holds items=[e,a] (bin cost=0.0025)
173: *** Bin=D holds items=[d] (bin cost=0.1225)
173: *** Bin=E holds items=[c] (bin cost=0.0676)
315: *** New winner:
315: *** New total cost=0.2371, old cost=0.2551
315: *** Bin=A holds items=[b] (bin cost=0.0225)
315: *** Bin=B holds items=[f] (bin cost=0.04)
315: *** Bin=C holds items=[c] (bin cost=0.04)
315: *** Bin=D holds items=[d] (bin cost=0.1225)
315: *** Bin=E holds items=[a,e] (bin cost=0.0121)
: *** Exit after 100000 iterations.
Admin1
Related