patternMinor
Algorithm for choosing unique options with least overall cost
Viewed 0 times
uniqueoverallwithoptionsalgorithmforleastcostchoosing
Problem
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:
For the above data, the following costs are generated:
/---------------+---------------+---------------+------------+--------\
| Destination 1 | Destination 2 | Destination 3 | Total Cost | Valid? |
+---------------+--
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? |
+---------------+--
Solution
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).
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).
Context
StackExchange Computer Science Q#73799, answer score: 4
Revisions (0)
No revisions yet.