Algorithm help

[Jim]

The problem:
I have a relation R where
domain set is: dom R = {A,B,C}, and
range set is: ran R = {1,2,3}.
The relations (maplets) are:
{A>1,A>3,B>2,B>3,C>1,C>3}

The following sets would be performed, if we use at most once every element
from each side of the relationship, within each new set. (E.g. {A>2,B>1} is
ok but {A>2,A>3,C>3} is not ok because A and 3 is being twice in the set).

We have:
first {A>1,B>2,C>3}
second {A>1,B>3} (not C3 because 3 is used)
third {A>1,C>3}
fourth {A>3,B>2,C>1}
etc.

I try to capture the sets with the most number of elements (first and fourth
line, that have 3 elements each) and be able to store these somehow, for
further manipulation.

I have spent long time with this problem, and I looked into the association
problem in operations management and in maths, but still, I couldn’t create
any algorithm.

Any help is appreciated.
Jim.

 

[rkm]

The problem:
I have a relation R where
domain set is: dom R = {A,B,C}, and
range set is: ran R = {1,2,3}.
The relations (maplets) are:
{A>1,A>3,B>2,B>3,C>1,C>3}

Can you point out why A>2, B>1, and C>2 are not listed as
relations, even though you use them below. I think I don't
understand the problem because of this.

Rick

 

[John C. Bollinger]

The problem:
I have a relation R where
domain set is: dom R = {A,B,C}, and
range set is: ran R = {1,2,3}.
The relations (maplets) are:
{A>1,A>3,B>2,B>3,C>1,C>3}

The following sets would be performed, if we use at most once every element
from each side of the relationship, within each new set. (E.g. {A>2,B>1} is
ok but {A>2,A>3,C>3} is not ok because A and 3 is being twice in the set).

We have:
first {A>1,B>2,C>3}
second {A>1,B>3} (not C3 because 3 is used)
third {A>1,C>3}
fourth {A>3,B>2,C>1}
etc.

I try to capture the sets with the most number of elements (first and fourth
line, that have 3 elements each) and be able to store these somehow, for
further manipulation.

I have spent long time with this problem, and I looked into the association
problem in operations management and in maths, but still, I couldn’t create
any algorithm.

The brute force way is to generate all the possible sets and retain only
the largest ones. If I've figured it correctly, this can be either
O(N^D) or O(N^R), where N is the number of relations, D is the size of
the domain, and R is the size of the range; which complexity applies
depends on the algorithm: whether you choose relations for the sets
based on their left-hand or right-hand sides. To do this you will need
to classify relations based on their left-hand sides, right-hand sides,
or both, depending on the details of the algorithm.

No, its not elegant, but you have already spent a lot of fruitless time
on this so if the brute force approach works adequately then use it and
go on.


John Bollinger
(e-mail address removed)

 

[Jos A. Horsmeier]

The problem:
I have a relation R where
domain set is: dom R = {A,B,C}, and
range set is: ran R = {1,2,3}.
The relations (maplets) are:
{A>1,A>3,B>2,B>3,C>1,C>3}

The following sets would be performed, if we use at most once every element
from each side of the relationship, within each new set. (E.g. {A>2,B>1} is
ok but {A>2,A>3,C>3} is not ok because A and 3 is being twice in the set).

We have:
first {A>1,B>2,C>3}
second {A>1,B>3} (not C3 because 3 is used)
third {A>1,C>3}
fourth {A>3,B>2,C>1}
etc.

I try to capture the sets with the most number of elements (first and fourth
line, that have 3 elements each) and be able to store these somehow, for
further manipulation.
Any help is appreciated.

Google up the 'job assignment problem', this is exaclty what you want.
Think of it this way -- build a bipartite graph, on the left are the
manager nodes, on the right are the departments. From every node on
the left to every node on the right, an arc exists a_ij. The value
a_ij = 0 when manager i does not manage department j, 1 otherwise.
Every arc ij has an associate cost c_ij. This c_ij = 0 when manager
i is capable of managing department j, otherwise c_ij is a very large
number ('big-M' in operations research lingo).

Every manager i is capable of managing just one single department
and every department wants to be managed by just one single manager,
hence the 'capacaty' of all managers equals one as well as the 'demand'
of all the departments.

The job assignment problem solver minimizes just this:

min sum(i, a_ij*c_ij)
w.r.t. sum(i, a_ij) = 1 and sum(j, a_ij) = 1

If you want as many managers managing as many departments, you
have to introduce an 'artificial' manager and en 'artificial'
department to your model. The cost for the artificial manager
managing real departments should be set to 'big-M', similar to
the costs of real managers managing the artificial department.
The artificial manager can manage the artificial department
at costs zero.

kind regards,

Jos (sorry, no Java code here)

 

[Jim]

Thank you for the help guys, Jim

 

[Jos A. Horsmeier]

Google up the 'job assignment problem', this is exaclty what you want.

I gave it some more thoughts and came to the conclusion that a regular
job assignment solver is a bit of an overkill here, especially if you
look at the problem size. Your problem resembles the '8 Queens' problem
a bit, with an additional constraint, i.e. 'Queens' (read: managers)
are not allowed to be placed everywhere on the board (read: cannot be
assigned to every job).

This all boils down to the following recursive back-tracking thingy:

public class Assign {

private static final int M= 3;

private static int[][] relation= new int[][] {
{ 0, 2 }, // A>1 A>3
{ 1, 2 }, // B>2 B>3
{ 0, 2 } // C>1 C>3
};

private static int[] mgr= new int[M]; // manager i manages job mgr
private static int[] job= new int[M]; // job j is managed by manager job[j]

private static String[] sol= new String[M*M]; // the solution stack
private static int cur= 0; // number of current solutions
private static int len= 0; // length of the solution

private static void assign(int m) { // assign manager m to a job

save(); // save a current solution
if (m >= relation.length) // all managers considered?
return;

for (int i= 0; i < relation[m].length; ++i) // check what this one can do
if (job[relation[m]] == 0) { // this job still free?

mgr[m]= relation[m]+1; // claim this job
job[relation[m]]= m+1; // job claimed by manager
assign(m+1); // assign next manager
mgr[m]= 0; // release this job
job[relation[m]]= 0; // this job still available
}
}

private static void save() { // save a current solution

int p= 0;

for (int i= 0; i < mgr.length; ++i)
if (mgr > 0) ++p;

if (p > len) // found a better solution?
cur= 0; // drop previous solutions

if (p >= len) { // worth keeping this solution?
len= p;
String s= ""; // cook up some rep. for this solution
for (int i=0; i < mgr.length; ++i)
if (mgr > 0)
s+= i+">"+ (mgr-1)+" ";
sol[cur++]= s; // and stack it
}
}

private static void print() { // print all solutions

for (int i= 0; i < cur; ++i)
System.out.println(sol);
}

public static void main(String[] args) {

assign(0);
print();
}
}

kind regards,

Jos