Find the optimal ordering of elements

Question

I have a list of logos (up to 4 color) that need to be printed. Each logo requires a setup time to mix paints needed for that logo. If I can sort the data so that two logos that use the same colors are back to back, then we will not have to mix as many colors saving money and time. Paints have a limited life span once mixed.

I am looking at a dataset like this...

Red | (Other Color)
Red | Black
(Other Color) | Black

It needs to end up in that order. That is the only order that will allow for 1 red to me made and 1 black. I've tried a few things like assigning a value to each common color, but no matter what, I can't seem to get it ordered correctly.

---

I used the following SQL procedure that someone wrote based on the TSP problem. (http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=172154)

Using the following test data I received the correct output

delete from routes
delete from cities
insert into cities values ('Black|Red')
insert into cities values ('Red')
insert into cities values ('Blue')
insert into cities values ('Black')
insert into cities values ('Blue|Red')

-- Numeric Value is Colors not Matching

insert into routes values ('Black|Red', 'Red', 3)
insert into routes values ('Black|Red', 'Black', 3)
insert into routes values ('Red', 'Black', 4)
insert into routes values ('Blue|Red', 'Red', 3)
insert into routes values ('Blue|Red', 'Black', 4)
insert into routes values ('Blue', 'Red', 4)
insert into routes values ('Blue', 'Black|Red', 4)
insert into routes values ('Blue', 'Black', 4)
insert into routes values ('Blue', 'Blue|Red', 3)

exec getTSPRoute 'Black'

Results:
Black->Black|Red->Red->Blue|Red->Blue->Black

The only issue is running back to the original "city" (Black returned for both the start and the end) and I have to select a "start city." If the wrong one is selected I don't end up with the most optimized route.

Answer 1

I suspect a Genetic Algorithm would be good for this. If you have a lot of logos, a brute force solution could take quite a while, and greedy is unlikely to produce good results.

http://en.wikipedia.org/wiki/Genetic_algorithm

Answer 2

For a reasonable amount of logos and colors, an easy way would be a brute-force approach in which you go through all the combinations and increase a counter each time mixing is required. After that, you sort combinations by that counter and choose the one with the lowest value.

Pseudocode

foreach combination
    foreach print
        foreeach color 
            if not previous_print.contains(color)
                cost++

order combination by cost (ascending)

You didn't mention if you are using (or are about to) any kind of tool (spreadsheet, programming language, ...) in which you intended perform this sort.

Edit:

Here's a quick implementation in VB.NET. Note that the code is intentionally left long as to make it easier to read and understand.

Private Sub GoGoGo()
    ' Adds some logos 
    ' This is where you add them from the database or text file or wherever
    Dim logos() =
    {
        New String() {"Black", "Magenta", "Orange"},
        New String() {"Red", "Green", "Blue"},
        New String() {"Orange", "Violet", "Pink"},
        New String() {"Blue", "Yellow", "Pink"}
    }

    ' Used to store the best combination
    Dim minimumPermutation
    Dim minimumCost = Integer.MaxValue

    ' Calculate all permutations of the logos
    Dim permutations = GetPermutations(logos)

    ' For each permutation
    For i As Integer = 0 To permutations.Count() - 1
        Dim permutation = permutations(i)
        Dim cost = 0

        ' For each logo in permutation
        For j As Integer = 0 To permutation.Count() - 1
            Dim logo = permutation(j)

            ' Check whether the previous logo contains one or more colors of this logo
            For Each color In logo
                If (j > 0) Then
                    If Not permutation(j - 1).Contains(color) Then
                        cost += 1
                    End If
                Else
                    cost += 1
                End If
            Next
        Next

        ' Save the best permutation
        If (i = 0 Or cost < minimumCost) Then
            minimumCost = cost
            minimumPermutation = permutation.Clone()
        End If
    Next

    ' Output the best permutation
    For Each logo In minimumPermutation
        Console.Write(logo(0) + " " + logo(1) + " " + logo(2))
    Next
End Sub

Public Shared Iterator Function GetPermutations(Of T)(values As T(), Optional fromInd As Integer = 0) As IEnumerable(Of T())
    If fromInd + 1 = values.Length Then
        Yield values
    Else
        For Each v In GetPermutations(values, fromInd + 1)
            Yield v
        Next

        For i = fromInd + 1 To values.Length - 1
            SwapValues(values, fromInd, i)
            For Each v In GetPermutations(values, fromInd + 1)
                Yield v
            Next
            SwapValues(values, fromInd, i)
        Next
    End If
End Function

Private Shared Sub SwapValues(Of T)(values As T(), pos1 As Integer, pos2 As Integer)
    If pos1 <> pos2 Then
        Dim tmp As T = values(pos1)
        values(pos1) = values(pos2)
        values(pos2) = tmp
    End If
End Sub

Answer 3

It looks like the travelling salesman problem (TSP). Let me explain.

First, consider an example where you have a map with four cities A, B, C and D. (I use 4 in the example but it has nothing to do with the number of colors). You want to find a route between the cities so you (1) visit each city only once and (2) the route is the shortest possible. [D,C,A,B] might be shorter that [B,A,D,C] and you want the shortest one.

Now, instead of the cities you have four logos. You want to find such an ordering of the logos, that yields a minimum cost in terms of color mixing. If you imagine that each of your logos is a point (city), and the distance between the logos is the "cost" of switching between one color set to the other, then you need to find the shortest "route" between the points. Once you have this shortest route, it tells you how you should order the logos. The "distance" between two logos L1 and L2 can be defined, for example, as a number of colors in L2 that are not in L1.

TSP it is a well known algorithmic problem. And it is hard (actually, NP-hard). If your input is small you can find the best solution. In case of 4 logos, you have 24 posible combinations. For 10 logos, you have 3.6 million combinations and for 20 logos you get 2432902008176640000 combinations (how to read that?). So for inputs larger than 10-15 you need to use some heuristic that finds an approximate solution, which I am sure is enough for you.

What I would do is that I would create a graph of costs of color mixing and feed it to some TSP solver

EDIT:

• Clarification. Not each logo is a separate point, but each set of colours in a logo is a point. That is: if you have two logos that have the same set of colours, you consider them as a single point because they will be printed together. Logos with red, blue, black are on point and logos with red, green are another point.
• It's rather Hamiltonian path problem than TSP (you don't need to end with the same color set as at the beginning), but it doesn't change much
• If there might be no matches in your logos, then first split your logos into disjoint groups that have no matches between them and later consider each group separately. If there are no matches between any of your logos, then you cannot do much :)
• Practically, I would use python and maybe networkx library to model your problem as graph, and later I would pass it to some TSP solver. Just format the input and make some other program do all the dirty work.