Algorithm for choosing unique options with least overall cost

Question

Problem And Question

I am looking for pointers for an efficient algorithm for the following problem.

It is hard to explain without some data so first I will provide some example data:

Destination 1:
   Source 1: Cost 26
   Source 2: Cost 32
   Source 3: Cost 98
   Create New Source: Cost 100
Destination 2:
   Source 1: Cost 12
   Source 2: Cost 99
   Source 3: Cost 51
   Create New Source: Cost 88
Destination 3:
   Source 1: Cost 55
   Source 2: Cost 31
   Source 3: Cost 76
   Create New Source: Cost 99

I need to choose one of the sources for each destination, so that each source (excluding 'create new source', which can be used as many times as required) is used zero or one times, and the overall cost is low.

I do not need (although it would be nice) an algorithm that produces the absolute lowest cost, because I imagine this would require brute forcing. Instead, I just need an algorithm that is rather more efficient than blindly using source $n$ for destination $n$.

Example Output And Constraints

The above data was actually chosen completely at random, but the following general rules apply to the data:

• It will be very likely that, excluding the 'Create new source' option, the amount of sources will be equal to the amount of destinations.
• It will be very likely that the cheapest option for destination $n$ will be to use source $n$.
• It will be very likely that the cost of creating a new source will be one of highest costing options.
• The example data above uses 3 sources, therefore there are $(3+1)^{3}=64$ total options, and as such, the solution is brute-forcible. At the time of writing, I am actually currently working with 33 sources and counting, there the brute forcing the $(33+1)^{33}=3.45... × 10^{50}$ options is not feasible.

For the above data, the following costs are generated:

/---------------+---------------+---------------+------------+--------\
| Destination 1 | Destination 2 | Destination 3 | Total Cost | Valid? |
+---------------+---------------+---------------+------------+--------+
| Source 1 (26) | Source 1 (12) | Source 2 (31) |         69 |  FALSE |
| Source 2 (32) | Source 1 (12) | Source 2 (31) |         75 |  FALSE |
| Source 1 (26) | Source 1 (12) | Source 1 (51) |         93 |  FALSE |
| Source 2 (32) | Source 1 (12) | Source 1 (55) |         99 |  FALSE |
| Source 1 (26) | Source 3 (51) | Source 2 (31) |        108 |  TRUE  |
\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/‾\/

Therefore

• Destination 1 should use Source 1.
• Destination 2 should use Source 3.
• Destination 3 should use Source 2.
• In actual fact, blindly using source $n$ for destination $n$ with this data actually has a cost of 201, almost double the best choice, and is ranked 15th of the 24 valid solutions.

Background To The Problem

I am working with a series of playlists, which when combined form one master playlist. Each playlist consists of a title in the format of (Master Playlist - Part $n$) and a list of items. These playlists are stored on a server.

The program I have written locally calculates the new state the master playlist needs to be in, splits it up with rules that are beyond the context of this question, and then starts making API calls to update the state of the playlists on the server accordingly.

The operations that can be done are

• Create a new empty playlist, giving it a name in the process.
• Delete an unwanted playlist, and any items inside.
• Add an item to an existing playlist.
• Remove an item from an existing playlist.
• Re-order an item to a new position in the playlist it is already in.
• Rename a playlist.

In the programs current form, for each local playlist part $n$, it will fetch the server state of playlist part $n$, work out whether it is cheaper to delete+recreate or add+remove, and then proceed accordingly.

This is not efficient because, using the above example, it may be much cheaper for local playlist part 2, to take the server playlist part 3, rename it, and modify it, and for local playlist part 3 to do the same for server playlist part 2.

As I already need to fetch all the playlist parts from the server, I am easily able to calculate the amount of API operations it would take to get each of the server playlists into the state required for each of the local playlists. This results in a cost table like at the top of this question, and leads on to the actual problem above.

Footnote

Sorry if question is too subjective, or if I should have posted this on a different stack exchange site, or if I've gone into a bit too much detail. I'm worried I may have done all three.

Answer 1

This is an instance of the assignment problem. There are polynomial-time algorithms, e.g., the Hungarian algorithm. See also assignment-problem.

The one twist in your problem statement is the "create new source". We can model this in the assignment problem by adding $N$ extra sources, one per destination. The $i$th extra source is connected (only) to the $i$th destination. Thus, "creating" a source for destination $i$ is equivalent to connecting it to the $i$th extra source. In other words, instead of treating it as cost 100 to create a new source for destination 1, just eagerly create a new source for destination 1, and treat it as costing 100 if destination 1 uses that source (and no other destination is allowed to use that source; i.e., the cost is $\infty$ for all other destinations).

Answer 2

Without the creation of additional source, your problem seem very close to an assignment problem. Namely, let $n$ be your number of destination and sources, $x_{ij}$ a $\{0,1\}$ variable that is one if Destination $i$ is assigned to source $j$, and $C(i,j)$ the cost of affecting source $j$ to destination $i$. Then you want to solve $$Min_{x_{ij}} \sum C(i,j) x_{ij} $$ under the constraints $$\sum_{j=1}^n x_{ij}=1$$ $$\sum_{i=1}^n x_{ij}=1$$ $$x_{ij} \in \{0,1\}$$ which can be solved efficiently in Polynomial time by the so-called Hungarian algorithm. The two constraints ensure that one source go to one and only one destination.