Sort routine? maybe.. not sure

[drag0n_45]

Hey there everyone,
I'm kind of confused what the "proper" forum for this is, but here goes:

I have a series of data in Excel (this isn't nec. an Excel question) that corrosponds with dollars paid over a period of time - ultimately bills paid on a given day of the month. I have about 15 such values. The amount paid ranges anywhere from $15 to $350. My goal is to balance the amount spent in such a way that the same approximate amount is spent in any 14 days within that range (a pay period). Since these are recurring bills, the bill paid on day 1 of the month could be in the same pay period as the bill paid on day 21, but not necessarily, since pay periods rotate.

It would be much easier if the pay period were every x day and y day of the month, as it would make budgeting simpler, and I could just look at a fixed chunk of days. However, since they rotate, that must be taken into account, and that's what makes everything overly complicated.

I suspect that a good place to start is to find the avg $/day, then the deviation of that average from each respective $/day on each day, and use that value to calculate what values should go where to make the balance. However, I know diddly about statistical analysis, and need this figured out faster than I can educate myself.

Ultimately my goal is make budgeting much simpler by not having a chunk of money being taken out of my paycheck in one pay period, being left with nothing, then have too much money next pay period, but having to compensate for the NEXT pay period with that extra.

I can provide values, but I'd much rather a method, as I can then apply it as things change. I don't mind VBA, VB, or C# code, since I'm a programmer and can understand it.

Any ideas....:confused::\

[smUX]

I think you'll find that http://www.vbforums.com/forumdisplay.php?f=20 is the right section of the forum to ask, it's definitely a maths-related question more than a programming one.

[leinad31]

If its real life budgeting then you should start off by categorizing the expenditures; mandatory (health, sustenance), important (bills), nice, useless.

[drag0n_45]

True, but these are all mandatory expenses - I can't afford the useless. :(.

Can an admin please move the post?

[si_the_geek]

Thread moved to 'Maths' forum

[drag0n_45]

Thanks!

[jemidiah]

Since these are recurring bills, the bill paid on day 1 of the month could be in the same pay period as the bill paid on day 21, but not necessarily, since pay periods rotate.

I don't understand how two bills separated by 3 weeks could be in the same 2 week pay period. Perhaps I'm misinterpreting something.

Lemme see if I have the setup right:
1. You have many bills, each needing to be payed monthly, for about the same each month.
2. A month varies in length throughout the year as usual.
3. You get paid every 14 days in a lump sum. Since most months don't divide neatly into 14 day periods, pay day slides around each month.
4. Each bill can be paid at any time in a given month.
5. You would like to ensure that each bill gets paid each month without horribly denting your bank account. So, you'd like to minimize the fluctuations of how much you pay in each 14 day period.

Are these correct?

[drag0n_45]

Jemidiah,
Thanks a lot for going so deeply into this - it's exactly it. There are, of course, certain bills that can't fluctuate (i.e. Rent), but most I can call and ask for a due date change. Thinking about things now whatever routine i use would have to allow for some bills to not be moveable while still factoring them into things.

That's prettymuch the idea - I'm in a pretty rough spot money-wise and am looking to make things as easy to manage as possible. Having a uniform bill setup thing will help me do that.

I feel like this is a fairly simple problem to solve, but I just can seem to put the pieces together. I think it's just because of the fact that all the bills aren't for the same values and there's a lot of variance i.e. $14-$350. I originally tried doing it with a chart, but I couldn't determine how to see the sum of an even chunk of 14 days.

[jemidiah]

I can see two somewhat reasonable ways of doing this. First, take, say, 5 pay periods, and find a way to optimize your bills over those alone. When, say, the 3rd pay period of those 5 comes up, rerun your algorithm and follow the modified results for another 3 pay periods. Repeat until retired. The second keeps you paying the same bills at the same time each month, instead of allowing for fluctuation between months, which makes the problem a lot simpler in some ways.

The second is more approximate, but seems a little more practical. You said you could call and get your bill payment day changed on some of your bills. It still seems like, for instance, if your cell phone bill were due on the last day of each month, you couldn't pay it on the 1st of that month instead--either it would be late, or so early you wouldn't have gotten the bill. So I think there's less freedom there than one might wish, which would mean that monthly changes to your payment schedule wouldn't be very easy to manage. In light of this, a repeating monthly pattern that works pretty well would seem sensible.

To use the second algorithm, first, for each bill, figure out which days it could be paid on in a typical month. E.g.: Cell Phone = {25-31}; Rent = {15}, .... If the day ranges are small, optimizing your configuration could be brute-forced. For instance, if you can only move 10 of the 15 values over a range of only 5 days each, there are only 5^10 = 9765625 possible configurations, which a computer could churn through quickly. However, this number is very sensitive to getting too large too quickly. For each configuration, your goal is to find the variance from average for each 14 day period inside the month. Such periods are {1-14}, {2-15}, {3-16}, ..., {18-31}, {19-1}, {20-2}, ..., {31-13}. Note that periods wrap around, so, for instance, {20-2} = = {20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2}.

So say you have a test configuration of your bill payment schedule--that is, you've picked a single day in each range for each bill and have decided to pay those bills exactly on those days each month. You would want to minimize the amount of fluctuation in each possible pay period from average. You would take each pay period range I've listed, say, {20-2}, figure out how much you pay in that range using your test configuration, and figure out how much that deviates from average. Note that you'd want this to be a positive deviation, so you'd take

deviation = Abs(RangeAmount(Range(i), curTestConfig) - Average)

You'd like to minimize overall deviation, and here you have a couple of options. You can minimize the sum of the individual deviations, or you can minimize some other function. It's common to minimize the sum of the squares of deviations, since this "penalizes" large fluctuations very heavily and damps them out.

So, suppose you're minimizing


Sum(deviation^2, i=1 to UBound(Range))
'Sum deviations over all possible values of Range

Again, if the number of possible solutions is relatively small, you could do this by a brute force check. If not, you would have to use a general-purpose global optimization algorithm. Wikipedia (http://en.wikipedia.org/wiki/Global_optimization#Approaches) lists tons of these. The easiest to implement would be the direct Monte-Carlo sampling. That just means you randomly choose a test configuration, figure out its deviation, and find a configuration with small deviation by repeating this until you're happy, or bored. A genetic algorithm would work as well, though they can be a lot of work to set up. Mating your test configurations could also be tricky; no (good) algorithm springs immediately to mind. The others would likely be too advanced, but I have to admit I'm not familiar with most of them.

[drag0n_45]

Wow, that was a lot of information! Thanks for journeying down that road with me! LOL

It sounds like I have a lot of homework to do - I know nothing about optimizations algorithms, though I do know a fair amount of calculus, so I'm sure I could use them.

Just a note though, it sounded to me like you were assuming that there would be no leeway with the due dates (or at least less than one might think). Thing is though, with most folks I could call them and get them to move the due date, then pro rate the month. Thus, I wouldn't just be restricted to a week-ish long period. Once I moved the due date I would be, but that range could actually be moved.

[jemidiah]

The algorithm I described in-depth keeps a constant payment schedule for each bill each month, so that you pay the electric bill on the 4th of every month, for instance. It just optimizes that type of payment schedule, trying to keep all possible 14 day chunks as even as possible. You could squeeze some more optimization out in a couple of ways--first, trying to optimize over 14 day chunks that actually occur, and second, by allowing some wiggle room in each payment. For instance, even though the electric bill is due on the 4th of every month, you could probably pay it several days in advance, giving you a range. The simpler algorithm wouldn't take advantage of this range.

Whatever optimization strategy you decide on will probably not be too hard to modify. I'd recommend using the algorithm I described above first, and then, if there is still too much deviation, adding in more complex things. You would want to plug in large ranges to the first algorithm--if you can move the electric bill anywhere in the month, give it the range {1-31}.

[drag0n_45]

Jemidiah,
I've been reading over your algorithm and don't quite understand it. I have a pretty good math background, but not a very good pattern analysis background. I tried to read it a few times and still don't quite get it. I think it's just the fact that I've never done math with ranges.

Any advice or starting points?

[jemidiah]

I think a worked example is best here. First, when I say range I mean a set of days in the month. A range could be simple, like the 12th through the 15th, which I wrote as {12-15}. It can be more complicated, like the 25th through the 2nd (wrapping around), which I wrote as {25-2}. It can be the entire month, which can be written many ways. One way is {1-31}. Another is {2-1}.

Say you have three bills: your internet bill (~$50), your rent (~$300; may be unrealistic :P), and your phone bill (~$100). Say you can move your internet bill to any day of the month, so you give it a range of {1-31}. Say rent has to be paid in the same 3 day interval each month, {14-16}. Finally, your phone bill can be moved a bit, but they like it near the first of the month. Give it a range of {25-5}.

Now, pick days in each of those ranges that you'll pay those bills on. I'm going to pick... (12, 14, 3), meaning internet on the 12th, rent on the 14th, and phone on the 3rd. Now, we know that pay periods happen in 14 day chunks. Let's see if we can make every *possible* 14 day chunk require about the same payments. What possible chunks are there? Say you get paid on the 1st and 15th. That gives a range of {1-14} between paychecks. Say you get paid on the 20th and again two weeks later on the... 20+14=34->3rd. This gives a range of {20-2}.

Here, you keep a list of all possible ranges:

{1-14}
{2-15}
{3-16}
{4-17}
...
{11-25}
{12-26}
{13-27}
{14-28}
{15-29}
{16-30}
{17-31}
{18-1}
{19-2}
{20-3}
{21-4}
...
{29-11}
{30-12}
{31-13}


For each range, you figure out how much you'd have to pay using your chosen pay schedule (again, (12th for $50, 14 for $300, 3 for $100)). For this example, it would be...


{1-14} -> $450
{2-15} -> $450
{3-16} -> $450
{4-17} -> $350
... -> $350 each (6 ranges)
{11-25} -> $350
{12-26} -> $350
{13-27} -> $300
{14-28} -> $300
{15-29} -> $0
{16-30} -> $0
{17-31} -> $0
{18-1} -> $0
{19-2} -> $0
{20-3} -> $100
{21-4} -> $100
... -> $100 each (7 ranges)
{29-11} -> $100
{30-12} -> $150
{31-13} -> $150


You'd then find the average amount spent over each possible range. Here, it's $6400 / 31 ranges = ~$206 / range. Now, you calculate the deviation from this ideal average. As I said there are several ways of doing this. A common one is to add the differences "in quadrature". I'll list the differences from ideal first:


{1-14} -> $244
{2-15} -> $244
{3-16} -> $244
{4-17} -> $144
... -> $144 each (6 ranges)
{11-25} -> $144
{12-26} -> $144
{13-27} -> $94
{14-28} -> $94
{15-29} -> -$206
{16-30} -> -$206
{17-31} -> -$206
{18-1} -> -$206
{19-2} -> -$206
{20-3} -> -$106
{21-4} -> -$106
... -> -$106 each (7 ranges)
{29-11} -> -$106
{30-12} -> -$56
{31-13} -> -$56


In quadrature, this is

Sqrt(244^2 + 244^2 + ... + (-56)^2) = Sqrt(713716).

This final number is what you want to make as small as possible. In fact, you can save a tiny bit of time by not taking the square root, since you're just interested in making it small. You can hopefully imagine randomly choosing a date in each of your bills' ranges, and calculating this overall variance. This is actually a valid method--you might get some nice result just by chance. The page I linked gives generic methods to solve this general type of problem--that is, you have some parameters that you can boil down into a single "fitness" number (your variance), and you want to find what combination of parameters gives you the lowest "fitness".

Note: please forgive computational mistakes in the above. I haven't double checked it.

[drag0n_45]

That's great! I'll take a more thorough look this afternoon, but I'm pretty sure taht the example helped a great deal. I think the issue with the link that you posted was the mathematical approach. I'm not used to some of the advanced functions the wiki page used. I think I get it now though. Thanks!
I'll double check when I get home and ask if I have any questions.