A recent tempo blog post compares Lagrangian versus Eulerian decision makers (let's call them LDMs and EDMs). These two approaches appear to have their origin as choices of frames of reference for studying fluid flow. An LDM tracks a single 'parcel' of flow though its entire journey while the EDM examines many parcels that flow through a particular location. Let's apply this to an airline OR (crew scheduling) scenario:
an LDM follows a particular crew operating a sequence of flights through a network before returning to her/his base, while the EDM looks at many crews arriving and departing through a particular airport. LDMs track flow-paths, while EDMS zoom in on activities within a specific node in the network. Another example from airline network revenue optimization: an LDM may focus on a passenger flowing and the accumulated revenue through an itinerary consisting of multiple flights, whereas the EDM zooms in on the variable price and fixed cost associated with a seat on a specific flight that is a part of many passenger itineraries.
Intuitively, it feels as if the LDMs focus on the clearly visible primal decision variables, whereas the EDM focuses on the latent, underlying dual problem. Column generation as an iterative optimization approach works well when the EDMs compute and transmit useful 'dual' signals from specific locations to LDMs (e.g., the rate of pilots arrive and depart at their node) who in turn, collect and apply this updated information to stitch together new and improved flow-paths across the network (i.e., columns), which in turn ensures more balanced and smoother flows across the nodes (i.e., rows). For some problem classes, if we solve the dual problem, our primal decisions are also at hand, and if the dual is unsolvable, the primal is likely to be problematic as well. Conjecture: Lagrangian and Eulerian decision makers build mental models that represent (informal) primal and dual formulations of the same problem. Depending on the context, one or the other approach may be more convenient or effective.
The ability to extract information from noisy dual signals is useful in solving complex or large-scale industrial optimization problems. For example, in the airline revenue optimization example, it is known to be more convenient and reliable for airline revenue/scheduling planners to take decisions based on the shadow prices of flights, rather than rely on the optimized prices of the millions of possible itineraries. Dual methods are insightful and can help solve a decision problem where a frontal assault fails. To the best of my knowledge, the default out-of-box method invoked by the leading mathematical optimization software packages today for solving linear programs is their dual algorithm.
In general, Eulerian decision making or as this post sees it, 'dual-driven decision making' may be the more attractive first-choice approach for human decision making. The tempo blog notes:
"... When flow gets turbulent, the fluid mixes a lot. To properly follow a “parcel”, you have to let it expand as flow lines diverge and churn. This means there is more fluid in your parcel than you started with, more “noise.” Eventually you are trying to analyze world hunger — the entire body of fluid.
But the Eulerian static parcel stays the same size. It just bleeds causal structure and gets more entropic. The action gets a lot more random and choppy, but still tractable in size. It is also easier to shrink what you’re paying attention to when things get complex — it’s called focusing – than it is to reduce the ambition of a model you’re tracking (generally called pruning)..."
Are Operations Researchers Eulerian Decision Makers?
Post a Comment
Note: Only a member of this blog may post a comment.