Traveling Salesman Problem in a Portrait?

I'd planned to stop blogging until May this year to do my small bit in helping Narendra Modi become the next Prime Minister of India in the Indian general elections to be held very soon - one that will determine the future of my family there, as well as the destiny of 1.2 Billion Indians. India has suffered from a curse of culpable silence in the last ten years, but now it seems, that is changing, thanks to inspiring examples like these that asks people to come out and 'Vote for India' (thanks to @sarkar_swati,  faculty at U-Penn, for sharing this video).
------------------------------------------------------------------------------

By sheer coincidence, this brief blog, like the previous one, is related to Asian (Japanese) art, and one i felt 'compelled' to do. Thanks to @SimoneCerbolini for sharing this beautiful portrait on twitter. What is interesting about this art is that it was done, as Simone tweets, using "a single thread wrapped around thousands of nails. Artwork "Mana" by Kumi Yamashita"

The artist, Kumi Yamashita, has a facebook page, and here is another picture from there.

The effect is stunning, and one marvels at the human 'cognitive shift' that convinces us that within this collection of thread and nails, is a lady. Here is a brilliant talk by neuroscientist V. S. Ramachandran (Director, Center for Brain and Cognition, UC, San Diego) on 'Aesthetic Universals and the Neurology of Hindu Art' that explains this in depth.



From the operations research perspective, we gravitate toward the mathematical problem hidden in this portrait: determining the least length of thread to traverse through all these nails. A mathematical optimization model that can be used to answer this question is the celebrated 'Traveling Salesman Problem' (TSP), which is known to be difficult to solve, in theory. In practice, however, extremely large instances have been solved to provable optimality.

Here is another page that displays a collection of pictures from the artist's 'constellation series'. It also includes this ultra-close up that lets us see how the threading really progresses at the micro-level.

Each nail is traversed multiple times, and a greater density of thread is used to create a darker shade (e.g. the eye and the brow). Additionally, there appears to be a greater density of nails in that area. Can a thread-traversal path generated by a TSP solver (e.g. concorde) produce a similar effect to the eye and the brain? I'm not sure, although it may still produce 'a reasonable picture of a lady'. If the density of nails is increased in these areas, then perhaps the TSP-artwork may do a good job. Alternatively, it may be possible to modify the TSP network structure to induce such an effect.

Building the Unsolvable Maze

I came across a tweet via Simon Singh, famous writer of books based on math-topics. I've read a couple of them: 'Fermat's last theorem' and 'The code book'. His tweet points to a picture of an amazing maze hand-drawn over 30 years ago in Japan. Although it is supposed to be 'unsolvable', some comments there claim that it could be solved very quickly if it was made publicly available. Among the very first papers I read after coming to the U.S to study traffic engineering (to understand the reasons for India's chaotic, maze like traffic) was about Moore's algorithm entitled "shortest path through a maze". Mathematically, the shortest path problem formulation has a couple of properties of small interest in the context of this discussion. It has no duality gap, and is totally unimodular: It is sufficient to solve the continuous 'relaxation' to recover an integral optimal solution to the primal or dual formulation. Wikipedia has a page on maze-solving algorithms.  Interesting as the optimization problem of finding an 'optimal route' to 'escape' this maze is, a more interesting question to me personally was: why would someone hand-build such an intricate maze over years; and then why not claim any credit for it? I have tried to interpret this based on my understanding of the Indian way.

(source link and main article at: http://imgur.com/gallery/4kyvVVb)

The intense concentration required for such a task is surely daunting: to at once elevate one's consciousness while also dissolving one's aham (ego) that hinders the mind from systematically growing a complex maze whose paths increase rapidly over time as more forks and merges are constructed. Paths that stop even as they begin, paths that ultimately lead nowhere, paths where you travel for a while, only to discover that you are back where you were before... and then after a lot of calm, refined, and introspective searching (not suffering), finding a path that leads one to satya (ultimate reality/truth) that transcends the maya of the maze that held us in its thrall. A path that dissolves the noisy duality between the world within the maze and without, uniting them harmoniously into a unified whole, even as the space enclosed within the maze maintains a provisional identity within this overall unity. And then perhaps a realization that there could be a pluralism of such (alternative optimal) transcendental paths to satya. A harmonious unity within multiplicity that celebrates its diversity, rather than a synthesized unity derived by optimizing the goal of orderly sameness. The latter produces an efficient monoculture, but one that invariably regards pluralism as a seed of chaos. The former, integral unity best represents the nature of the underlying philosophical unity of India that has continually preserved and refined its dharma civilization over several thousand years. This forms the dharmic basis for any reasonable 'idea of India'. I look forward to reading Rajiv Malhotra's new book on this subject.

Journeys that traverse such a path have led to amazing discoveries that enlightened the world, and will continue to do so. Perhaps it produced this captivating art that simultaneously appeals to the casual observer, the artist, the seeker, and the analyst alike; yet each of us seeing only a partial facet of its underlying truth. A work of art to which its 'creator' deliberately did not append a signature to, and claim ownership of, perhaps unwilling to disturb it's harmony. That is the way of the Yogi.

Dedicated to Rajiv Malhotra on the occasion of India's 65th republic day.Thank you.

Optimize Your In-store Holiday Shopping Route

Remember the last time you were not tired after holiday shopping in a busy mall, bulk shopping at a discount-club store, or weekend shopping at a crowded grocery store?

(source links: http://info.museumstoreassociation.org, http://binaryapi.ap.org)

Hopefully, the simple and preliminary 'operations research (O.R)' analysis in this post can help make the experience a little less stressful and maybe even let us enjoy a bit of retail therapy that we can't get online.  The shopping optimization problem addressed here is simple one, albeit with a twist. This post was triggered by an observation made after recent shopping expeditions to a nearby Costco outlet.

We have a long shopping list of L line-items (i) of various quantities N(i) that we have to pick up in a store. How should we optimally reorder our shopping list to reflect the sequence in which we pick up these items?




Version 1
The simple version aims to minimize total shopping time. For example, we can formulate this as an instance of the so-called traveling salesman problem (TSP) that finds the shortest sequence that starts at the entrance, visits each of the L 'cities' once, then the checkout counter, and ends at the store exit (entrance). A google search shows this 2009 research paper by researchers at UPenn, which shares the technical details and interesting results for this version.

To simplify our problem, we assume that the topology of the store is prior knowledge, and we can roughly pre-assign items in the same aisle to the same 'city'. The resultant problem is to find the order of visits to the aisles of interest to us. If the aisles are neatly arranged as node intersections in a rectangular grid, then we simply have to find the shortest rectilinear "Manhattan" distance tour in this grid. Depending on the type of the store, the store-layout itself may be optimized by the retailer based on the observed foot-traffic and 'heat-map' data. For example, it may be designed to retain the customer in the system to increase chances of purchase (exploratory tour, store selling expensive luxury/fashion products), or quickly out of the system (routine tour, obligatory products like groceries), or based on some other goal. Store space and layout problems are known to be commercially useful optimization problems in the retail industry.

Picture linked from an iTunesApp (Concorde) page of Prof. Bill Cook that solves TSPs :)

Version 2
Let us additionally assume that product attributes have an impact on our order. Suppose one or more items in our list is located in the frozen section at a grocery store, then we may prefer to get there at the end of our tour. Luckily, many stores appear to anticipate this (?), and locate this section towards the end of the store. Thus if 'maximum freshness' or 'minimum damage' is an additional consideration, this may alter the TSP route and the final ordering of items in our shopping list.

Version 3
This was the problem that was of immediate interest to me today. Costco sells stuff in bulk, so the items tend to be heavy, and considerable energy is expended moving the cart through the store. At the risk of mangling undergrad physics, let us proceed with our analysis...
Let μ be the (constant) coefficient of rolling friction between the wheels of the shopping cart and the store-floor. Then the work required to move mass m through distance d = force x displacement =μmgd, where g is the (constant) acceleration due to gravity. Thus a squeaky-wheeled cart will make us work extra hard. Speed of shopping is a consideration if we want to keep track of power (force x velocity). Covering the same tour length in half the time requires twice the power, i.e. the rate at which our body expends stored energy.

Carry versus Cart (reinventing the wheel)
If we had zero rolling friction, technically the only work involved is in lifting items and putting them in our cart. We can assume that this work is independent of our order of visit and is a fixed quantity. On the other hand, if we are not working with a wheeled-cart, but carry our stuff in a market-basket or shopping bags, then we have to raise the potential energy of the items to height 'h' (mgh) all the way until checkout, and also overcome the sliding friction between our shoes and the floor, which would probably be higher than the rolling friction, as illustrated below.

(link source http://static8.depositphotos.com)

Why is a shopping experience increasingly stressful over time?
As we add items to our cart, the work done per unit time (power) required increases. In the continuous case, this problem closely resembles our 'optimal snow shoveling problem' analyzed during a February snow storm. The accumulated objective function cost there increases as the square of the distance. Here, we look at the discrete situation. When we visit city 'i' to pick up N(i) items each having mass m(i), we instantaneously add mass N(i) * m(i) that we have to lug around until checkout. After picking up k-1 items, my total work done will approximately be:
μg * sum (i = 0,... k-1) W(i) * d(i, i+1), where i = 0, represents the store entrance, m(0) represents the mass of an empty shopping cart, and
W(i) = sum(j = 0, .., i) N(j) * m(j) = total mass carried from city i to i+1.

In other words, the 'cost' accrued while traversing any pair of cities also depends on the items we picked up earlier, i.e., it is no longer memory-less and varies depending on the cities visited earlier.

Result: our shopping gets increasingly more tiring over time

If one of the items in our shopping list involve a heavy item, then our optimal solution may no longer be the shortest time tour.  We now have to solve a minimum-effort TSP. Operations Researchers have also looked at methods for solving a path-dependent TSP in the past. A simple heuristic approach would be to break the trip into two tours. The earliest items stay with us the longest, so we first find the optimal sequence through the light items, followed by the shortest tour through the heavy items. We also have to organize the shopping cart carefully enough to ensure that our light items do not get squished by heavy products, and our ice-cream doesn't melt. I'm sure there are better algorithms than the one provided here.

Recommendation
If we want to burn calories while shopping then a good way to do that, based on our previous discussion is (a) carry our items, (b) pick up the heaviest items first, and (c) take the longest route to maximize energy expenditure (d) walk briskly. This health-and-fitness article provides ten tips for exercising that includes these ideas. For the rest of us who are looking to minimize effort, we simply do the opposite:

We sort our shopping list items in decreasing order of expected weight (frozen stuff goes to the bottom too), while also ensuring that the aisles of adjacent items in the list are close to each other, and we are not revisiting aisles or zig-zagging much.  Some swapping may be required to find improved sequences. Many of us have probably evolved into efficient shoppers over time, and naturally take these steps and more, but if there an opportunity for improvement that the 'science of better' can uncover for us to make our shopping less stressful, let's take it.

Happy Holidays!

Update 1: December 17, 2013
IBM Smarter Retail article says:
"..... Most recently, Lowe’s has offered the customer a product location functionality that is integrated with their wish list. According to Ronnie Damron, .....Whether customers are browsing the store for ideas or searching for a specific item in a hurry, we think the Product Locator feature will simplify the shopping process, creating a better experience that encourages customers to come back again and again.”

Operations Research for the SmartGrid - 2: Optimization Problems

In this sequel to part-1,  an overview of a few, specific optimization models employed within three different Smart-Grid areas is provided. I found these samples to be interesting from a practitioner's perspective. INFORMS publishes a lot of good papers in these areas, and is an excellent source of references.

Managing Electric-Vehicle (EV) Charging within a Smart-Grid
EV System Perspective: 
EV problems are fun. Researchers in Hong Kong have investigated efficient online charging algorithms for EVs without future information, where EV charging is coordinated to minimize total energy cost. EVs arrive at the charging station randomly, with random charging demands that must be fulfilled before their departure time. Suppose that N EVs arrive during a time period T, indexed from 1 to N according to their arrival order.  The optimal charging scheduling problem minimizes a total (convex) generation cost over time T, by determining the best charging rate for EV i at time t, x(i, t), subject to various constraints.

The difficulty of an efficient charging control mainly comes from the uncertainty of each EV’s charging profile. Prior approaches assume that the arrival time and charging demand of an EV is assumed to be known to the charging station prior to its arrival. However, the HK team have come up with an optimal online charging algorithm that schedules EV charging based only on the information of EVs that have already arrived at the charging station. They show that their approach results in less than 14% extra cost more an optimal offline algorithm,   which can be potentially reduced even further.

EV User Perspective

Cool routing algorithms can also be developed from a user-perspective. One interesting work I came across takes a more holistic and rigorous view of the simple Tesla routing problem that I blogged out a while ago. Researchers in Europe look at a routing subproblem within the more general context of managing congestion at EV charging stations and minimizing the impact of EVs on grid performance. They employ an algorithm to compute the best charging points to visit to based on the estimated travel time (shortest-path, and reachability based on available battery power) to all charging points, and the point-specific charging cost. Input: O-D locations, initial battery level, desired charging level for the EV user, and the preferred time of departure. The optimal route, the subset of intermediate charging points, and the slot that the EV is going to charge at, are returned as output.

Demand Response and Pricing
Revenue Management and supply chain analytics folks will be pretty familiar with this area. Smart-devices can be programmed to automatically (with human overrides) respond to price changes by reducing or rescheduling electricity usage. Couple of differences here from standard RM/SCM problems : i) unlike supply chains that process manufactured widgets through warehouses and distribution centers, it is quite difficult to efficiently store and "ship" electricity using batteries, although the technologies are getting better each day. Thus, the electricity we use is probably produced less than a second ago, and marginal costs can spike during peak periods ii) electricity tends to be incredibly inelastic, making it stubbornly resistant to pricing changes, unlike say, smart-phones.

We noticed that prior approaches that apply peak-hour "congestion" pricing tended to 'migrate' rather than mitigate peaks. By carefully combining peak and off-peak pricing with accurate short-term load forecasting, and jointly optimizing the entire price profile, it is possible to proactively flatten the overall predicted load profile by inducing customers to make small shifts in their usage. Even a small peak shift-reduction during high-load days can result in a lot of savings. In fact, our experiment using actual Smart-Grid data showed that even a half a percentage point peak reduction using optimization could potentially lead to more than a 25% reduction in cost, which can benefit both the customers, as well as the utility companies.

Smart-Grid Control
Among the variety of problems solved here, researchers are also looking at the security-constrained optimal power flow that aims to minimize the total cost of system operation while satisfying certain contingency constraints.This smart-grid formulation extends the standard optimal power flow (OPF) problem, which determines a cost-minimal generation schedule cost while satisfying hourly demands, as well as energy and environmental limits, and meeting network security goals. Optimization methods used here include Benders decomposition, as well as Lagrangian multiplier techniques. Some of the newer variations employ distributed algorithms that are designed to work on a massive scale.

These are just a few samples that caught my attention. There are a variety of other problem areas being addressed (e.g. batteries, renewable energy sources, micro-grids), all of which perform some type of an optimization.

Solve TRP, Drive Tesla

So the awesome and hyped Tesla Model S is beating Mercedes, BMW, and Audi in sales despite the $70K price tag. One problem is the current lack of charging stations required to recharge over long trips. CNNMoney reports:
"CNNMoney took a Tesla Model S on a test drive from Washington D.C. to Boston. The all-electric car drove 450 miles with two stops to recharge at Tesla's Supercharger stations in Delaware and Connecticut"



A second problem is that unlike conventional gasoline cars that can be refueled very quickly, charging can take a relatively long time, and adds significantly to your total travel time. In the near future, as the number of Teslas increase, the number of charging stations is likely to go up too. However, it will remain a sparse resource for some time. A future Tesla trip from New York to California will require many recharging stops, reminiscent of the old stagecoach problem during the Gold Rush era, which is used to illustrate the principles of Dynamic Programming.

Update: May30, 2013
Popular Mechanics reports:
"...the California-based EV automaker plans to expand its fast-charging "supercharger" network across the continental U.S. During today's announcement, Musk said New York to Los Angeles trips would be viable as soon as this winter. 

"When you get in a car you have the ability to go almost anywhere," Musk said. "That's what the supercharger network will do." 

The rollout will begin as soon as this summer, with the number of stations tripling to 27 nationwide by the end of June. In addition to increasing supercharger density along the already-established California and Mid-Atlantic coasts, Tesla will debut chargers in a handful of new metropolitan areas within the next few weeks, including Austin/Houston, Portland/Seattle, Boulder/Denver, and Chicago/Milwaukee. By the end of the year, Musk expects to to have "a couple hundred" superchargers spread across the U.S. and southern Canada, with as little as 80 to 90 miles between stations along the Altantic and Pacific coasts..."

Tesla Routing Problem
Given a road network G having a limited number of charging stations located at specific nodes, the Tesla Routing Problem (TRP) will have to:
Find the shortest feasible time path from origin O to Destination D in network G.

Feasibility requires the car to visit enough charging stations in a timely manner. Optimality requires that the sequence of visits be carefully selected such that the total time spent is kept to a minimum.

Total travel time = driving time + recharge time

This involves two decisions:
D1. Which recharging stations to visit en-route?
D2. How long to recharge at every pit stop?

Assumptions:
A1. The longer you recharge, the longer your available range (to a limit).
A2. All recharging stations are similar, and infinite capacity (no queuing!)
A3. Range is deterministic

Update on A2: The Tesla can charge on any outlet, but the time to recharge can vary depending on the source.

Clearly, optimally solving TRP involves the finding a solution to a Traveling Salesman Problem even in the special case of instantaneous recharge (Y=0).

(Updated September 2013: As mentioned in the comments, the general case is not a TSP in the network of charging stations. Here, the assumption is that stations are sparsely located and we visit each one along the way. The title is changed to reflect this distinction).

This is no different from the (milder) challenge faced by conventional car drivers in unfamiliar areas where gas stations may be hard to come by (see this old post). Charge cannot be carried in Jerry-cans. The  shortage of charging stations does make every long Tesla trip a non-trivial problem to manage. Tesla owners have to deal with a NP-Hard Optimization Problem (Heh) on every such trip, but in practice, it should not be difficult to find good quality, feasible TRP solutions.

The recharge time makes the TRP a bit more interesting. If two stations are close to each other, we don't have to recharge fully, and just need the minimum to reach the next stop - or perhaps we recharge fully, which allows us to reach a station that is further away but turns out to be more time-effective, overall. Clearly, these two decisions appear to be interlinked and may need to be jointly optimized. D1 is a binary decision variable X(i) - we either visit or don't visit a station at node X(i), whereas D2 is a semi-continuous variable Y(i) conditional on D1:

Y(i) ≤ U.X(i)
where U = maximum recharge time.

Another interesting and maybe even useful problem for Tesla-makers to solve is where to add new charging stations on the network G over time. What is the minimum number and location of stations required to guarantee feasible solutions to any TRP in the 48 states of continental US? How will stations deal with congestion in the future? and so on ...

I haven't driven a Tesla yet but I wouldn't mind relocating my office to inside one and telecommute.

Optimally Managing Ladybugs

My daughter loves ladybugs.  However, when it comes to cleverness, many have noted how bees and ants (which seem to have a special place in Indian hearts :) "solve" traveling salesman and shortest path instances that matter to them (see this interesting link as well). In contrast, a ladybug's decision analytics appears to be somewhat shaky. They don't seem to have the kind of auto-GPS of bees and ants (at least in the context of this post), and seem to get confused and stray from their optimal path.

(pic source)

Recently, a number of LBs invaded my residence, and I spent a lot of time trying to shoo them away and determine how they got inside in the first place so that I could block their entry. Then, I came across this website. Apparently, ladybugs prefer humidity and warmth and try to enter homes as winter begins. OK. However, a good number also enter the house come spring time, which was puzzling. It seems some of the LBs goof up. Ladybugs roosting under windows outside the house, with a certain probability, enter the house instead of enjoying spring time outside. Once inside, they suffer from dehydration and die (unless they figure out the route to the bathroom or kitchen). If we try to force them out, they get stressed and shed 'yellow blood' that can stain walls. The optimal ladybug solution for this time of the year is to simply open the windows, so the ones who came inside by mistake can leave. It's a win-win for both parties, and it actually worked. On the other hand, during winter, we have to try and provide a cozy, alternative home in backyard and insulate the house well to keep them out.

Optimally Shoveling Snow

This post attempts to compare the efficiency of various approaches used to clear a rectangular area (L > B) of snow, using a good old manual shovel of width w, always moving in straight lines. We assume that the gradient of the area is zero, and that h inches of snow has fallen uniformly over the field. We also ignore the capacity of the shovel for now. The total snow that must be banked at the borders of the field is constant = LBh. Also total working distance traversed ~ LB/w.

Snow shoveling can be a grueling exercise for some, and public health departments always publish safe shoveling tips during the winter season. This is especially important for people with potential heart problems or back problems. Hopefully analyses like these will help (I'm sure people have looked at this before, but just in case ...).


Our objectives are to minimize:
1. Total work done = Total snow moved X distance moved.
2. Number of Stop-Starts with a fixed unit cost k incurred
3. Total work time in cold weather.

Model:
Given an area bx, and assuming we are moving along x, the snow nearest the starting point must be moved the maximum distance, and this distance linearly reduces to near-zero at the end of x. Thus (introducing an integral sign in this blog, yikes):
a) total work done = ∫wxdx = wx²/2
b) Unit stop-start cost = k

Approach 1: Shoveling east-to-west (along L, banking at the west end) or bi-directional traversing:
total number of passes =  B/w
total work done = (B/w) * wL²/2 + kB/w = BL²/2 + kB/w



Note that the effort level is independent of the shovel width. A wider shovel requires fewer passes but more effort per pass.

Approach 2: Shoveling south-to-north (along B, banking at north end) or traversing in both directions:
total cost = LB²/2 + kL/w

Thus, the second approach reduces the total work done by a factor L/B. However, this reduction is achieved at the expense of more stops (which may not be a bad thing from a health perspective; k may be negative or zero for some). If L = 2B, the second approach requires 50% less effort, but requiring twice as many passes. 

Approach 3: I observed that my Canadian neighbor divides up the rectangle into two areas, always starts from the middle, and creates banks on both sides. If we bank the snow at the south and north ends:
total number of passes =  2L/w
total cost = LB²/4 + 2kL/w

The third approach is twice as effort-efficient as the second approach, at the expense of making twice as many banks, plus an additional penalty of traveling to the mid point after each pass. On the other hand, you are also less likely to run into capacity problems, since the material handled per pass is the lowest. We can also verify that among all starting points chosen for approach-3, the mid-point (B/2) yields the minimal effort. In general, any of these approaches become preferable in terms of total cost, depending on the chosen objective function. For example, we could modify approach-3 and bank snow close to the ends the field (< B/2) at their respective (west or east) ends at the expense of adding more stop-starts.


Time Considerations

If the shape of the field changes, the approaches may change, but it appears that a good principle to follow is to limit the material moved between successive bankings. In particular, we want to identify the shortest Euclidean path between every point in the field to the nearest feasible bank, and purely from an effort perspective, shovel snow along a path to a feasible bank that is optimal for all points on that path. This seems to reduce the working duration taken as well: 
Suppose we maintain constant momentum (i.e. mass X velocity = constant) during a pass, our velocity will inversely proportional to the amount of snow accumulated (e.g. 1/wx). Total time per pass ∝  ∫wxdx = wx²/2, which is proportional to the effort.

For such a velocity model, approach-3 also appears to be optimal from the time perspective. If we assume constant velocity, then the three approaches take the same working time, ignoring the shovel-free travel time required for approach-3. Among these alternative time-optimal approaches, the third approach does the best on the effort-objective.


Lawn Mowing
Non-propelled, walking lawn mowers with bags? Regardless of the traversing method adopted, our effort (per our chosen model) increases as the square of distance until we empty our cut-grass. If we adopt approach-2 or 3, we have more banking opportunities.  However, approach-3 may result in a mowing pattern that won't look so nice, so approach 2 may be more preferable. Operating a self-propelled mower with built-in mulching may reduce our effort considerably.

Update 1: Post "Nemo" Shoveling, February 9, 2013
A truly optimal solution is to have a kind and wonderful neighbor. After three hours of efficient shoveling (h = 24 inches) and 40% completion, Kevin zipped in with his snow plough and finished the remainder in 5 minutes before going off to help others. I now have to find the best way to thank him.

Update 2: (WSJ, via @ThaddeusKTSim), February 10

 (source link: online.wsj.com)

House Hunting Efficiently

One of the consequences of the kind of convergence shown in this graph was that it created the need to buy a house. It's become a ritual to spend weekdays creating a list of houses that are feasible with respect to hard constraints (big kitchen, level lot, ..), and then converting that into a prioritized list based on how they score on soft constraints (pre-wired for Bose speakers, for example) that in turn motivates a preferred way of visiting these houses during weekends. I noticed that I rarely see each house in isolation and my view of a house tends to be colored by what I saw earlier. However, of late, the time to view these houses has become a scarce resource, so I created an O.R driven prioritized list that maximizes and optimally allocates viewing time, keeping the total duration equal to the limited time available. I used my automobile GPS unit as the solver.

This GPS unit "solves" the Traveling Salesman Problem (TSP) to figure out the optimal (?) order of visitation that minimizes total drive time, which automatically maximizes aggregate viewing time. (In particular, if houses are located on either side of a busy highway or Main Street, a good heuristic would be ensure that the optimal path intersects such a link infrequently.) I can then allocate the optimal expected viewing time to the houses based on personal preferences. The total viewing time also informs me if I have spread myself too thin, in which case, I can start deleting houses with the lowest scores from the list and re-optimize until the solution looks reasonable. 

If viewing order is important from a 'relative comparison' perspective, the resultant constrained TSP problem becomes a bit more harder to solve using a GPS unit. A simple heuristic rule could be to fix the second node ("first house to first") and/or the second-last node ("house to visit last") of the tour and let the others be visited based on time-optimality. If your realtor drives you around, her/his office is the start and end node of the Hamiltonian circuit.

One issue I encountered while using the GPS unit to merely drive-by a house as part of a local neighborhood search (pun unintended) is that I had to get close enough to the house and maybe pause a bit to inform the GPS that this house has been reached. Otherwise, the GPS unit would continually re-route me back to the house, resulting in considerable confusion.

The King and the Vampire

Read this Wikipedia entry if possible to enjoy the format of this 'fun' post a bit more.

(pic source link: Wikipedia)

Every Indian child has grown up listening to the stories of King Vikram and the Vetaal (some kind of vampire spirit who  often clambers up a drumstick tree). It used to be particularly exciting to read these tales in the children's magazine Chandamama, where the first paragraph went something like this:

Dark was the night and weird the atmosphere. It rained from time to time. Eerie laughter of ghosts rose above the moaning of jackals. Flashes of lightning revealed fearful faces. But King Vikram did not swerve. He climbed the ancient tree once again and brought the corpse down. With the corpse lying astride on his shoulder, he began crossing the desolate cremation ground. "O King, it seems that you are firm about the decision you've taken. But it is better for you to know that there are situations where an O.R decision optimization project invariably results in complaints, which apparently requires another O.R project to fix! Let me cite an instance. Pay your attention to my narration. That might bring you some relief as you trudge along," said the vampire possessing the corpse. 

The OR vampire went on:
Years ago in a bankruptcy protected U.S airline in a windy city, a well-paid MBA consultant for the Onboard Services department (OS) approached our OR team to pitch a new R&D project to manage an inventory problem on a network. Apparently, OS was hit by a surge of complaints in recent times that contractually purchased hotel room inventory in several U.S cities served by the airline were left puzzlingly and 'dangerously underutilized' in the last few months, way off their usual levels. Could we help match supply and demand using our OR bag of tricks by moving things around in some optimal manner?

No, ..These complaints were not coming from Flight-Attendants (FAs), but from management folks in OS. If anything, the FAs were happier and chatty about the quality time they were spending with family and kids. FA's don't make the kind of money that pilots do but since there's roughly about 2-3 FAs for every pilot, he wondered if our team's OR-based crew scheduling system was giving away expensive 'happy hours' at company expense? .. yes, this problem started 3 months ago, How did we know? ....

It wasn't a guess. We deployed a shiny new optimization system for planning monthly crew schedules for OS just 4 months ago. Things were not looking good. Where did we screw up? We investigated the reasons for this and within a couple of days found the answer that had the entire team laughing and celebrating. We gave the consultant a brief answer that he was satisfied with. The 'network imbalance' project was shelved.

So tell me King Vikram, what do u think happened and why did my team laugh and celebrate? Answer me if you can. Should you keep mum though you may know the answers, your head would roll off your shoulders!"

Forthwith King Vikram replied: "Vetaal, this is one of your easier ones. The answer is in three parts.

1. A significant portion of the senior FA population were married women who were happy because they got to spend more weeknights at home. Their work-hours per week is upper-bounded by federal regulations and remains fairly constant if optimized well enough, which must mean that these FAs were spending a lesser proportion of time away from home than ever before while still making the same kind of money.

2. Since FAs don't get paid as much as pilots, a relatively expensive portion of their schedules is likely to be the hotel room and transportation costs associated with their overnight layovers. I suspect that the new algorithms in the scheduling system managed to uncover improved schedule patterns among those trillion trillion possibilities by identifying near-optimal daytime airport connections that yield a denser work-day in tandem with a shorter TSP sub-tour traveling pattern that brings them back home more frequently. Doing so must have also maintained or slightly improved the weekly productivity levels (otherwise management would not have bought into this model in the first place).

3. This result is a win-win for all stakeholders once the longer-term agreements with hotel chains are favorably renegotiated to sync with this newly realized reality. This is precisely what you must have told the consultant. Since all this was accomplished without additional capital investment using OR, 'The Science of Better', your team probably felt that their algorithm's practical effectiveness was validated by this 'complaint'.

No sooner had King Vikram concluded his answer than the vampire, along with the corpse, gave him the slip.

(pic source link: Chandamama.com)

Long-distance convergence

The first picture tracks the achieved percentage reduction in a certain minimization objective function value (a shortest path distance) relative to it's initial value, over time.

Not monotone convergence, but still pretty good, and the relative gap finally goes close enough to zero (within a tolerance of 0.5%). Most would be happy to see this solution performance on any O.R decision problem instance in practice.

The next picture tracks the raw values corresponding to the first plot - the shortest path in miles, between the location of my ORMS job and that of my wife's (non ORMS job). The time scale is in years. This also happens to be the commute distance (logarithmic scale).

Average convergence rate = 581 miles/year
Total cost incurred = 27,500 mile-years (counting from year "-2")

Sometimes, superlinear convergence feels terribly slow, but in this era of labor restrictions, we'll chalk this down in the 'wins' column.