Pairing Problem

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

arush - 02 Jul 2009 20:41 GMT

I have the following assignment problem for which i have already
formulated an integer linear program. I was wondering if there is a
known algorithm for solving the problem. A reduced version of the
problem is as follows:

I have six balls {s1,s2,s3........s6} and three boxes{Box1,Box2,Box3}.
I have to assign a box to each ball. for example (s1,s3) ---> Box 2,
(s2,s4) ----->Box1 and so on. Pairing these balls has a cost assigned
to it represented by cost(i,j) forall i,j = 1,2,3,4,5,6.

I have to pair up the balls in such a way that i incur the minimum
cost. Is there any know solution for this problem.

Thanks
Arush.

Reply to this Message

Paul Rubin - 02 Jul 2009 22:57 GMT

> I have the following assignment problem for which i have already
> formulated an integer linear program. I was wondering if there is a
[quoted text clipped - 11 lines]
> Thanks
> Arush.

Search for "weighted matching problem". There are indeed known
algorithms. The base case, a bipartite graph, does not apply here, but
there are algorithms (well, at least one for sure) for the nonbipartite
(if that's a word) case.

/Paul

Reply to this Message

arush - 03 Jul 2009 01:45 GMT

> > I have the following assignment problem for which i have already
> > formulated an integer linear program. I was wondering if there is a
[quoted text clipped - 18 lines]
>
> /Paul

Hello Rubin,
I did think of the maximum weight on a regular graph. The problem with
that i suppose is that the maximum weight on a graph may result in
selecting just a subset of nodes. (in my case the six balls
s1,s2,s3,....s6 ) . I need to make sure that every ball is placed in a
box.
Arush.

Reply to this Message

Paul Rubin - 03 Jul 2009 15:45 GMT

>>> I have the following assignment problem for which i have already
>>> formulated an integer linear program. I was wondering if there is a
[quoted text clipped - 22 lines]
> box.
> Arush.

No, I meant what I said: "weighted matching problem". The matching
problem pairs nodes (connected by edges) in a graph so as to maximize
the number of paired nodes (equivalently, the number of selected edges)
without having two or more edges incident on a single node. The
weighted matching problem maximizes the sum of the weights of the
selected edges, rather than the number of selected edges.

Reply to this Message

arush - 05 Jul 2009 22:15 GMT

Hello Rubin,
So the weighted matching problem maximizes the sum of the weights of
the
selected edges, rather than the number of selected edges. Since i want
all the nodes to be selected does that imply that i would look out for
the maximum matching .

Reply to this Message

Paul Rubin - 06 Jul 2009 13:22 GMT

> Hello Rubin,
> So the weighted matching problem maximizes the sum of the weights of
> the
> selected edges, rather than the number of selected edges. Since i want
> all the nodes to be selected does that imply that i would look out for
> the maximum matching .

Assuming all your weights are positive. (Doesn't work with negative
weights.)

Reply to this Message

Math Forum / Mathematics / Operations Research / July 2009

Pairing Problem