Help! -Match problem

Hi, group.

I need your help.

I have two tables, one is tblTutor with the names and their available
times, the other one is tblTutee with the names and the available times.
What I need to do is to match every tutee with one tutor. Of course, the
available times of the matched tutee should be a subset of the available
times of the tutors. So, my question is, How should I set the structure of
the tables and how can I get the matched list?

Thank you very much!

Joe

Hi,


Part of the solution is to run a maximum flow algorithm (Ford-Fulkerson,
or using the Simplex Method), part of the solution is to get the "graph"
(from which you can run the max flow algorithm). SQL can be use for that
second part.

I start with the following tables:

tutors tutor period
E alpha
E beta
E gamma
D alpha
D gamma
D delta
C alpha
C beta
C gamma
B alpha
B gamma
A beta
A gamma
A delta
B beta

tutees tutee period
a alpha
a beta
a gamma
b alpha
b gamma
b delta
c alpha
c beta
c gamma
d alpha
d gamma
e beta
e gamma



The SQL Statement (JET):
----------------------------------------
SELECT a.tutor, a.tutee
FROM (SELECT tutors.tutor, tutees.tutee, Count(*) AS Critical
FROM tutors INNER JOIN tutees
ON tutors.period = tutees.period
GROUP BY tutors.tutor, tutees.tutee) AS a
INNER JOIN (SELECT tutees.tutee, COUNT(*) as Required
FROM tutees
GROUP BY tutees.tutee) AS b
ON (a.tutee=b.tutee) AND (a.Critical=b.Required)
GROUP BY a.tutor, a.tutee;
-----------------------------------------

supplies us with the graph of tutors who can accept tutees:

Query41 tutor tutee
A e
B a
B c
B d
B e
C a
C c
C d
C e
D b
D d
E a
E c
E d
E e



based on the assumption that a tutor must be available for ALL the periods
required by a tutee to be able to be the tutor of the tutee.


The graph is just then a matter so define a SOURCE node, with links of
capacity of one toward each tutee-node, then define links from each
tutee-node toward each tutor-node, capacity of one, then, from each tutor
node to the SINK node, each link again with a capacity of 1 (or more, if a
tutor can get more than one tutee). A solution of the max flow FROM the
SOURCE to the SINK is then a possible assignment. If the max flow is less
than the number of tutee, a solution is impossible (for all tutee to get a
tutor). That is where the simplex method becomes more helpful, since it can
"easily" perform post-optimization analysis. I am not aware of a SQL
implementation of the Simplex method (even for very sparse "matrix" ).


To solve through the simplex method, well, I hope you already know the
method, if not, as fast search on Google give me the following site:
http://www-fp.mcs.anl.gov/otc/Guide/...planation.html

To get the graph-to-simplex representation of the max flow problem, start
with Xi the flow in link i, Xi=0 as usual non-negativity constraints on
variables for the Simplex, but also, Xi = Ci, the capacity of the link, as
real constraints of the problem we try to solve. You try to maximize the sum
of the Xi getting out of the source. That's all. Since every pivot is
either -1, either +1, the Simplex will preserve integrality if you start
with an integral solution (ie, you won't get 0.5 student here, or there).

Note also that min{ z } is the same as - max{ -z }, it is just a matter
of sign.



Hoping it may help,
Vanderghast, Access MVP




"Chengfu" wrote in message
...
Hi, group.

I need your help.

I have two tables, one is tblTutor with the names and their available
times, the other one is tblTutee with the names and the available times.
What I need to do is to match every tutee with one tutor. Of course, the
available times of the matched tutee should be a subset of the available
times of the tutors. So, my question is, How should I set the structure of
the tables and how can I get the matched list?

Thank you very much!

Joe

Hi,


There is a nice presentation, and a detailed algo, the shortest augmenting
path, about the max flow problem at
http://study.haifa.ac.il/~dshaposh/readme1.html


Vanderghast, Access MVP

Hi,


oops. There is a major constraint I forgot if you use the Simplex:

The sum of Xi entering in a node k must be equal to the sum of Xi
leaving the node k, except for the source node and for the sink node. That
creates one more additional constraint,per tutor and per tutee.



Vanderghast, Access MVP

Hi,


included, the graph that correspond to my data (all flows are from left to
right), as example, if X5=1, that means tutee c is assigned to tutor B



and here are the non-trivial constraints (for the simplex method), assuming
each tutee would get a tutor

Leaving tutee:

a: x1+x2+x3=1
b: x4=1
c: x5+x6+x7=1
d: x8+x9+x10=1
e: x11+x12+x13+x14=1


arriving at a tutor ( based on a capacity of 1 for each link leaving each
tutor node)

A: x11=1
B: x1+x5+x8+x12 =1
C: x2+x6+x13 =1
D: x4+x9=1
E: x3+x7+x10+x14 =1