Bin-packing C++ solution using multi-map

Question

The need (context).

Several times a day, we need to migrate a set of digital assets from one system to another. The process uses memory (the assets are held in memory for a short time) and we need to do our best to keep the memory capacity down. Fortunately, we have some flexibility (there is no hard ceiling) but there is a noticeable performance improvement if we keep our migration to about 50Mb of assets at a time.

Each migration consists of about 15,000 digital assets, ranging from a hundred bytes or so, up to well over 50Mb (but very rarely). A typical (std) distribution of our assets has a mean (μ) of 213777.0 and a standard deviation (σ) of 1591525.0 - this isn't very accurate - (there's a slight pull towards the low end and then a few very big assets), but it's good enough.

Each asset has a unique id and, along with some other metadata, we have its size available to us. Although we could use an 'asset' struct, for flexibility sake (and because I am unused to templates), I chose to use a pair<size_t,size_t> to represent each asset - the first being the id, the second being the actual size of the asset. (size_t is suitable for both the id and the asset size). I know structs would be more suitable, and will make the change as suggested below.

Therefore, it seemed reasonable (still does) to use a bin-packing solution (a 1-D knapsack-problem).

The criteria of assessment.

The calculation speed of the bin-packing solution is not very important (we are looking at only 15k assets), and neither is a terribly optimal solution. The primary criterion was ease of understanding, and ease of use. Some of our juniors have never heard of bin-packing, and finding a reasonably easy to read method with few lines is more important than a very generalised, maximally optimal, super-fast solution.

The search.

Wikipedia, StackOverflow, and Google are always the first places to look, of course; and bin-packing is a very well-addressed area.

From these, I found the code by Bastian Rieck on his bin-packing GitHub repo, specifically the max_rest_pq function that uses a priority queue.

While it worked fine, I am not familiar with std::priority_queue, and likewise, it seemed only to store the size of each bin, not the contents of each bin. I chose to use pair size_t/size_t for asset-id/weight - I'm not so good at templates, but structs will probably be used in the deployed solution.

The novelty(?!)

Instead, I chose to replace Bastian's use of a std::priority_queue with a std::multimap, by exploiting its lower_bound() method (The map's key here represents space available, not size of current fill). Likewise, using extract()/insert() instead of pop()/push() found in std::priority_queue.

Why I asked this question.

While I may be an experienced programmer, I am not a good programmer. I'm looking to improve on the solution I wrote.
It seems to work well against than many other (more complex, lengthy) algorithms solutions, but maybe it's no good.

The code

#include <vector>
#include <iostream>
#include <map>
#include <unordered_map>

std::multimap<size_t,std::vector<std::pair<size_t,size_t>>> make_bins(const std::unordered_map<size_t,size_t>& objects, size_t K) {
    std::multimap<size_t,std::vector<std::pair<size_t,size_t>>> bins;
    bins.insert({K,{}});
    for(auto& item: objects) { //ID-Weight
        if (item.second >= K) {
            bins.insert({0,{item}});
        } else {
            auto bin = bins.lower_bound(item.second); // we have a bin that has space.
            if (bin != bins.end()) {
                auto node = bins.extract(bin);
                node.key() = node.key() - item.second;
                node.mapped().push_back(item);
                bins.insert(std::move(node));
            } else {
                bins.insert({K-item.second,{item}});
            }
        }
    }
    return bins;
}


// Test data.. 
int main() {
    
    size_t max_capacity = 500;
    std::vector<size_t> obj = {2,42,2,32,21,32,19,2,4,2,4,5,2,5,6,6,96,37,34,54,80,55,84,20,74,50,56,95,40,93,28,37,17,101,28,82,55,58,42,101,29,54,88,73,4,37,22,25,71,93,99,51,14,95,82,90,99,66,63,58,14,73,7,6,98,63,60,79,60,49,91,58,68,52,6,51,69,82,36,71,7,28,88,42,80,81,42,32,52,93,53,3,20,15,8,211,91,52,38,46,79,60,76,86,22,50,101,70,92,43,27,6,33,19,15,30,99,87,52,59,38,92,71,85,32,76,21,10,82,96,61,30,9,75,39,14,6,31,28,75,61,33,85,42,2,41,43,64,3,68,60,77,39,61,63,38,25,66,93,30,75,71,31,23,67,20,93,2,4,45,51,81,23,25,27,2,17,66,17,32,26,31,35,54,2,5,65,51,31,84,42,36,2,50,46,22,53,50,84,84,65,51,72,54,99,46,90,44,60,2,40,38,80,26,95,2,94,56,66,31,25,18,89,42,59,3,86,50,97,18,58,79,100,32,82,94,66,87,61,32,85,87,48,76,7,24,33,19,64,15,60,10,47,7,44,80,100,72,39,61,17,83,48,100,79,52,20,26,66,50,64,26,44,85,22,68,62,72,9,16,2,35,35,14,15,9,8,33,93,50,21,30,75,51,64,40,27,23,34,83,29,35,58,17,81,7,40,43,62,35,10,121,95,30,92,71,16,16,43,16,76,40,33,6,26,23,68,66,80,92,101,52,11,60,71,18,65,11,42,14,5,49,2,89,80,23,121,5,9,53,58,23,2,10,98,19,29,38,91,57,51,9,40,76,62,96,83,35,96,64,4,46,40,5,28,35,26,57,101,78,63,59,3,68,61,23,61,101,70,76,37,74,46,43,30,66,32,73,22,6,49,33,23,91,111,39,76,98,7,78,72,50,43,92,56,15};

    std::unordered_map<size_t,size_t> u;
    size_t x = 1002;
    for (auto &i : obj) {
        u[x++] = i;
    }
    
    auto bins = make_bins(u,max_capacity); // 69,99
    for (auto& bin: bins) {
        size_t wt = 0;
        std::cout << max_capacity - bin.first << ": [";
        for (auto& i: bin.second) {
            wt += i.second;
            std::cout << '{' << i.first << ',' << i.second << '}';
        }
        std::cout << "]\n";
    }
    return 0;
}

Answer 1

Choice of algorithm

It seems to work better than many (more complex) algorithms, but maybe it's no good?

Wikipedia has a very nice article about the bin packing problem. Your algorithm only processes items in the order they appear in the input, it's therefore one of the possible "online" algorithms. Offline algorithms that can look at the whole input and process it in the optimal order can be better.

Your algorithm is the Best-Fit algorithm: from all the bins that exist and have enough space, you choose the one that has the least space left, thus trying to fill existing bins as fast as possible.

To show that your algorithm doesn't always pack in the best way, just consider the following input:

std::vector<size_t> obj = {100, 300, 200, 400};

Assume that this is also the order they are processed in by make_bins() (the std::unordered_map makes it a bit unpredictable). It then ends up with three bins of sizes 400, 200 and 400. But ideally you would only get two bins with sizes 500 and 500.

The order matters, and your test vector just happens to result in a very good fit. Probably, the (modified) first-fit-decreasing algorithm is better and is still relatively simple to implement.

Also note that your algorithm is an approximation, it is possible to calculate the optimal bin packing, but this is an NP-hard problem, and thus is going to be very slow for large inputs.

Don't create an empty bin at the start

Even though some descriptions of bin packing algorithms tell you to start with creating an empty bin, this is not necessary, as some step of the algorithm will tell you that if no bin exists that a new item can fit in, you have to create a new bin anyway. In your code, you can remove the line that inserts an empty bin.

Create your own struct instead of using std::pair

I am using pair size_t/size_t for weight/object id - I'm not so good at templates.

The problem with std::pair<> is that it makes the code hard to read, and you have to remember the order in which things are stored in the pair. If you can, just create your own struct, like so:

struct object {
    std::size_t id;
    std::size_t size;
};

std::multimap<std::size_t, std::vector<object>> make_bins(...) {
    ...
}

Instead of having an unordered map to hold the input, you can use a std::vector<object>; you don't need the \$O(1)\$ lookup by id.

Consider using auto and creating type aliases

Long type names take long to type and are hard to read. Sometimes you can avoid writing a type by using auto, and in other cases you can create an alias for a type. For example:

using bin_type = std::vector<object>;
using bin_map = std::multimap<std::size_t, bin_type>;

auto make_bins(const std::vector<object>& objects, std::size_t K) {
    bin_map bins;

    for (auto& item: objects) {
         if (item.size >= K) {
             bins.emplace(0, {item});
         } else if (auto bin = bins.lower_bound(item.size); bin != bins.end) {
             auto node = bins.extract(bin);
             node.key() -= item.second();
             node.mapped().push_back(item);
             bins.insert(std::move(node));
         } else {
             bins.emplace(K - item.size, {item});
         }
    }
             
    return bins;
}