Defragmentation with minimum changes

Question

I need to design an algorithm that does a simple defragmentation, but with the "minimum amount of changes" feature. Let's say I have 3 containers with capacity of 10 and following items in them:

Container 1: 2 3 3
Container 2: 4 4
Container 3: 1 5 1 1

All the containers are filled up to 8/10. Now i want to place next item of size 3 - the overall free capacity is 6, but none of the container has free capacity of 3. Although there are multiple possible solutions for doing defragmentation, I need the algorithm, that will find the solution, where item of size 2 from the 1st container will be placed somewhere else, so the new items can be then placed into container 1, since this solution requires only one change (instead of replacing two items from container 3). So the required result is supposed to be:

Container 1: 3 3 3(new item)
Container 2: 4 4 2(moved from Container 1)
Container 3: 1 5 1 1

I did some research already, all I could find was either Knapsack problem, or Buddy algorithm, but i am not sure, whether these are really what I am looking for.

Can anyone of you help me to design this algorithm as simple as possible? I am solving a situation where I will have low amount of large containers and huge amount of items in them, so enumerating all possibilities is not quite optimal.

Thanks a lot!

UPDATE Just to make clear what am I asking - it it no problem to determine whether the situation can be solved by doing one change only. The problem is, how to find the minimum amount of replacements when "one single move" is not possible.

Nope, they are not. But the sizes are given and I cannot modify them on the fly. — Marek Galinski, Dec 07 '15 at 21:36
I can sort the containers however i want. The order of containers is totally unimportant. — Marek Galinski, Dec 07 '15 at 23:31
I'm not 100% sure your example is valid. Your suggested solution is moving `2` from Container 1 to container 2, then placing the `3` in Container 1. Wouldn't moving a single `1` from Container 3 then placing the `3` in Container 3 be "faster"? You're only relocating 1 unit instead of 2. — Mr. Llama, Dec 08 '15 at 18:26
@Mr.Llama, in my case, i do not care whether i move item of size 2 or item of size 1. I still move one item only, that's what counts. — Marek Galinski, Dec 08 '15 at 18:31

mhum · Accepted Answer · 2015-12-08T18:21:45.100

This is not an answer to the question, but it is too long for a comment. The problem as stated here is NP-complete (once we've suitably changed it to a decision problem), reducible from the PARTITION problem.

Let x₁, x₂, ..., x_n be an instance of the PARTITION problem. For the sake of notation, let us take x₁ to be the size of the smallest of the x's and let W be the sum of all the x's. Further, for the sake of simplicity let us assume that W is even.

We construct an instance of the given problem to encode our PARTITION instance as follows. We have three containers of sizes W, W/2-x₁, and x₁. Initially, the first container contains items of sizes x₁, x₂, ..., x_n and the other two are empty. The new item to be inserted is of size W/2. We observe that this new item can be inserted into these containers if and only if the original PARTITION problem has a solution.

EDITED TO ADD (more proof detail)

First, we suppose that we have a solution of the original PARTITION problem, i.e.: a split of the x's into two subsets S₁ and S₂ such that the sum of the x's in each subset are equal to W/2. Suppose that S₁ contains x₁, the smallest element. Then, we can move x₁ into the third container and all the other elements of S₁ into the second container, thus leaving a space of W/2 in the first container for the new item.

Next, suppose that we have some way of inserting the new W/2-sized element into these containers. By inspection, the only way this can happen is by making space for it in the first container; and the only way that can happen is by moving exactly W/2 worth of items out of (and, consequently, leaving exactly W/2 worth of items in) the first container. Clearly, this defines a split of the original set of items into two subsets such that each subset has size W/2.

Now, just because this problem is NP-complete doesn't mean that all is lost. It simply means that if you think you've come up with a solution that solves all instances in polynomial time, then you should probably check your work. The structure of the types of instances you will see (e.g.: "low amount of large containers and huge amount of items in them") may help guide the search for useful heuristics.

Thanks, you might be right this is an NP-complete problem, i have that feeling too. Is there any equation or definition that would prove this is 100% sure an NP-complete problem? Can you prove it anyhow? — Marek Galinski, Dec 08 '15 at 17:18
The proof is sketched out in my answer. I will add one more paragraph to clarify. — mhum, Dec 08 '15 at 18:15

score 0 · Answer 2 · answered Dec 07 '15 at 20:11

0

If these containers are built up from scratch, you could add state to say which one was least filled, and always put the next item there.

If you can remove the size of the containers from within the container to outside the container, this could become simpler.

Just my 2 cents.

answered Dec 07 '15 at 20:11

Aaditya Kalsi

1,039
8
16

But this does not solves the situation that even when placing the new amount into least filled container there always may be som fragmentation, that will not allow new item to be placed anywhere, even though the overall free capacity will be sufficient. Furthermore, it may occur in my use case that item will grow its amount. I am looking for a solution that takes the situation "As-Is" and finds the optimal defragmentation. However, thanks for your effort :) – Marek Galinski Dec 07 '15 at 20:17

Defragmentation with minimum changes

2 Answers2