MATLAB Central Newsreader - Simple Optimization Problem

Simple Optimization Problem

Neal Gordon — Sat, 14 Mar 2009 03:33:01 -0400

OK, here is my question. A simple example: Say you have 4 people who each spend a certain amount.
Bob - $50
Tim - $5
Sal - $95
Jon - $200
Together they spent $350, so thats an average of $87.5/person.
Find a solution to minimize the number of transactions between the people so that everyone has spent the same amount.

example solution
Tim pays Jon $82.5
Bob pays Jon $30
Bob pays Sal $7.5

Thanks.
-Neal

Re: Simple Optimization Problem

ImageAnalyst — Sat, 14 Mar 2009 03:39:34 -0400

On Mar 13, 11:33=A0pm, "Neal Gordon" <gordon....@osu.edu> wrote:
> OK, here is my question. A simple example: Say you have 4 people who each=
spend a certain amount.
> Bob - $50
> Tim - $5
> Sal - $95
> Jon - $200
> Together they spent $350, so thats an average of $87.5/person.
> Find a solution to minimize the number of transactions between the people=
so that everyone has spent the same amount.
>
> example solution
> Tim pays Jon $82.5
> Bob pays Jon $30
> Bob pays Sal $7.5
>
> Thanks.
> -Neal
---------------------------------------------------------------------------=
------------------
I don't understand. If Tim pays $5 total, or even $5 per transaction,
then how can he spend $82.5 which is not a multiple of $5? And in
your example solution, not everybody has paid the same amount. Tim
paid $82.50, Bob paid $37.50, and Jon and Sal didn't pay(spend)
anything. Are you sure you're explaining this correctly?

Re: Simple Optimization Problem

Neal Gordon — Sat, 14 Mar 2009 04:08:01 -0400

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <84a25b13-1e98-4886-bfa2-f1454477e057@l39g2000yqn.googlegroups.com>...
> On Mar 13, 11:33=A0pm, "Neal Gordon" <gordon....@osu.edu> wrote:
> > OK, here is my question. A simple example: Say you have 4 people who each=
> spend a certain amount.
> > Bob - $50
> > Tim - $5
> > Sal - $95
> > Jon - $200
> > Together they spent $350, so thats an average of $87.5/person.
> > Find a solution to minimize the number of transactions between the people=
> so that everyone has spent the same amount.
> >
> > example solution
> > Tim pays Jon $82.5
> > Bob pays Jon $30
> > Bob pays Sal $7.5
> >
> > Thanks.
> > -Neal
> ---------------------------------------------------------------------------=
> ------------------
> I don't understand. If Tim pays $5 total, or even $5 per transaction,
> then how can he spend $82.5 which is not a multiple of $5? And in
> your example solution, not everybody has paid the same amount. Tim
> paid $82.50, Bob paid $37.50, and Jon and Sal didn't pay(spend)
> anything. Are you sure you're explaining this correctly?

Original amount spent:
Bob - $50
Tim - $5
Sal - $95
Jon - $200
Together, as a group, they spent $350 = 50+5+95+200, so thats an average of $87.5/person.

So, to clarify, we would like to find the quickest way for everyone in the group to have spent the same amount overall. Now, I will show the iterations with the current amount spent per person.
--iteration 0--
Bob : $50
Tim : $5
Sal : $95
Jon : $200

--iteration 1--Tim pays Jon $82.5--
Bob : $50
Tim : $5 + $82.5 = $87.5
Sal : $95
Jon : $200 - $82.5 = $117.5

iteration 2--Bob pays Jon $30--
Bob : $50 + $30 = $80
Tim : $87.5
Sal : $95
Jon : $117.5 - $30 = $87.5

iteration 3--Bob pays Sal $7.5--
Bob : $80 + $7.5 = $87.5
Tim : $87.5
Sal : $95 - $7.5 = $87.5
Jon : $87.5

final spending with 3 iterations(transactions):
Bob : $87.5
Tim : $87.5
Sal : $87.5
Jon : $87.5

I hope this helps. This solution is trivial, but I am interested in the solution of 15+ people while trying to achieve less iterations than the "Number of people minus 1", which in this case is 3 obvious iterations.

Re: Simple Optimization Problem

David Vavra — Sun, 06 Mar 2011 18:30:12 -0500

Hi,
I'm solving the exact problem. Did you solve it eventually?

What I plan to do:
- use TORSCHE toolbox for Matlab, which has support for Integer Linear Programming
- define problem using ILP, where I introduce new binary variable which will say who did send money to who - will be used for counting transactions
- set criteria to minimizing number of transactions

Do you have some other suggestions?

David Vavra

"Neal Gordon" <gordon.363@osu.edu> wrote in message <gpfaj1$im7$1@fred.mathworks.com>...
> ImageAnalyst <imageanalyst@mailinator.com> wrote in message <84a25b13-1e98-4886-bfa2-f1454477e057@l39g2000yqn.googlegroups.com>...
> > On Mar 13, 11:33=A0pm, "Neal Gordon" <gordon....@osu.edu> wrote:
> > > OK, here is my question. A simple example: Say you have 4 people who each=
> > spend a certain amount.
> > > Bob - $50
> > > Tim - $5
> > > Sal - $95
> > > Jon - $200
> > > Together they spent $350, so thats an average of $87.5/person.
> > > Find a solution to minimize the number of transactions between the people=
> > so that everyone has spent the same amount.
> > >
> > > example solution
> > > Tim pays Jon $82.5
> > > Bob pays Jon $30
> > > Bob pays Sal $7.5
> > >
> > > Thanks.
> > > -Neal
> > ---------------------------------------------------------------------------=
> > ------------------
> > I don't understand. If Tim pays $5 total, or even $5 per transaction,
> > then how can he spend $82.5 which is not a multiple of $5? And in
> > your example solution, not everybody has paid the same amount. Tim
> > paid $82.50, Bob paid $37.50, and Jon and Sal didn't pay(spend)
> > anything. Are you sure you're explaining this correctly?
>
> Original amount spent:
> Bob - $50
> Tim - $5
> Sal - $95
> Jon - $200
> Together, as a group, they spent $350 = 50+5+95+200, so thats an average of $87.5/person.
>
> So, to clarify, we would like to find the quickest way for everyone in the group to have spent the same amount overall. Now, I will show the iterations with the current amount spent per person.
> --iteration 0--
> Bob : $50
> Tim : $5
> Sal : $95
> Jon : $200
>
> --iteration 1--Tim pays Jon $82.5--
> Bob : $50
> Tim : $5 + $82.5 = $87.5
> Sal : $95
> Jon : $200 - $82.5 = $117.5
>
> iteration 2--Bob pays Jon $30--
> Bob : $50 + $30 = $80
> Tim : $87.5
> Sal : $95
> Jon : $117.5 - $30 = $87.5
>
> iteration 3--Bob pays Sal $7.5--
> Bob : $80 + $7.5 = $87.5
> Tim : $87.5
> Sal : $95 - $7.5 = $87.5
> Jon : $87.5
>
> final spending with 3 iterations(transactions):
> Bob : $87.5
> Tim : $87.5
> Sal : $87.5
> Jon : $87.5
>
> I hope this helps. This solution is trivial, but I am interested in the solution of 15+ people while trying to achieve less iterations than the "Number of people minus 1", which in this case is 3 obvious iterations.