The Perfect Matching: Part 1
The Rediscovery of Optimization
How many Operational Researchers does it take to change a light bulb? Optimally Six: Two Americans to auction, three Hungarians to transport and a German to fit the bulb — VK
Light bulb jokes aside, this post is based on my recent foray into the early history of Convex Optimization. A story of the rediscovery a nearly identical technique to solve the multiple disguises of a problem. The cast of characters is a short list of clever minds from different eras in history unbeknownst of each other’s approach— Jacobi (Germany), Kuhn, Birkhoff (USA), and Kőnig, Egerváry, von Neumann (Hungary).
Operations Research
Operations Research (OR) was compulsory for engineering undergraduates (the mid-90s) in India. The subject felt dry. I forgot the rules as quickly as I memorized them for the sake of exams. We didn’t have access to a graphing calculator or know if one existed — perhaps not. My recollection is blurry, but our computer lab resembled a highly secure facility. It hosted a few standalone personal desktops running on Windows 95 operating system without internet access. They might as well be museum exhibits with strictly supervised access for use. But we were mesmerized watching the screen pointer move as we moved the mouse! It was magical.
Amid the fear of breaking expensive equipment and my ignorance of a computer’s capabilities, I failed to connect the dots. I consider that a colossal missed opportunity of my teenage years. Little did I realize the rules I busily memorized to apply on paper were algorithms to tackle the complexity of computationally intensive problems. Black boxes (blind rules) are like parlor tricks. They obscure the real power and beauty of mathematics. Obtaining answers may feel like pulling a rabbit out of a hat, but one fails to appreciate why they work in the first place and what their inherent limitations are, not to mention the unintended consequences of applying them to the real world. Modern non-explainable Deep Neural Networks belong in this category — but I digress. Given the time crunch and course load, I did what was required to cross the hurdle.
Fast forward a quarter-century. Over the past several years, I have been catching up with a growing collection of Project Euler problems during the winter holidays. I attempt to digest and tackle them at a leisurely pace. Persistence usually pays off, opening doors to fascinating ideas. This problem, in particular, was a perfect candidate for applying one of the OR parlor tricks I learned and vaguely recalled from my undergraduate days. The internet helped. This time, my goal was different though — to get the intuition behind it. Hence this article. I will admit, it’s broad brush strokes. Any lack of mathematical rigor is on me. I am a visual person. This article may make real mathematicians in the audience squirm, but this is a non-mathematician’s attempt to convey the early advances in what has now blossomed into the fascinating world of Convex Optimization. Let’s take it from the top.
Complexity
The practical world is driven by inordinately complex processes. Whether it’s assigning seats to passengers for an airline booking or customizing burger toppings, there is complexity lurking in plain sight. The list is endless — course assignments to faculty, e-commerce shopping cart, packaging and shipment of goods, assigning bids to contractors, risk-averse portfolio allocation, trans-continental supply chain, electronic device sizing for optimal design, time-slots for satellite communication, high speed circuit switching in modern data centers, computer vision, GPS based satellite navigation, and so on.
Q: How does complexity manifest?
A: A wide open expanse of possibilities
This visual in a recent tweet captures its essence.
All the possible ways life can tumble forward is enormously expansive. We call it future (green cascade). The present moment (vertical line) precludes all possible futures. In navigating life (green lifeline), we only get to experience one with conscious (volitional) choices we make and subconscious decisions made for us by circumstances (nature/nurture). The rest (black cascade), if one takes the Many-worlds interpretation seriously, are experienced by our copies. The key takeaway is that the space of decisions is vastly complex and we get to pick one.
Is there an optimal set in the vastness of decision space?
Mathematical optimization attempts to model complexity. It peeks at the combinatorial explosion to extract patterns. Finding a solution (best possible decision) comes under the heading of Convex Optimization. Before we develop an intuition, it’s worth rehashing how far we have come with computation.
Computation
The ever-increasing processing power of modern computing has forged tremendous progress in many intellectual and practical pursuits. Not that long ago, around 1950, that wasn’t the case. Computers were mechanical, even as solid mathematical foundations were being laid by the likes of Turing, Gödel, von Neumann and others. Let’s pick an example for illustration. Suppose there’s a large project that involves many tasks (and many individuals) to complete. Let’s call it the “personnel assignment” problem.
- Its completion requires a fixed number of tasks (jobs).
- Each task requires some expertise (subcontractors) who bid for them.
Each contractor has their own rates / completion schedules. So we may be looking at few different ways to optimize — fastest schedule, lowest overall budget, highest productivity and so on.
In September 1949, Thorndike took a swipe at mathematicians when he was addressing the American Psychological Association (APA) on a typical “personnel assignment” problem that they were dismissing as a non-problem.
The past decade, and particularly the war years, have witnessed a great concern about the classification of personnel and a vast expenditure of effort presumably directed towards this end.There are, as has been indicated, a finite number of permutations in the assignment of men to jobs. When the classification problem as formulated above was presented to a mathematician, he pointed to this fact and said that from the point of view of the mathematician there was no problem. Since the number of permutations was finite, one had only to try them all and choose the best. He dismissed the problem at that point. This is rather cold comfort to the psychologist, however, when one considers that only ten men and ten jobs mean over three and a half million permutations. Trying out all the permutations may be a mathematical solution to the problem, it is not a practical solution -- Edward Thorndike, 9th Sept, 1949 APA Conference, Denver, CO Excerpted: On The History of Combinatorial Optimization (Till 1960)
Assume the project where contractors can carry out tasks, but must bid (with their quotes listed in identical units of currency or time) to win a contract.
What is an optimal assignment of bidders to tasks?
Well, that depends on (a) what we want to optimize and (b) under what constraints. The cells could represent cost-for-task or completion-time. They could also stand for qualification-level. Depending on what the numbers represent, we may want to minimize (or maximize) the overall cost, schedule for completion or score.
- Tasks: {A, B, C, D} | Contractors (Bidders): {I, II, III, IV}
We start with a 4×4 matrix. If one were to guesstimate, an argument would proceed something like this:
- Of the four ways to pick any of the four possible contractors (or tasks), we pick a cell (say B/III = 1). Then scratch the remainder of row III and column B because we have given away that bid.
- What remains is a 3×3 grid. Then we repeat the process. Say we pick C/IV = 2, and get rid of the remainder of row IV and column C. This we can do in three possible ways.
- We are left with a 2×2 grid. There are two possible ways to pick. Say we assign task A to Bidder II (A/II = 5). After that, the only remaining option is D/I = 9.
The assignment, viz., A:II, B:III, C:IV, D:I costs 5+1+2+9=17 units. But is that that the best we can do (most optimal)? If we insist on being methodical, we must check 4×3×2×1 = 24 = 4! (four-factorial) possible assignments — and for each, calculate the cost. The sets yielding the least total cost are the most optimal assignments.
As Thorndike lamented, a ten persons/ten jobs assignment task may be represented in a row/column spreadsheet (a 10×10 grid) which blows up to over 3.5 million permutations, i.e., 10! = 3628800 possibilities to scan and pick a winning (optimal) combination should one exist. That was the case in early 1950. Without computers or clever techniques (or both) seemingly simple tasks could seem insurmountable.
Computers are extremely fast today compared to 1950. Suppose one assignment takes a mere microsecond (1μs) to verify/compute. Scanning 10×10 grid takes 3.63 s — not bad (or terrible) depending your perspective. But is mere brute-force sufficient? Perhaps not. Here is the solution (all 24 listed) obtained by brute force. We notice two possible ways to minimize overall budget: 17 units. However, if the numbers indexed productivity, only a single assignment maximizes productivity: 27 units.
Since 1950, the world has enjoyed over seven decades of quantum leaps in computing. It continues to evolve in ever more powerful ways. Modern GPU’s are equipped with hundreds of TeraFLOPS. But Complexity, like air, expands to fill the space. Nowadays, it’s not uncommon to have millions of variables with equally large number of constraints in modern optimization problems. In many cases, the hunt for optimal solution may last several hours to a few weeks. It’s a NP-hard problem and brute force alone is woefully inefficient. We need Convexity — the clever insights from geometry.
Convexity
This will be the next installment (part 2) in the series.
Thank you for your readership and support.
© Dr. VK. All rights reserved, 2022
References
- On the history of combinatorial optimization (till 1960) — A. Schrijver, 2005
- A tale of three eras: The discovery and rediscovery of the Hungarian Method — Harold W. Kuhn, 2010
