(NOT homework, don't worry)

We have a number payments of which we don't know the exact value.

And the number of payments which fit into a given disjoint set of ranges together with the percentage of the total value of payments, that payments from this range provide.

How can we compute the bounds on the total sum of payments?

For instance say that we know:

there are 4 payments in the range 0 <= x < 5

and 2 payments in the range 5 <= x < 20

and 2 payments in the range 20 <= x < 100

and that the payments in the range 0 <= x < 5 provide 10.7% of the total

payments in the range 5 <= x < 20 provide 27.7% of the total

and payments in the range 20 <= x < 100 provide 61.6% of the total

I think it should be clear we don't actually care about the value of specific payments, only their average within the range so that we can reason about the total value of payments in a given range, so that we would have:

0 <= X < 20

10 <= Y < 40

40 <= Z < 200

and that X = 0.107(X+Y+Z), Y = 0.277(X+Y+Z), Z = 0.616(X+Y+Z)

and we want to compute the upper and lower bounds of X+Y+Z.

It seems to me that the 3 equalities define a plane like:

(1/0.107 - 3)X + (1/0.277 - 3)Y + (1/0.616 - 3)Z = 0

and so we can find the upper/lower bounds of the total by intersecting the plane with the box defined by the inequalities, and at each interesting point (the lines intersecting the box) compute the total value and find the min/max of those to get the upper and lower bounds.

This would extend to any number of ranges in increasing dimensions, my only issue now is actually going about implementing this.

**0**

# compute bounds on total value (intersecting plane with box in N dimensions)

Started by luca-deltodesco, Jan 31 2012 08:50 AM

2 replies to this topic

Sponsor:

###
#2
Members - Reputation: **1792**

Posted 31 January 2012 - 10:06 AM

Looks like this can be solved as an linear program, since the constraints and the function to optimize are both linear, and you are (I assume) modelling the average payments X, Y, Z as arbitrary scalars (and not as integers, or fixed-point rationals).

Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!