CODEWITHSUNDEEP
optimizationgraph-theoryhungarian-algorithmassignment-problem
os12
os12

Reputation: 13

What is the optimal solution for minimum cost storage assignment optimisation problem?

I have been trying to find a solution for the following assignment problem:

The problem is to assign the packages to the storage room so as to minimise the total cost.

My thoughts:

Upvotes: 1

Views: 161

Answers (2)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

A Mixed-Integer Programming model can look like:

 min sum((p,s),T[p,s]*x[p,s])
 sum(p, Z[p]*x[p,s]) <= C[s]    ∀s
 sum(s, x[p,s]) = 1             ∀p
 x[p,s] ∈ {0,1}

This can be solved with any MIP solver. These assignment models tend to be fairly easy to solve.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372724

This problem is NP-hard by a reduction from the set partition problem. In that problem, you’re given a set S of positive integers, and the goal is to split it into two sets that have the same sum.

You can reduce that problem to this one as follows. Given a set S, sum up its elements to get their total 2n, which we assume is even. Now create three storage rooms, two of size n and one of size 2n. Call the two rooms of size n the “main rooms,” and the room of size 2n the “overflow room.” For each element of the set S, create an item to store whose size is equal to its value. Finally, assign costs as follows: the cost of placing any item into one of the two main rooms is zero, and the cost of placing any item into the overflow room is 1.

Now, think about the cheapest way to place items. If there is a partition of S into two equal sets, then you can place the items in the main rooms at cost 0 using that partition. Similarly, if you can place the items into the rooms at cost 0, then you must not have put any items into the overflow room, and so you have split the items in a way that perfectly fills the two main rooms - a partition.

Upvotes: 0

Related Questions