Combinatorial best match

Question

Say I have a Group data structure which contains a list of Element objects, such that each group has a unique set of elements.:

public class Group
{
  public List<Element> Elements;
}

and say I have a list of populations who require certain elements, in such a way that each population has a unique set of required elements:

public class Population
{
  public List<Element> RequiredElements;
}

I have an unlimited quantity of each defined Group, i.e. they are not consumed by populations.

Say I am looking at a particular Population. I want to find the best possible match of groups such that there is minimum excess elements, and no unmatched elements.

For example: I have a population which needs wood, steel, grain, and coal. The only groups available are {wood, herbs}, {steel, coal, oil}, {grain, steel}, and {herbs, meat}.

The last group - {herbs, meat} isn't required at all by my population so it isn't used. All others are needed, but herbs and oil are not required so it is wasted. Furthermore, steel exists twice in the minimum set, so one lot of steel is also wasted. The best match in this example has a wastage of 3.

So for a few hundred Population objects, I need to find the minimum wastage best match and compute how many elements are wasted.

How do I even begin to solve this? Once I have found a match, counting the wastage is trivial. Finding the match in the first place is hard. I could enumerate all possibilities but with a few thousand populations and many hundreds of groups, it's quite a task. Especially considering this whole thing sits inside each iteration of a simulated annealing algorithm.

I'm wondering whether I can formulate the whole thing as a mixed-integer program and call a solver like GLPK at each iteration.

I hope I have explained the problem correctly. I can clarify anything that's unclear.

---

Here's my binary program, for those of you interested...

x is the decision vector, an element of {0,1}, which says that the population in question does/doesn't receive from group i. There is an entry for each group.

b is the column vector, an element of {0,1}, which says which resources the population in question does/doesn't need. There is an entry for each resource.

A is a matrix, an element of {0,1}, which says what resources are in what groups.

The program is:

Minimise: ((Ax - b)' * 1-vector) + (x' * 1-vector);

Subject to: Ax >= b;

The constraint just says that all required resources must be satisfied. The objective is to minimise all excess and the total number of groups used. (i.e. 0 excess with 1 group used is better than 0 excess with 5 groups used).

Answer 1

You can formulate an integer program for each population P as follows. Use a binary variable x_j to denote whether group j is chosen or not. Let A be a binary matrix, such that A_ij is 1 if and only if item i is present in group j. Then the integer program is:

min E_i,j (x_jA_ij)

s.t. E_j x_jA_ij >= 1 for all i in P.

x_j = 0, 1 for all j.

Note that you can obtain the minimum wastage by subtracting |P| from the optimal solution of the above IP.