Friday, September 20, 2013

Finding an Optimal Meeting Location

I encountered a neat version of this problem last week at work, while folks were trying to schedule a meeting with a client.

Decisions, Decisions. Location, Location, Location. Where do we meet?

Problem Statement
There are Wij project team members located at office O(i), i = 1, ..., M, that have skill sets j = 1, .., N. Each office location is staffed by a workers having different skill-sets and job responsibilities, such as research, software development, pre-sales, analytical services, etc. It is preferable that everybody attends, but to achieve a quorum and a productive meeting, at least Q(i) persons from O(i), and at least S(j) persons of skill-set j must be present. Assume that the unit travel expense T is roughly the cost of a round-trip air-ticket between O(i) to the airport nearest the meeting location, and that we incur a fixed, location-specific setup cost C. There are additional requirements that limit the number of feasible location choices: safety, conference-friendliness, etc.

Objective: optimally locate the meeting to minimize total cost.

Let A* be the airport associated with the optimal location.
Let x(ij) be the number of people of skill set j attending from O(i)

The problem formulation looks like this:
Minimize Sum(i, j) x(ij) T(O(i), A*) + C(A*)
sum(j) x(ij)  Q(i), i = 1, ..., M
sum(i) x(ij)  S(j), j = 1, ..., N
 x(ij)  Wij, x integer.
A*  {commercial airports associated with feasible locations}

This resembles a capacitated location-allocation problem. If the x-variables are fixed, the formulation reduces to a pure A* location search. Similarly, if A* is fixed, the problem turns into a capacitated supply-demand problem.  If every location had exactly one skill set, then we can allocate no more than min(W, max(Q, S)) from each office, leaving us with a pure location problem. Let's assume this is indeed the case, and proceed.

If there are K feasible airports, we can compute the M travel costs, plus the setup-cost C per candidate to determine the total cost associated with a choice. After O(MK) computations in an exhaustive search, we can determine A*. But what if K is very large? We could look at this as a Weber problem and find the centroid, or, suppose we restrict our candidates to coincide with one of the office locations. This is not a terrible idea, since we can avoid paying for an external conference hall (C~0). This requires only O(M2) computations, and all team members at the optimal office location can attend.  Will the best choice from this restricted set of "extreme points" yield an optimal cost solution? In general, it is not guaranteed. If air fares to/from a particular airport (e.g. Las Vegas) is relatively low, then it may be optimal for the selected team members from every location to fly there, even if it is lies outside the convex hull of the office (airport) locations. However, if the traveling cost is a 'nice' function of distance traveled, then results from the literature can be employed to provide decision support:

Literature: Finding An Optimal Meeting Point on Road Networks
Stackoverflow discussion: "Shortest distance travel - common meeting point"

A wonderful reference book is the classic ol' textbook by R. L. Francis, et al., on Facility Layout and Location Analysis.
(pic link source: Amazon.com)

The 2013 Annual INFORMS conference is being held in Minneapolis, MN this year. Hypothermically Hypothetically, where would such a conference be located in order to minimize the total expected air travel + hotel cost of attendees (+ organization cost)? Any guesses?  If the optimal location remains static over time, a subset of attendees will end up paying a relatively higher cost, hence some rotation policy may be preferable.

Finding a location in a time-space network?

(pic link source and related blog: Planning an Annual Meeting? Location is Key!)

(A more concise version is published in the INFORMS conference blog).

Wednesday, September 4, 2013

Sine-Generator in the Aryabhatiya, 1500 years ago

Came across this post by Rajiv Malhotra on facebook, and am posting a screenshot.  More research and findings continue to trickle in about the discoveries and creations of ancient Indian mathematicians, and this sloka (verse) is not an isolated example. The focus of this brief post is on the design of the sloka from the data compression optimization aspect.

Brevity and conciseness was important to ancient Indian scientists and linguists for various reasons. Their success in optimally designing such slokas to be memorized by maximizing the density of information carried per unit syllable, while also (and this is important) ensuring that the sloka is logically sequenced and constructed, and relatively easy to memorize, is utterly remarkable. In particular, the affection for the minimal among those Sanskrit grammarians is legendary. There is an oft-repeated saying in ancient India that the joy experienced by a grammarian who manages to achieve a half-a-syllable reduction is only equaled by their joy upon the birth of their child. The choice of the objective function drives the design approach. In contrast with the previous example, we have the Vedic chants in Sanskrit, the world's oldest, unbroken surviving oral tradition, where redundancy was deliberately added to minimize error in oral transmission (an achievement that may have contributed toward India having the world's oldest, unbroken civilization). In this case, what was memorized and repeated was much, much longer than the original verses in order to optimize information and audio fidelity.


(Mysore is a city in Karnataka, India, whose state language is Kannada)

Update (Sept 5, 2013)
The English transcript of the sloka can be found here in the Nature Journal (thanks to Srikrishna ‏for sharing this link).


Update 1: December 15, 2013
A superb post at http://hindufocus.wordpress.com on a compressed Sanskrit verse for remembering the value of Pi to 32 decimal places.
"..... Here is an actual sutra of spiritual content, as well as secular mathematical significance.
gopi bhagya madhuvrata
srngiso dadhi sandhiga
khala jivita khatava
gala hala rasandara
..... The translation is as follows:
O Lord anointed with the yogurt of the milkmaids’ worship (Krishna), O savior of the fallen, O master of Shiva, please protect me."

Sunday, September 1, 2013

Why the UPA will get re-elected in 2014: in 100 words or less

Stats indicate UPA to be the most corrupt government in Indian history, so it won't get reelected in the 2014 elections. Wrong. Here's proof.

1. Scam cash, embezzled dough, and black money is a sunk cost. Irrecoverable past. 

2. INC has turned India's voting mass into MYLOPs.

By definition, MYLOPs are Markovian; their vision of the future is independent of past events, given instant gratification. It follows from (1) and (2) that whoever supplies the biggest freebie to the voting mass now, wins. UPA just designed the free lunch, transcending the NFL theorem

No contest.



Notation
INC = Indian national congress, the dynastic party (ideology: Nehruvian socialism), which has wrecked India almost continuously since political independence (1947).

UPA = United Progressive Alliance = INC + clones, won the last two elections, seeks a hat-trick (= three-peat, in American).

MYLOPs = Myopic, Local Optimum seeking Pessimists. First introduced here

Free lunch = FSB = A grossly underfunded food security bill, which provides a theoretical guarantee of free food for all poor people, but in reality is a food bank for UPA's vote bank.