The Right Way!

It’s been an amazing March and the journey so far has been exhilarating. Fighting dragons, crossing bridges, running races, going in “Strange Loops” etc. Looks like an excerpt from a fairy tale adventure except for the fact that the prince (supposedly me) is definitely not living happily anymore. Big thanks to a couple of colleagues (that includes my mentor Mr. Pai) who helped open the window:

        “Hello Linear-Programming”,
        NULL, NULL, hInstance, NULL);

Well! It all started when my colleague got this wonderful problem from his friend. It went like this:

“What would be the maximum messages that you could send using any given number of senders and dispatchers with varying capacities plus other defined constraints?”

This was the “Larger than Life” generic version of the problem that we yearned to crack. The real problem (the one I believe I have solved rightfully below) was too tempting to be conquered, especially after having slain the dragon (I was able to contain a trojan-horse in my PC without having to forfeit/format my kingdom/hard-disk), I ended up with a naïve procedure that of iteratively, proportionally dividing the load based on sender/dispatcher capacities. My mentor knew from day one that, this was a classic Linear Programming (LP) problem (which I couldn’t fully comprehend then) and he was quite adamant in trying to get this solved “the right way”.

Thus began my captivating journey on Mr. Well’s “Time Machine” across Prussia, along with Euler trying to cross all the 7 Konigsberg bridges “exactly once” (Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani) and Greece, where I pitted against the tortoise in place of Achilles trying to prove Zeno wrong and then going in “Strange Loops” over Escher’s paintings (Godel-Escher-Bach: An Eternal Golden Braid by Douglas R. Hofstadter). And finally after pounding through various other Finite Mathematics & LP books ranging from (A Beginner’s Guide To Finite Mathematics: For Business, Management, And The Social Sciences by W. D. Wallis) to (Linear and Nonlinear Programming: International Series in Operations Research & Management Science by David G. Luenberger & Yinyu Ye), I finally was able to comprehend the problem at hand, and more importantly confront the beast that we intended to leash, “the right way”.

The Problem:

Three senders S1, S2 and S3 can send 50, 100 and 60 messages respectively. These senders need to consume three dispatchers namely D1, D2 and D3 with message capacities 40, 80 and 60 respectively. Determine the message distribution across the senders and dispatchers for maximum throughput provided:

  • S1 can consume only D2 and D3 for sending messages
  • S2 can consume only D1 and D2 for sending messages
  • S3 can consume only D1 and D3 for sending messages


:: My Take On It ::

The problem has been modeled into the following matrix and LP problem as shown in figure below:

The Problem Matrix In LP Terms

The Problem Matrix In LP Terms

I have adopted the “Simplex Method” for solving it as shown in figure below:
The Simplex Solution

The Simplex Solution

:: And now we have the distribution with maximum possible messages (180) as shown in figure below::
The Distribution For Maximum Messages

The Distribution For Maximum Messages

In case, you are still wondering why I live unhappily, you need to take a look at the “size” of the window again that my colleagues have opened.
Yeah it certainly is Infinity ()!