Revenue sharing and operations research – part 2

This is a mini-series on how revenue sharing and operations research are linked. You might want to read part 1 on the specific business problem I was solving. In this part, I’ll be telling you about the maths behind the business solution.

But first, I have to tell you about a couple of maths concepts.

Converging from opposite directions

Let’s say someone asked you how tall you are. Instead of giving a straight answer, you decide to give a simple maths puzzle. You say you are at least 6 feet tall. Then you also say you are at most 6 feet tall. So what’s your height? Let’s put those 2 conditions into mathematical form:

  • H >= 6
  • H <= 6

To satisfy those 2 conditions, there’s only 1 answer: You must be 6 feet tall.

It looks elementary, but it will come into play later on. Just keep in mind that an equality can be split into 2 inequalities. This actually reminds me of the squeeze theorem, but I digress.

Reversing the direction of an inequality

The next maths concept is how to reverse the direction of an inequality. For example, we have

x >= 5

This can also be expressed as

-x <= -5 This will also come in handy later on.

System of linear inequalities

My experience in operations research had been confined to course work in an academic semester. Operations research mainly is about maximising or minimising some objective. You are given a series of conditions to fulfill. Then you’re given an objective to maximise or minimise. And you’re to translate those conditions and objective into a mathematical model formulation. Let’s look at an example.

Jake’s mom gave him $15 to buy some sweets (because he did awesomely in a maths test. Parental note: I don’t think this is a good reward, but hey, it’s your kid). But mom told Jake that he cannot buy more than 3 lollipops (although Jake already decided he’s not buying more than 4). There’s this contest where if you submit wrappers from peppermints and lollipops, you win an iPad (I’m totally making this up!). Jake needed just 4 more wrappers, and he didn’t want more than 4 because he wanted to buy more chocolates. Also, Jake had secretly decided to buy at least $10 worth of sweets.

Now, chocolates cost $2 each. Peppermints cost $1 each. And lollipops cost $3 each.

Let C be the number of chocolates bought.
Let P be the number of peppermints bought.
Let L be the number of lollipops bought.

Let the objective be to maximise the number of sweets bought. So in maths form, we typically write it as:
max C + P + L

Let’s formulate the conditions:
2C + P + 3L <= 15 (mom only gave Jake $15) L <= 3 (mom said Jake can't buy more than 3 lollipops) L <= 4 (Jake independently decided he's not buying more than 4) P + L = 4 (Jake just wanted 4 more wrappers) 2C + P + 3L >= 10 (Jake wanted to waste at least $10)

Now, logically speaking the condition for the number of wrappers doesn’t make sense. We could say the number of wrappers for peppermints and lollipops be at least 4, which makes better sense. But this is a hypothetical example. More to the point, it’s my hypothetical example, and I needed an equality condition. So there.

You might also note that there are redundant conditions.
L <= 3 L <= 4 can be represented by just L <= 3 because if it's satisfied, then L is definitely <= 4. This is to show you that in your mathematical formulation, you can get redundant conditions. It's up to you to eliminate them so you work with less conditions. Real life problems are messy, don't you know? Let's clean up the formulation. Objective: max C + P + L 2C + P + 3L <= 15 -2C - P - 3L <= -10 P + L <= 4 -P - L <= -4 L <= 3 I've rearranged the conditions a little for clarity. Note the inequality reversal for the "more than $10" condition. Note the split of the equality to 2 inequalities. Why are we doing this? So we get the general form Ax <= B where A is the coefficient matrix x is the variable vector B is the value vector We need to do the inequality reversal so the "direction" for all the inequalities is the same. Otherwise we cannot have Ax <= B. In this case, A is | 2 1 3 | |-2 -1 -3 | | 0 1 1 | | 0 -1 -1 | | 0 0 1 | x is | C | | P | | L | B is | 15 | |-10 | | 4 | | -4 | | 3 | With this Ax <= B form, we're dealing with matrices and vectors. That means we can use all the mathematical techniques for solving such formulations, such as Gaussian elimination or even Gauss-Jordan elimination. The idea is to solve all of our unknowns at one go.

You might notice that we have more inequalities than unknowns. This means we have multiple solutions.

For example, a possible solution for (C, P, L) is (2, 3, 1). That solution satisfies all the conditions. It doesn’t mean it’s optimal, but it’s a solution. This means solutions exist for the problem (sometimes just knowing this is reassuring…).

The dual

I want you to know that the objective can always be stated in the opposite manner. If the objective is to “maximise X”, it is equivalent to “minimising -X”. This is known as the dual of the problem. For example, maximising profit is equivalent to minimising the negative value of profit. NOTE: Maximising profit is NOT equivalent to minimising cost. Profit and cost are generally not the opposite of each other (they’re different business terms), even if they sound like they are (and sometimes give the same solutions). The mathematical formulation and solution is different for both of them. Know what you’re solving.

This duality property is useful if your program is optimised to solve only minimisation problems. So you just convert a maximisation problem to a minimisation problem, and your program works just fine!

Linearity

And you might also note that the objective and the conditions are all linear, meaning unknowns are up to power of 1 (as opposed to quadratic or cubic). Sometimes you get a non-linear condition, and depending on the situation, you might be able to form linear conditions that are equivalent to that non-linear condition.

For example, CP = 2 (number of chocolates multiply by number of peppermints equal to 2).
This set of conditions might be equivalent:

  • C >= 1
  • P >= 1
  • C <= 2
  • P <= 2
  • C + P = 3

The first 2 conditions are inferred from the fact that C and P cannot be zero. If they are, then CP = 2 is never satisfied. If they’re never zero, then they must be at least 1.

The 3rd and 4th conditions are inferred from the fact that C and P cannot be more than 2. If they are, then the other unknown is fractional. For example, if C is 4, then P must be 1/2. But these are number of items, so they must be integer. Therefore, C and P must be at most 2.

Based on the first 4 conditions, C and P can only take on either 1 or 2 as values. The only combination of permutations that still satisfies the “CP = 2” condition is one unknown must be 1 and the other unknown be 2. Hence the sum of the two unknowns must be equal to 3.

Not all non-linear conditions can be translated into linear conditions. Go ask an operations research professor for more.

Integral conditions

And we come to the worst part. All the unknowns must be integer (you can’t buy 2.37 chocolates. Well, at least not without the candy store owner going crazy). This integral condition makes the problem much harder to solve. If you solve the Ax <= B form, you generally get fractional values for the unknowns. This is the optimum solution, but doesn't satisfy the integral condition. If I remember correctly, you solve Ax <= B as usual. Then you take one of the unknowns and work with the 2 integers that are the floor and ceiling values of that unknown. Then you solve iteratively again, with reduced and reformulated conditions for Py <= Q. For example, if you get C = 2.37, then you split off 2 scenarios with C = 2 and C = 3 as the optimum solutions. Scenario 1 is Objective: max P + L P + 3L <= 11 -P - 3L <= -6 P + L <= 4 -P - L <= -4 L <= 3 Scenario 2 is Objective: max P + L P + 3L <= 9 -P - 3L <= -4 P + L <= 4 -P - L <= -4 L <= 3 Basically, you just substitute C = 2 and C = 3. For each scenario, you continue splitting with the other unknowns. There are 3 unknowns, so there are eventually 8 scenarios (2^3 = 8). It's a binary tree. Well, it's at most 8 scenarios, because you might get lucky and hit an original optimised solution with one or more of the unknowns having an original value that's already an integer (now that's a long sentence...). For each of the scenarios, you either get a solution or you get a contradiction somewhere (meaning it's unsolvable). The contradiction can come from the splitting, because when you substitute a possible value into one of the unknowns, the resulting set of conditions contain a contradiction. For example, out of the set of conditions, you get 2 conditions as follows: x <= 4 -x <= -8 ( meaning x >= 8 )

Since an unknown variable cannot be both (less than or equal to 4) AND be (more than or equal to 8), the scenario becomes unsolvable.

Then you examine all those scenarios with solutions, substitute the solutions to the unknowns, and compare the result. If it’s a maximising problem, you check which scenario gave a solution that’s the largest. If it’s a minimisation problem, you check which scenario gave a solution that’s the smallest. And that particular solution becomes the optimum integral solution.

Let me tell you, you do not want to do this by hand. This is why software is written to handle the Gaussian eliminations and checking all the possible scenarios due to the integral condition. With just 3 unknowns, you’re expected to do 9 Gaussian eliminations (1 for the original, 8 for the branch scenarios), and check through all 8 scenarios. Imagine having hundreds of variables and conditions…

Mathematics and programming in one. Having skills in one but not the other makes writing the software quite difficult. Imagine a mathematician who cannot express his ideas in programming code, or a programmer who cannot understand the maths involved.

Back to the business problem

After that extremely long mathematical discussion, we can now turn back to the original business problem. If you haven’t read part 1, you should do so now, otherwise you’d be lost.

Let R be the total revenue for a content provider for that particular month
Let R1 be the total revenue for ProductA
Let R2 be the total revenue for ProductB
Let R3 be the total revenue for ProductC
(so R1 + R2 + R3 = R)
Let X1 be the revenue share for the telecommunications company for ProductA
Let X2 be the revenue share for the telecommunications company for ProductB
Let X3 be the revenue share for the telecommunications company for ProductC
Let Y1 be the revenue share for the content provider for ProductA
Let Y2 be the revenue share for the content provider for ProductB
Let Y3 be the revenue share for the content provider for ProductC

Let the revenue sharing split for the telecommunications company be 30%
Let the revenue sharing split for the content provider be 70%

The objective is to minimise rounding errors. Actually, there should be no errors, but we can live with a possible solution first. If it’s non-zero, then we panic…

The unknowns in this case are X1, X2, X3, Y1, Y2 and Y3.

Objective: minimise ABS(R – X1 – X2 – X3 – Y1 – Y2 – Y3)
X1 + Y1 = R1
X2 + Y2 = R2
X3 + Y3 = R3
X1 = 0.30 * R1
X2 = 0.30 * R2
X3 = 0.30 * R3
Y1 = 0.70 * R1
Y2 = 0.70 * R2
Y3 = 0.70 * R3

And Xi’s and Yi’s must be integers, for i = 1, 2, 3

And ABS stands for the absolute function.

As you can see, there’s a lot of equal conditions. And it’s a problem with integer conditions. Frankly speaking, I don’t want to program a solution either. Just looking at what I’ve written is already giving me a headache…

I’m glad my ex-colleague said no. *whew* This was too complicated to implement. And the content provider might have more products, so the number of unknowns is unknown (no pun intended).

There’s actually a little bit more to the maths formulation, but I’ll tell you about it in the 3rd part. I had to come up with a solution that made mathematical sense and could be understood by other people. Mostly, the users (that is, “normal” people) must be able to understand the logic behind it.

Leave a comment if you have any questions about the maths involved (or even tell me I’m wrong), and I’ll do my best to answer them.

Absolutes and almost every

Back when I was writing my thesis, I came across this abbreviation: a.e. It took me a while, but I eventually found that it meant almost every. This might have been almost everywhere in measure theory, but I don’t think so. I seem to recall just “almost every”.

Almost every what, you ask?

Well, I was doing research on computer virus behaviour, so I had books from computer security, graph theory, biological viruses, mathematical models (with exponents and ordinary differential equations and such). I think it was in graph theory. An author was talking about a result or theorem and the proof included almost every type of graph, which was good enough.

I thought that was interesting, because I’ve thought of mathematics as absolute. Maybe this was why I suck at statistics… The idea of some event having a probability of happening, instead of just be or be not, shakes my world somewhat. Of course, I’m less shaken now since life isn’t really absolute…

My greatest accomplishment came when I was in the computer lab, and a Masters student was around. She’s from China, and you know those people are wicked clever. She held up a book, looked at me, then walked over to me.

“Do you know what a.e. means?”

AHA! Me, honours student, knew something a Masters student didn’t!

“I think it means almost every.”
“Oh. OHHHH! Thanks!”

I suspect she asked me because she believed my English was better than hers, and not because I was more knowledgeable in whatever topic that book of hers was about. Have you seen programming books translated to Chinese? I can read the words, but that doesn’t mean I know what the hashbrown that meant… She approached me probably (yay statistics) because she believed a.e. stood for something that someone moderately versed in English will know.

Still, it was an accomplishment. I could tell you I went on to brag about it to all my friends, but truth be told, I continued working on my program code… I was in the computer lab for something, you know…

Is there an equation to describe regular polygons?

So a blog reader, Michael Gmirkin, sent me an in-depth email about the possibility of the existence of a super equation that can describe any regular polygon. I wasn’t sure. For reference, you might want to check out these 2 blog posts about the equation for a square: question, answer.

I was going to just ask you here. Then I remembered there’s a Stack Overflow equivalent for maths. So I went there and asked the question. So if you know the answer, you can comment here, or go to the maths StackExchange site and earn yourself some points.

You can assume that the centre of the regular polygon in at the origin (0,0). Researching a little on the topic, I also learnt about the apothem, which is also the shortest distance from the centre to a polygon’s side. The “normal” radius is the distance from the centre to one of the regular polygon’s vertex.

If you trace 2 circles, one with the apothem and one with the radius, you get an inscribed circle and circumscribed circle respectively.

Bezier curve inflection points

Adrian Colomitchi wrote me an email about an article I wrote. It turns out that I was wrong about the inflection point section. I was trying to figure out what Timo meant by “loop tips”, and I figured it could be an inflection point.

So here’s how Adrian describes inflection points:

If you drive or ride a bicycle: inflection points will happen when you switch your direction from left-to-right or vice-versa.
The inflexion points have 0-curvature (and infinite radius)… for an instant you travel straight (because you are switching the direction).
By contrast, the tip points will have maximum curvature.

Here’s how the inflection points should actually look like (screenshots taken from Adrian’s site):

A Bezier curve with no inflection points:
Bezier curve with no inflection points

A Bezier curve with one inflection point:
Bezier curve with one inflection point

A Bezier curve with two inflection points:
Bezier curve with two inflection points

You can find out more about inflection points on a cubic Bezier curve on Adrian’s website.

If you have anything to add about inflection points (or Bezier curves), comment below.

Elevator waiting maths

John Cook wrote an article on where to wait for an elevator. Where do you wait so you walk the minimum distance to the elevator? Read his article for the full explanation and solution. Here’s a pictorial summary of the solution:

Elevator optimum waiting position

The problem was from a paper written by James Handley (and collaborated with others). Basically, you don’t wait at the average position among all the elevators. You wait at the elevator with the median position.

In reality, however, you still have to enter the space where the elevators are. Therefore, the best position with the minimum distance to walk is

to remain at the point of entry, and to not move at all!

That of course, assumes that the elevators had been activated to arrive at your floor. You know, you need to push the button. How do you push that button if you’re 5 metres away? With a long pole? Other people? Telekinesis?

I have a more in-depth discussion on this in the January 2011 issue of Singularity. Go download it and read it. It’s free.

Here’s something to think about. James Handley is a mathematician. What’s he doing in the faculty of medicine? Because he’s helping with epidemiology. If you’re not familiar with the word, “epidemiology” means the study of epidemics. The spread of viruses, rates of infection and the like.

This reminds me of the time when my thesis mentor (back in my university days) suggested I work in the field of epidemiology. Because my thesis dealt with computer virus behaviour. Oh my god, I just looked at my thesis again… oh dear, ordinary differential equations! *closes thesis hurriedly*

Maths, context and culture

I was reading this post by Dan Meyer on pseudocontext in maths problems.

If we invite pseudocontext in our classrooms without condition, it becomes harder and harder to tell the difference between the real and the unreal.

Back when I was young, a lot of maths problems made little sense to me. In those days, the maths syllabus up to primary 6 (at 12 years old, or grade 6 if you’re in America) wasn’t particularly hard. At least to me. I’m not bragging, I’m just saying that the education system made things more difficult by introducing word problems. The epitome of conquering a maths exam paper was solving all the word problems at the end.

Word problems were created to introduce another element into elementary math (to make them difficult?). They added language. Suddenly it was something like:

John, Fred and Ken had $5 total. John bought 10 red marbles and Fred bought 12 blue marbles. If 1 red marble costs $0.10, and 1 blue marble costs $0.15, how many blue marbles can Ken buy if they still want to have $1 left?

Your command of the English language became a factor. But it was still ok, because the wording usually formed a pattern. It was marbles, people’s ages, number of apples or oranges in the basket, or some such. In a normal situation, if I really wanted to know your dad’s age, I’d just go ask him. I don’t really need to infer that your dad is 2.5 times your age, and then I figure the answer out (assuming I know your age).

Students here kill each other with A’s

Now if you don’t already know, it’s bloody competitive here in Singapore. Students are afraid of not doing well in school, of heads shaken by their friends, teachers, parents and relatives. Parents send their children to tuition classes (in addition to the normal school classes), regardless of their children’s grades. If the grades are bad, then improve them. If they’re great, great! Now perfect them. Go do your ten year series!

I went to tuition classes till I was 10 years old (primary 4 or 4th grade). I stopped because my dad couldn’t afford to pay for the classes. Being able to eat and pay the bills were more important. It’s a good thing I was disciplined enough to get good enough grades (and imbue enough motivation for all subjects, not just maths).

When I was in university, to supplement the cost of education, I looked into giving tuition. I was surprised that everyone from primary one to university level (?!) were asking for help. Let me just say, I make a lousy tuition teacher. I don’t really know the current syllabus well enough to help the students. Once, I brought up the subject of video games, using the position of battleships to illustrate … something. I can’t remember. I think it was x- and y-coordinate stuff. I was trying to interest the young boy I was teaching. It fell flat. I suck…

The Singapore Math Method

Which brings us to curriculum. It turns out that under the Singapore maths curriculum, Singapore students rank high for maths internationally. It’s so good that America has adopted the method. There’s even a name for it: Singapore Math Method. Let me tell you, I’m simultaneously amused and confused.

I’m even more surprised that Israel adopted the method in 2002, translating the textbooks to Hebrew. I was browsing in the bookstore reading Start-up Nation (Amazon link). It told a story of how Israel, being surrounded by hostile countries, had to innovate hard. Their brightest people are in the universities doing research and are also in the top military ranks. The book told a story of how the “flat” nature of their military translated to their way of doing businesses, in particular start-ups. My friend Christopher told me that per capita, Israelis were the richest in the world. It’s their culture that made them more inclined to creating wealth. I was also told about the Jewish mother syndrome… So I’m a little surprised that this group of people want to know about our (Singaporean) method of teaching maths.

I still believe in solving real world problems. I believe we’re not injecting enough curiosity into our students. That Singapore Math Method seems to have less force-feeding of concepts, and more of coaxing the student to question. The Singapore culture doesn’t seem to require curiosity for the students to do well (have I mentioned the parents are bloody competitive?). Hopefully, that’s changing.

This is going to be a cynical view, but I think most Singaporeans are striving for wealth, and wealth alone. Wealth translates to a better life. There’s nothing wrong with that. Singaporeans strive hard to attain wealth so they can forget about (seemingly) miserable lives. Ok, let me take that back. Apparently, Singapore is one of the happiest places in the world. There’s a “but” though…

Singapore ranks high on evaluated happiness, but not on experienced happiness

Alright, this is starting to depress even lil’ cheerful me…

So. Problems are formulated, and then given to our students to solve. But they have to learn how to formulate problems too, and that comes from asking questions, from being curious, from being disciplined and persistent. And that comes from cultural and societal influences, not from educational systems.