Resource Allocation Algorithm (Weights in Containers)

Question

I am currently trying to work through this problem. But I cannot seem to find the solution for this problem.

So here is the premise, there are k number of containers. Each container has a capacity associated with it. You are to place weights in these containers. The weights can have random values. However, the total weight in the container cannot exceed the capacity of the container. Or else the container will break. There could be a situation where the weight does not fit in any of the container. Then, you can rearrange the weights to accommodate the new weight.

Example:

Container 1: [10, 4], Capacity = 20
Container 2: [7, 6], Capacity = 20
Container 3: [10, 6], Capacity = 20

Now lets say we have to add new weight with value 8.

One possible solution is to move the 6 from Container 2 to Container 1. And place the new weight in Container 2.

Container 1: [10, 4, 6], Capacity = 20
Container 2: [7, 8], Capacity = 20
Container 3: [10, 6], Capacity = 20

I would like to reallocate this in an few moves as possible.

Let me know if this does not make sense. I am sure there is an algorithm out there but I just cannot seem to find it.

Thanks.

I thought the "Distribution of Cookies" problem would help but that requires to many moves.

Answer 1

As I noted in the comments, the problem of finding if ANY solution exists is called Bin Packing and is NP-complete. Therefore any solution is either going to sometimes fail to find answers, or will be possibly exponentially slow.

The stated preference is for sometimes failing to find an answer. So I'll make reasonable decisions that result in that.

Note that this is would take me a couple of days for me to implement. Take a shot yourself, but if you want you can email [email protected] and we can discuss a contract. (I already spent too long on it.)

Next, the request for shortest path means a breadth first search. So we'll take a breadth-first search through "the reasonableness of the path". Basically we'll try greedy first strategies, and then cut it off if it takes too long. So we may find the wrong answer (if greedy was wrong), or give up (if it takes too long). But we'll generally do reasonably well.

So what is a reasonable path? Well a good greedy solution to bin packing is always place the heaviest thing first, and place it in the fullest bin you can. That's great for placing a bunch of objects in at once, but it won't help you directly with moving objects.

And therefore we'll prioritize moves that create large holes first. And so our rules for the first things to try become:

1. Always place the heaviest thing we have first.
2. If possible, place it where we leave the container as full as possible.
3. Try moving things to create large spaces before small ones.
4. Deduplicate early.

Figuring this out is going to involve a lot of, "Pick the closest to full bin where I fit," and, "Pick the smallest thing in this bin which lets me fit." And you'd like to do this while looking at a lot of, "We did, X, Y and Z..." and then looking at "...or maybe X, Y and W...".

Luckily I happen to have a perfect data structure for this. https://stackoverflow.com/a/75453554/585411 shows how to have a balanced binary tree, kept in sorted order, which it is easy to clone and try something with while not touching the original tree. There I did it so you can iterate over the old tree. But you can also use it to create a clone and try something out that you may later abandon.

I didn't make that a multi-set (able to add elements multiple times) or add a next_biggest method. A multi-set is doable by adding a count to a node. Now contains can return a count (possibly 0) instead of a boolean. And next_biggest is fairly easy to add.

We need to add a hash function to this for deduplication purposes. We can define this recursively with:

node.hash = some_hash(some_hash(node.value) + some_hash(node.left.hash) + some_hash(node.right.hash))

(insert appropriate default hashes if node.left or node.right is None)

If we store this in the node at creation, then looking it up for deduplication is very fast.

With this if you have many bins and many objects each, you can have the objects stored in sorted order of size, and the bins stored sorted by free space, then bin.hash. And now the idea is to add a new object to a bin as follows

new_bin = old_bin.add(object)
new_bins = old_bins.remove(old_bin).add(new_bin)

And remove similarly with:

new_bin = old_bin.remove(object)
new_bins = old_bins.remove(old_bin).add(new_bin)

And with n objects across m bins this constructs each new state using only O(log(n) + log(m)) new data. And we can easily see if we've been here before.

And now we create partial solutions objects consisting of:

prev_solution (the solution we came from, may be None)
current_state (our data for bins and objects in bins)
creation_id (ascending id for partial solutions)
last_move (object, from_bin, to_bin)
future_move_bins (list of bins in order of largest movable object)
future_bins_idx (which one we last looked at)
priority (what order to look at these in)
moves (how many moves we've actually used)
move_priority (at what priority we started emptying the from_bin)

Partial solutions should compare based on priority and then creation_id. They should hash based on (solution.state.hash, solution.last_move.move_to.hash, future_bins_idx).

There will need to be a method called next_solutions. It will return the next group of future solutions to consider. (These may share

The first partial solution will have prev_solution = None, creation_id=1, last_move=None, and priority = moves = move_priority = 0. The future_move_bins will be a list of bins sorted by biggest movable element descending. And future_move_bins_idx will be 0

When we create a new partial solution, we will have to:

clone old solution into self
self.prev_solution = old solution
self.creation_id = next_creation_id
next_creation_id += 1
set self.last_move
remove object from self.state.from_bin
add object to self.state.to_bin

(fixing future_move_bins left to caller)

self.moves += 1
if the new from_bin matches the previous:
    self.priority = max(self.moves, self.move_priority)
else:
    self.priority += 1
    self.move_priority = self.priority

OK, this is a lot of setup. We're ALMOST there. (Except for the key future_moves business.)

The next thing that we need is the idea of a Priority Queue. Which in Python can be realized with heapq.

And NOW here is the logic for the search:

best_solution_hash_moves = {}
best_space_by_moves = {}
construct initial_solution
queue = []
add initial_solution.next_solutions() to queue
while len(queue) and not_time_to_stop(): # use this to avoid endless searches:
    solution = heapq.heappop(queue)
    # ANSWER HERE?
    if can add target object to solution.state:
        walk prev_solution backwards to get the moves we want
        return reverse of the moves we found.

    if solution.hash() not in best_solution_hash:
        # We have never seen this solution hash
        best_solution_hash[solution.hash()] = solution
    elif solution.moves < best_solution_hash[solution.hash()].moves:
        # This is a better way of finding this state we previously got to!
        # We want to redo that work with higher priority!
        solution.priority = min(solution.priority, best_solution_hash[solution.hash()].priority - 0.01)
        best_solution_hash[solution.hash()] = solution

    if best_solution_hash[solution.hash()] == solution:
        for next_solution in solution.next_solutions():
            # Is this solution particularly promising?
            if solution.moves not in best_space_by_moves or
                   best_space_by_moves[solution.moves] <=
                        space left in solution.last_move.from_bin:
                # Promising, maybe best solution? Let's prioritize it!
                best_space_by_moves[solution.moves] =
                        space left in solution.last_move.from_bin:
                solution.priority = solution.move_priority = solution.moves

            add next_solution to queue
return None # because no solution was found

So the idea is that we take the best looking current solution, consider just a few related solutions, and add them back to the queue. Generally with a higher priority. So if something fairly greedy works, we'll try that fairly quickly. In time we'll get to unpromising moves. If one of those surprises us on the upside, we'll set its priority to moves (thereby making us focus on it), and explore that path more intensely.

So what does next_solutions do? Something like this:

def next_solutions(solution):
    if solution.last_move is None:
        if future_bins is not empty:
            yield result of moving largest movable in future_bins[0] to first bin it can go into (ie enough space)
    else:
        if can do this from solution:
            yield result of moving largest movable...
                in future_bins[bin_idx]...
                    to smallest bin it can go in...
                        ...at least as big as last_move.to_bin
        if can move smaller object from same bin in prev_solution:
            yield that with priority solution.priority+2
        if can move same object to later to_bin in prev_solution:
            yield that with priority solution.priority+2
        if can move object from next bin_idx in prev_solution:
            yield result of moving that with priority solution.priority+1

Note that trying moving small objects first, or moving objects to an emptier bin than needed are possible, but are unlikely to be a good idea. So I penalized that more severely to have the priority queue focus on better ideas. This results in a branching factor of about 2.7.

So if an obvious greedy approach succeeds in less than 7 steps, the queue will likely get to size 1000 or so before you find it. And is likely to find it if you had a couple of suboptimal choices.

Even if a couple of unusual choices need to be made, you'll still get an answer quickly. You might not find the best, but you'll generally find pretty good ones.

Solutions of a dozen moves with a lot of data will require the queue to grow to around 100,000 items, and that should take on the order of 50-500 MB of memory. And that's probably where this approach maxes out.

This all may be faster (by a lot) if the bins are full enough that there aren't a lot of moves to make.