How can I consolidate items { a_0, .., a_N } into K groups, such that the consolidation process is the least costly?

Question

Let me give you an example of what I mean. Let's say I have N=3 items { A, B, C } and want to consolidate them into K groups (0 < K < N). For example, consolidating them into K=2 groups might produce the result

{ {A, B}, {C} }

I have a function Cost(X, Y) >= 0 that returns the cost of consolidating item X into item Y. For example, if Cost(A, B) = 10 and Cost(B, C) = 15 then producing

{ {A, B}, {C} }

costs 10 and producing

{ {A}, {B, C} }

costs 15.

The cost function is not commutative (It's not always true that Cost(X, Y) = Cost(Y, X)).

What I want to do is find an algorithm for the least costly consolidation into K groups.

For example, let's say the costs are

Cost(A, B) = 12
Cost(B, A) = 4
Cost(A, C) = 5
Cost(C, A) = 11
Cost(B, C) = 3
Cost(C, B) = 20

and I want to consolidate into K=1 groups. The least costly would be

B -> C
A -> C

at a cost of 8.

I'm trying to figure out a generalization of how to determine this.

How I think it should start out is to order all the costs:

Cost(B, C) = 3
Cost(B, A) = 4
Cost(A, C) = 5
Cost(C, A) = 11
Cost(A, B) = 12
Cost(C, B) = 20

The item in the above list will always be a one of the moves in the consolidation process:

B -> C

Now, what I suspect needs to happen is iterate through the rest of the list and see if each consolidation.

The next item in the list is B -> A. Since I already moved B to C, skip over this one.

The next item is A -> C. Since A hasn't yet been consolidated into a group, this is a valid consolidation.

Now we're done since we have K=1 groups, { {A, B, C} }.

I'm wondering how to write this algorithm.

To be more concrete, here's a C# setup:

using System;
using System.Collections.Generic;
using System.Linq;

public class Widget
{
    public int Distance { get; set; }
    public int Weight { get; set; } 

    public static int Cost(Widget w1, Widget w2)
    {
        // returns the cost of consolidating w1 into w2
        return Math.Abs(w1.Distance - w2.Distance) * w1.Weight; 
    }
}

public class Program
{
    public static void Main()
    {
        var widgets = new List<Widget>() 
        {

            new Widget() { Distance = 10, Weight = 1 },
            new Widget() { Distance = 20, Weight = 1 },
            new Widget() { Distance = 30, Weight = 1 },
        };

        var tuples = from x in widgets
                     from y in widgets
                     where !x.Equals(y)
                     select Tuple.Create(x,y);

        var ordered = from t in tuples
                      orderby Widget.Cost(t.Item1, t.Item2)
                      select t;

        int K = 2;
        int sum = 0; 

        // ... What to do here??? 

        Console.WriteLine(sum); // should write 10

    }
}

FYI, this isn't a homework problem or anything. I'm doing it for fun.

Why you have not considered B->A and considered A->C? Reason is not clear. please elaborate. — Prakhar Asthana, Aug 01 '16 at 20:18
@PrakharAsthana That cost would be `9`, which is greater than the cost of `B -> C, A -> C`. — Ms. Corlib, Aug 01 '16 at 20:22
What I meant was after selecting B->C "Why you have not considered B->A and considered A->C?" As if you would have selected B->A the total cost would have been 7. — Prakhar Asthana, Aug 01 '16 at 20:24
Once B is has been "consolidated" into C, it cannot be consolidated anywhere else. Sorry, Is should've made that clear in my original post. — Ms. Corlib, Aug 01 '16 at 20:28
The search term you may be looking for is [*graph traversal*](https://en.wikipedia.org/wiki/Graph_traversal), specifically with a weighted directed graph. There are many graph traversal algorithms, most popular of which are [depth first](https://en.wikipedia.org/wiki/Depth-first_search) and [breadth first](https://en.wikipedia.org/wiki/Breadth-first_search) brute force searches, and the smarter [A*](https://en.wikipedia.org/wiki/A*_search_algorithm). You may have to do some tweaking to allow for the non-commutativity. — RoadieRich, Aug 01 '16 at 20:47
Related: https://stackoverflow.com/questions/38680868/algorithm-for-consolidating-n-items-into-k — Peter Duniho, Aug 01 '16 at 21:41

Daniel · Answer 1 · 2016-08-02T03:32:18.400

You can build a graph (tree) of possibilities, where each edge represents an application of the consolidation function over a set of elements and each node stores the elements left to be consolidated.

For example, you have {A, B, C} and Cost(A, B) = 10, Cost(C) = 15, Cost(A,B,C) = 30.

You can build a tree like this:

        {A,B,C}
     10 /    \ 30
      {C}    { }
   15 /        
    { }

When you build the tree, you can just consider the empty nodes as leaves of it and then you can make a pre-order transversal, computing the cost at each level, and when you get to a terminal, you see if its a better option than what you have seen before (just initialize a global variable "best" with very high value before the transversal, and when you get to a terminal, you do best = min(best, cost) )

score 0 · Answer 2 · answered Aug 02 '16 at 03:50

I'm posting this as an answer because it's technically an answer, but it's intended less as something to implement and more as a warning not to try to prove NP-hardness.

Interpret the consolidation costs as a weighted complete directed graph. We're looking for the lightest set of N - K arcs such that (i) each vertex is the tail of at most one arc belonging to the set (ii) ignoring direction, the set contains no cycle. Condition (i) defines a matroid, and condition (ii) defines a matroid. We obtain new matroids by declaring the sets with more than N - K elements to be dependent (truncation), then apply a polynomial-time algorithm for the matroid intersection problem.

How can I consolidate items { a_0, .., a_N } into K groups, such that the consolidation process is the least costly?

2 Answers2