You are the visionary curator of the prestigious 'Innovations Through Time' museum exhibit in DS City. This year concludes with seven weeks of auctions of groundbreaking historical artifacts, each requiring a significant upfront cost for restoration, specialized display infrastructure, and enhanced security.
A clause in the museum's charter, imposed by the mysterious benefactor who donated the artifacts, dictates a rigid rule: if you have sufficient funds (the amount of which is determined by how the previous restorations and auctions went) for the next artifact, you must proceed with its restoration and auction, regardless of its individual financial prospects. If funds do not suffice, the artifact is returned to the donor unrestored and the auction is cancelled. Moreover, while most artifacts have a high probability of drawing huge crowds and thus generating substantial additional revenue, there's always a risk of lower-than-anticipated public interest. In such cases, the auction in that week is cancelled as well, and the restored item is returned to the donor, impacting your available cash for the next restoration.
Your initial budget is $10 million. Your mission is to determine which artifact to restore and auction next so as to maximize the museum's final operating budget after all seven artifacts have been considered.
Details
Each artifact has an upfront restoration cost, a success probability (meaning it will attract enough attention to have an auction), and a potential auction revenue (which is normally distributed around a mean with a standard deviation of 10% of that mean, reflecting the variability of public interest).
Artifact Data:
- Henry III's Chamber Pot: Restoration Cost $7,000,000, Success Probability 0.55, Mean Expected Revenue $12,000,000
- Statue of Caligula's Horse Consul: Restoration Cost $3,500,000, Success Probability 0.70, Mean Expected Revenue $6,000,000
- Newton's After Apple Encounter Cooling Washcloth: Restoration Cost $3,000,000, Success Probability 0.85, Mean Expected Revenue $4,000,000
- Johnny Weissmuller's Swim Trunks: Restoration Cost $1,800,000, Success Probability 0.70, Mean Expected Revenue $3,000,000
- The Edison Beard Filament: Restoration Cost $1,400,000, Success Probability 0.80, Mean Expected Revenue $2,000,000
- The Wright Brothers' Second Propeller: Restoration Cost $300,000, Success Probability 0.90, Mean Expected Revenue $1,000,000
- The Apollo 13 Electric Patch Contraption: Restoration Cost $300,000, Success Probability 0.95, Mean Expected Revenue $500,000
For each artifact, its restoration cost is immediately deducted from your budget when the item is selected, provided the current funds suffice for the restoration (if the funds do not suffice, the auction for this item is cancelled). If the auction attracts enough interest (based on its success probability), the normally distributed revenue is added to your budget before you select the next artifact.
Have you found a good policy for choosing the next item? If not, here is one more chance to think for yourself!
One way of solving this puzzle is to simply fix the sequence of artifacts. In this case, a good sequence is
- Statue of Caligula's Horse Consul
- Henry III's Chamber Pot
- The Apollo 13 Electric Patch Contraption
- The Wright Brothers' Second Propeller
- Newton's After Apple Encounter Cooling Washcloth
- Johnny Weissmuller's Swim Trunks
- The Edison Beard Filament
This sequence gives expected net gains of $2,102,378. What is interesting is that this value exceeds the sum of the expected gains of all seven items, which is only $1,975,000. The main trick here consists in setting up the Chamber Pot for auction directly after the Horse Consul. Note that the Chamber Pot is expected to lose us $400,000. By placing it after the Horse Consul, there is a chance that we can avoid restoring the Chamber Pot due to insufficient funds, thereby limiting our expected losses should the auction of the Horse Consul be unsuccessful. However, even with this optimized sequence and the expected net gains of over $2.1 million, accepting the donor's proposal remains risky: The chance of ending up with a lower operating budget than the starting $10 million is over 51% as this Seeker Colab shows. The distribution of the net gains over 100,000 scenarios is given below.
In the Colab, we also show a second Seeker model where the solver does not fix a sequence upfront but learns a policy for selecting the next artifact based on the available funds and the artifacts that are still available. Curiously, even a simple extreme learning machine (ELM) with just seven hidden nodes can capture a policy that exceeds $2.1 million in net gains and that Seeker can find in half a minute using a 2,000-scenario resolution (not available in the demo version).
We also compared Seeker with two different reinforcement learning methods, DQN and REINFORCE. The former proved not competitive for this problem, while the second could ultimately provide a policy that was only mildly worse than the one found by Seeker, but at significantly larger computational costs.
This shows that using Seeker as a policy learner can be highly effective, which is particularly appealing when policies must adhere to certain side constraints to be admissible. It also shows a path to utilizing optimization to achieve superior operational results even at a breakneck pace when starting a full optimization is prohibitively time-consuming: Simply use Seeker offline to learn a policy that then executes online in microseconds with the knowledge that the policy will work robustly as Seeker optimized it for thousands of scenarios.
Do you find applications of optimization solvers like this exciting? Then why are you still using creativity-stifling legacy optimizers? Get in touch and try Seeker for yourself: A license for your free evaluation license is just one email away.