Does creativity emerge from search, as stated in this video?
The Principle of Search and Inference
Search algorithms are by no means new. The entire field of operations research can be viewed as the science of search and deterministic inference. Search is the process of zooming in, making a choice, trying it out, and then shifting the focus elsewhere. Deterministic (sometimes called logic or dual) inference is the opposite process of zooming out, finding that certain choices can never work, and eliminating them from further consideration. The very same principle powers logic programming (think Sudoku playing, where you as a human probably hate instances that require search) and game-playing in AI (alpha-beta search).
Game 2, Move 37
While the memory of Move 37 in Game 2 of AlphaGo vs Lee Sedol is more recent, just ask Gary Kasparov how he felt about another Game 2 Move 37, namely 37. Bishop E4 in his match vs IBM Deep Blue in 1997. I worked at Bell Labs in 1997/1998, and Ken Thompson, who had advised Kasparov, told me how Kasparov would not shut up about this one move. He certainly considered it deep and creative. To the point where he seriously considered the possibility that IBM was cheating. (I later worked with Murray Campbell, one of the creators of Deep Blue, at IBM. He assured me they were not cheating.)
The Missing Spark
So the result of search and deterministic inference can be surprising and appear fresh and unexpectedly neat. But is that creativity?
When talking about intelligence and creativity, there appears to be a missing spark, doesn't it? And indeed, while plain search and deterministic inference certainly work, they can be very inefficient. Intelligence-driven creativity would be expected to do more than just try things and rule out what does not work.
For example, think of an intrepid mathematician who works around the clock, generating ever-new hypotheses and eventually finding one that can be proven. Now, of course, they can come up with a new theorem, but they would arrive there more by tenacity than by genius. A truly gifted mathematician would be expected to have this je-ne-sais-quoi, the uncanny ability to focus their attention on structures that yield interesting new theorems, as if guided by an oracle.
Machine Intuition
Clearly, what traditional search algorithms are missing is intuition. Or, as we computer scientists call it, our traditional algorithms lack the ability to conduct statistical inference. Just look at the standard textbooks on OR and see how little space they devote to branching. But isn't magical search guidance precisely the part that a deterministic Turing machine is missing (NP ?= P)?
This was my starting point in 2007. I wanted optimization algorithms to learn to do better search. When I told my colleagues that I worked on the use of machine learning in OR, I was told I was a fool (the actual words used were harsher) for thinking that a machine could learn to have this magical guidance, because the problems were 'too hard' (nota bene: the same people are now working on ML4OR grants). And indeed, the first results were not great. Learning while solving a problem instance would lead to a more effective search, but it was overall slower because of the computational efforts invested in learning.
So we shifted our attention to offline learning. The question was: Could a machine adapt its search behavior based on the experience of solving similar problems in the past? This approach separated the learning from the solving and allowed us to benefit from our learnings without having to pay for them while solving a problem.
The crucial term in this scientific quest is "similar." Just as in ML, there is also a no-free-lunch theorem in OR: For every algorithmic strategy that works well for one problem instance, there exists another problem instance for which the same strategy is abysmal. So, inherently, we have to start from a distribution of problem instances.
But now we are facing a chicken-and-egg problem: The best way to search depends on the distribution of search situations we encounter, but our search choices also affect the distribution of search situations we will encounter later. We investigated this issue in a paper in 2008 on the accuracy of search heuristics.
The immediate result of this research was that we would not be able to fix a distribution of "typical" search situations and to create a training set to which we could then apply the ML kitchen sink because, as soon as we would let the learned strategies make the choices for us, they would skew the distribution of search situations away from the ones they were trained to handle well. (Ironically, there also exist search strategies that are positively dumb, but that skew the search in such a way that this single-minded way of making choices becomes more and more accurate—read the paper above; it is fun!).
The only feasible approach to learning superior search strategies for us was to learn based on end-to-end search performance. And this gave rise to the idea of building automatic algorithm configurators.
The rest of the story is then very simple: We built configurators that find good default search strategies first, and then we enabled them to tailor the search strategies for the given problem instance at hand by using algorithm portfolios. In total, we won 20 first places at international competitions in this way, so it is safe to say that this approach to augmenting search algorithms with statistical inference works.
Learning to Search
In an effort to overcome the static flavor of offline learning, even when using instance-specific tuning, eventually we built so-called 'hyper-reactive' search algorithms: These are search algorithms that track features of the search itself (how long has it been since we found an improving solution? where do we spend most our search efforts so far?) and then learn how to use these features to adapt their search strategies online.
Using this approach, we won the AI4TSP (think: traveling salesperson with uncertain travel times) competition in 2021. This win (on a problem none of us had ever worked on before) sparked the creation of InsideOpt: We wanted companies and academics to have access to this technology at last.
In October 2023, we launched Seeker 1.0.
As you would expect, the entire idea of the solver is that it gets tuned for your business problems, the instances that you encounter, and for the time that is affordable for you. Why would you care about some industry benchmark you never heard of before, you want to know that the tools you choose work for your problems. When using the tuned Seeker, you now leverage a solver whose search strategies are specifically tailored for your business.
Bridging the Gap
In the 80ies, rule-based systems ruled and people believed that expert systems were the answer. Now the pendulum has swung to the other side and the main efforts are spent on statistical inference. To me, both thesis and antithesis are lacking, and the synthesis is actually quite obvious: We need our tools to leverage deterministic inference, statistical inference, and search. Each play their part, and together they can create incredibly powerful new capabilities where a solver like Seeker can be shipped, tailor itself automatically to your business, while providing robust decision support even under uncertainty.
So what is creativity? In my opinion, it is the ability to efficiently find solutions through the confluence of:
What do you think?
]]>You have probably read a dozen articles like this one, correct? We would not have written this one if we did not think they were wrong. Are you ready for a dissenting view?
The process of standing up an OR solution is frequently described as follows (note that we focus on the technical management and are leaving out the company political context in this article):
Following this process, we conservatively estimate that 50% of projects die before reaching stage (4), 70% before reaching stage (5), and 85% die before they see a year in deployment. With this article, we hope to change that.
The waterfall model above is based on one crucially wrong assumption, namely that your stakeholders know what is needed. They do not, and you cannot really blame them for it either.
Try to write down a comprehensive definition of a house you would consider buying. Chances are, you are not only incapable of working out the trade-offs between your various different objectives, you will likely even forget half of the metrics that matter (or, if you actually engaged in the example, did you list the distance to the nearest supermarket just now?).
Buying a house is one of the most consequential decisions we make in our lives. And we are the experts; we know everything there is to know about our preferences, needs, and priorities. And yet, we do not approach it by writing down an all-encompassing specification first. Instead, we consider our options first and then decide what is a must-have, what is a nice-to-have, and in what regime of quality we are willing to accept what trade-offs between our objectives (100K more for a school district that is rated 7 instead of 5 is okay, but not for 10 instead of 8).
Many people will actually not buy a house right away but first settle on a location and rent there, just to see if it is actually practical and that they did not overlook anything crucial. That is to say, they first test a proxy—not quite the real thing, but an approximation—to learn what actually matters.
And that is why you should not start with an optimization problem definition but a business case. The first thing you need to do is understand what decisions need to be taken, how these decisions are executed, and how they create value or costs for your business, including the risks that they pose.
The middle part of this last sentence is frequently overlooked, so let us say that again: You need to understand how the decisions to be automated are being executed. If you only understand the high-level business value but not the underlying business process, your project will likely suffer the fate of 50% of projects that make it to stage (5) but do not survive the first year in production.
Next, you need to understand the basis for decision-making. What is the baseline, i.e., how are the decisions being taken so far? Based on what information are the decisions being taken? We write 'information' and not 'data' because not all that goes into the decision may actually be available in the form of data. It is extremely important to understand the difference if you want the solutions your OR model provides not to be dismissed as naive and void of an understanding of the industrial context.
After the initial information-gathering stage, it is already time to build a low-cost end-to-end pipeline that connects all inputs all the way to the execution stage. Right away. This initial solution serves two purposes: 1. To see if we can actually fill in all the blanks to connect data with decision execution. And 2. to serve as a basis for experimentation and further information gathering. Consider this your cheap rental unit.
All system components should be staged in this phase, but do not worry about them being pretty (linting, long-term maintenance, etc. are not concerns at this stage). If you are planning to use a cloud service or a deployment service like NextMV to run your optimization, set this up in experimental mode and stand up your service end-to-end, including any outside communication.
In its first instantiation, there does not even have to be any optimization model. You can use a plan created by the baseline to see if you can digitally connect to the execution stage, or, if you add a dummy plan maker to your pipeline, you can have the execution stage ignore the operational plan created and just confirm that it could execute it in principle (if it were a feasible plan). Importantly, use this first system to jot down your first set of data requirements and constraints on the operational plans as imposed by the execution stage.
Now it is time to build and iterate on the optimization module based on an increasingly realistic problem specification. The objective now is to get an understanding of the value entitlement of the optimization as quickly as possible. The process here is as follows: You optimistically assess the value of making better decisions based on optimization while retiring technical risk as quickly as possible. That means, with every iteration on the optimization model, the value assessment should get more and more realistic. If, at any time in the process, the optimistic entitlement assessment drops below a critical threshold, you can stop the project with as little investment lost as possible.
Of course, with traditional mixed-integer problem (MIP) solvers, this is easier said than done. In rare cases, the business problem is quickly formulated as a MIP and then we are done, modulo some late constraints or slight tweaks in the objective as more business requirements reveal themselves. The vast majority of real-world problems will throw curve balls, though. Some important terms in the constraints or the objectives will have non-linear relationships with decision variables. Some data will be estimated and come with uncertainty. There is usually more than one objective function to optimize with non-stationary (i.e., non-linear) trade-offs across their regimes. The list goes on.
Given that we have to expect significant changes to the optimization model definition as we iterate with the business, we cannot spend three months on one iteration and implement an elaborate branch-and-price model or implement our own meta-heuristic solution. If you do that (see the canonical model above), your project will likely end unsuccessfully at stage (3) or (4) after it is discovered that months of development were just invested in a solution to a problem the business does not have.
Modern solvers like InsideOpt Seeker help iterate quickly and learn fast. One advantage of Seeker is its uncanny ability to support experimentation with the problem specification. There are highly expressive modeling concepts available that help accommodate most requirements from the business, including stochastic, non-linear, non-convex, non-differentiable, and multi-objective optimization.
Instead of fearing the next meeting with the business stakeholders and wondering what changes they will want this time that will render much of our work useless, we frequently find that Seeker makes it so easy to change problem formulations that we can even pro-actively experiment with different specifications to help the stakeholders understand some trade-offs better, for example, between risk and expected costs, profit and service quality, inventory and stockouts, etc. In this way, we can engage in a much deeper discussion about what specification will actually create the most business value, unincumbered by the restrictive modeling capabilities of traditional MIP solvers. It is frequently this exchange that creates the buy-in needed to make a project succeed.
Importantly, do not focus on the speed with which your optimization model works, even if time-to-decision is an important factor in the end. The objective at this stage is to find out as precisely as possible what value an automated decisioning process can potentially deliver for the business while gaining an increasingly better understanding of the requirements and targets. At the same time, any co-development that needs to take place on the system, data, or execution side should take place simultaneously in an agile fashion as well.
While iterating, as soon as the problem requirements appear to be understood well enough, we go into shadow mode. That is to say, test as early as possible if the plans created actually work, either in a sandbox or in practice. Depending on the business use case, this can mean simulating a generated plan and comparing it with the baseline and/or actually executing a few optimized plans in real execution. In this way, with as little risk as possible, we assess if our solutions work or if our problem specification needs further refinement.
After maturing our solution and gaining a sound understanding of the real business value that can be materialized, it is time to build a solution that could, in principle, go into production. At this stage, we still iterate on our model, but no longer to incorporate changing business requirements we were not aware of before but to improve optimization efficiency.
We may experiment with different formulations that implement the same problem specification, which will aid the solver in creating high-value plans faster. For a solver like Seeker, this stage typically includes the first automatic tuning of the solver for the specific model that was created. Note that this feature tailors the optimization search for your specific business problem, which includes the time you can allot for the optimization process. Seeker employs different search patterns depending on whether there are 60 minutes or 60 seconds left for optimization. In this way, the machine determines automatically how best to invest whatever computing time you can afford to spend on the optimization.
To improve optimization efficiency, you may also consider running your solver in parallel. Seeker offers true distributed optimization that is not limited by the number of cores on your CPU as are thread-parallel solvers. All that is required to harness parallel compute power for Seeker is to add two integers to your model, one that uniquely identifies your problem and the other that identifies the process that collaborates with others on this same problem. In doing so, you not only gain an easy way to harness as much compute power as is needed, but you also make the solution process resistant to hardware crashes. Seeker will continue its search exactly at the point it was stopped, which makes it easy to recover even after severe machine interruptions.
Note how late in the game the expert optimization work actually takes place. In this way, we avoid building elaborate solution approaches for incomplete or flawed problem specifications. Moreover, right after this step is done, we can be very confident that the resulting solution meets expectations and does not dangle in mid-air, unsupported by data that cannot be provided, compute that cannot be connected, and incapable of being caught by an execution whose requirements we do not meet.
Which means that as soon as we have our optimization model, we can go into production. Directly.
Finally, we deploy our solution, first in Beta, always ready to redeploy the original decisioning process if needed, and then for real. If you are using a deployment service like NextMV, you automatically get options to run multiple optimization models to see if an updated model gives better solutions in shadow mode or to deploy a new model sporadically and send its solutions to the execution step to assess its validity in practice. If you stand up the compute yourself, you will want to add monitoring features as well as model update features yourself to facilitate the ongoing support of the optimization service.
Importantly, make your service as robust as possible. Think about computing sub-optimal but feasible fall-back solutions that can be sent to the execution stage should the full optimization run fail for some reason. The person or department in charge of monitoring the service should always have options to keep the operations running.
In summary, we suggest that you follow this framework:
We wish you good luck with your projects! And of course, if you want help at any stage, we are here for you.
]]>]]>
]]>
Many data science companies aim to leverage machine learning to personalize healthcare. The problem is that probability distributions of the potential causes of the patients' ailments do not create value for healthcare providers. Optimization does. But only when it can handle uncertainty. Can you?
Note: This is a puzzle and not a real case. The situation below is made up and is not based on real data.
AI Health is a startup in DS City. They have created a machine learning model that provides diagnoses based on a natural language description of the symptoms, electronic health records, as well as genetic markers. Unfortunately, no healthcare provider is buying their product. The issue is that the diagnoses provided by AI Health carry more uncertainty than human doctors' assessments after conducting additional tests.
AI Health now wants to overhaul its product. Instead of providing a personalized diagnosis for the patient, they want to provide a personalized test and treatment plan. As this is an actionable insight, it would create tangible value for healthcare providers.
For the optimization, the following data is available:
Based on this data, AI Health wants to provide a personalized test and treatment plan in the form of a tree. Each inner node is associated with a test to be conducted. Depending on the test outcome, we follow the left (negative test) or the right (positive test) branch in the tree. Leaf nodes are then associated with a prescription for the initial treatment.
They show you the example of a patient with lower back pain. The system they already built lists four potential causes and their probabilities for this patient: arthritis (75%), a ligament strain (10%), a genetic skeletal deformation (10%), or a ruptured spinal disc (5%). There are five tests that can be conducted: Arthro ($500), Theanos ($10), DiaFate ($270), URFLT ($280), and Radiol ($300). For each potential cause and test, the matrix below gives the probability (in percent) that the test will come back positive.
You note that no test is perfect and that false positive and false negative rates for the tests fluctuate depending on the real medical issue. For example, when the Theanos test comes back positive, you can say with certainty that the patient does not have arthritis, but there is a 50/50 chance that the patient has a strained ligament.
As for the costs of treatment, the following matrix gives the total treatment costs (in dollars) if a (real) cause is initially treated with one of three available treatments: medication, rehabilitation, or surgery.
These costs reflect the total cost of treatment, including the recovery from initial misdiagnoses and mistreatments. You note that the costs are not symmetric. A strained ligament treated with meds simply incurs the cost of rehab ($1,500) plus the cost of initially prescribed (useless) meds ($1,000). However, arthritis treated with rehab incurs more than the cost of the pharmaceutical treatment plus the initially prescribed rehab, possibly because a delayed medical treatment requires higher dosages or more expensive medicine. You note that the cost of initial mistreatment can be very high. In the case of a ruptured disc that is initially treated with rehab, the costs skyrocket to $14,500, or $10,000 more than the cost of the operation plus the cost of the erroneously prescribed rehab.
AI Health asks you to provide a test and treatment plan in the form of a tree for this patient, which will minimize the total expected costs, which are the sum of the expected test costs and the expected treatment costs.
For each patient, the healthcare provider does not want to conduct more than three tests, and all tests have to be different (on the path from the root to each leaf, in the tree as a whole, you may have duplicate tests and also more than three different ones). This is because the false positive or false negative rate of the tests is systemic and not caused by a faulty application of the test, which is why repeating a test must not increase our confidence in the result.
Can you provide such a cost-efficient test and treatment plan?
Are you confident that your plan is cost-optimal? If you are not, maybe think some more? You can also visit https://colab.research.google.com/ and build a Seeker model to help you find a good plan.
If you are confident that your plan is optimal, can you assess the risk of complications (any treatment cost exceeding $3,500 is considered a complication)? How would you change your plan if it is okay to have expected total costs of up to $2,000 but the risk of complications must be minimized?
One plan with low expected costs is this:
The expected costs of this test and treatment plan are $1746, with expected test costs of $308, and expected treatment costs of $1437. Did you find a better one?
Real-world optimization problems require us to handle uncertainty in data estimates, forecasts, or, as in this case, action outcomes. And yet, most optimization solvers treat uncertainty as an afterthought, thereby severely limiting the ability of practitioners to provide robust decision support. This puzzle perfectly illustrates why looking at a few dozen or even hundreds of 'scenarios' is not enough.
The density of the treatment costs is plotted below (the Seeker model we used to create this analysis is provided at the very end of this article).
The density of complications is so low that we need to zoom in to see the curve.
Note the tiny hump at $14,500. These patients must have a ruptured disc (5%) but receive rehab as initial treatment, which is only possible if the the Radiol test came back negative (1%) and the Theanos test came back positive (20%). The chance of seeing these patients is therefore 5% x 1% x 20% = 1/10,000. And yet Seeker sees these cases and takes them into account in its optimization!
For this test and treatment plan, Seeker assesses the risk of complications at 833/100,000. This implies that 0.8% of patients would encounter complications, potentially very severe complications, as in the example above. We asked Seeker to reduce this risk while keeping the expected costs within $100 of the cost-optimized plan. The result is this revised test and treatment plan:
Its expected total cost is only $65 more than the original plan, but the risk of complications is reduced to 194/10,000. $65 for 75% less risk—that is the power of Seeker.
def ttplan(pID, uID):
env = skr.Env("license.sio", pID, uID, stochastic=True)
env.set_stochastic_parameters(int(1e5), 0)
numberOfTests, nodes, priorTests, numberOfDiseases,
diseasePrior, numberOfTreatments, layers, testProbabilities,
testCosts, treatmentCosts = createInstance()
# decision variables
prescribedTests = [env.categorical(0, numberOfTests-1)
for _ in range(nodes)]
treatments = [env.categorical(0, numberOfTreatments - 1)
for _ in range(nodes)]
phaenTests = [env.convert(numberOfTests-1), prescribedTests[1]]
for i in range(2, nodes):
phaenTests.append(env.if_(phaenTests[i // 2] ==
numberOfTests-1
, numberOfTests-1
, prescribedTests[i]))
# enforce no double-testing
for i in range(2, nodes):
noTest = env.eq(phaenTests[i], numberOfTests-1)
for pr in priorTests[i]:
neq = env.neq(phaenTests[i], phaenTests[pr])
env.enforce(env.or_([noTest, neq]))
# stochastic data
diseaseProb = env.discrete_uniform(0, 99)
disease = env.index(diseaseProb, diseasePrior)
dice = [env.discrete_uniform(0, 99) for _ in range(layers)]
# derived terms
indexOnLayer = [env.convert(1)]
testOnLayer = [phaenTests[1]]
treatment = 0
for k in range(1, layers + 1):
indexOnLayer.append(2 * indexOnLayer[k - 1] + (dice[k - 1]
< env.index(disease, testOnLayer[k - 1]
, testProbabilities)))
if (k < layers):
testOnLayer.append(env.index(indexOnLayer[k]
, phaenTests))
else:
treatment = env.index(indexOnLayer[k]-nodes, treatments)
diagnosticCostsOnLayer = [env.index(testOnLayer[k], testCosts)
for k in range(layers)]
costOfTreatment = env.index(treatment, disease, treatmentCosts)
diagnosticCosts = env.sum(diagnosticCostsOnLayer)
# objective
totalCosts = costOfTreatment + diagnosticCosts
expTotalCosts = env.aggregate_mean(totalCosts)
# cost optimization
env.set_restart_likelihood(0.05)
env.minimize(expTotalCosts, 120)
print("costs", expTotalCosts.get_value())
print("Tests", [t.get_value() for t in phaenTests])
print("Treatments", [t.get_value() for t in treatments])
print(env.get_number_evaluations())
# minimize risk
# constrain expected costs
costBound = 100 + expTotalCosts.get_value()
env.enforce_leq(expTotalCosts, costBound)
print("Cost bound set to", costBound)
# assess risk
risk = env.aggregate_relative_frequency_geq(costOfTreatment
, 3500)
env.evaluate()
print("Risk ingoing", risk.get_value())
# minimize risk
env.minimize(risk, 120)
print("Tests", [t.get_value() for t in phaenTests])
print("Treatments", [t.get_value() for t in treatments])
print(env.get_number_evaluations())
print("costs", expTotalCosts.get_value())
print("risk", risk.get_value())
return
]]>
As winter casts its frosty spell over DS City, 'The Cozy Bean' transforms into a haven for coffee aficionados and a bustling hub where artists and data scientists converge. The Cozy Bean roasts their own coffee, to unique perfection. As rent and labor prices have soared recently, they have turned to you to help protect their profitability. Do you think you can save this beloved hotspot?
[To dive straight into the challenge, you can skip ahead to the section just before the curvy arrow. Be sure not to scroll below it.]
Evelyn, the owner of The Cozy Bean tells you that they usually buy raw coffee at a bargain by procuring coffee that must be roasted in the same week, or it will go bad. She says that they can afford to buy these perishable beans because they have highly limited roasting capabilities and the demand always surpasses their production capabilities anyway. Coffee is therefore roasted just in time and is consumed in The Cozy Bean immediately.
Evelyn goes on to explain that there are two kinds of coffee beans on the market, Amber Harmony (A) and Black Velvet (B). Both cost the same, $500 per standard coffee unit (SCU). Both bring the same revenue, $5,000 per SCU. And both have the same expected roasting time of 10 hours per SCU, which is the only limiting factor for production. They can only roast for 60 hours each week and this limit cannot be extended as this would require a different business license.
You listen intently as she goes on to elaborate that the only difference between the two coffees is how their roasting times vary, based on how dry the beans are to begin with. Dryer beans roast faster, whereas wetter beans take longer.
For production reasons, roasting times are always full hours. When you ask if Evelyn has any data available on the roasting times, you're impressed to find that she has a spreadsheet going back two years. For every week, she noted down how long roasting took for the coffee that had been bought for that week.
As you investigate the data, you notice that Amber Harmony's roasting times per SCU seem to vary normally around 10 hours (always rounded to the nearest integer) with a standard deviation of 2 hours, while Black Velvet has a minimum roasting time of 8 hours plus some additional time that varies in accordance with a Poisson distribution with lambda 2, which implies that the expected roasting time is also 10 hours and varies with the same standard deviation of 2 hours as Amber Harmony.
You denote the randomized roasting time for Amber Harmony with R(A), and the randomized roasting time for Black Velvet with R(B). Then, the production planning problem, where you determine how much of each coffee A or B to roast, is a simple linear program:
Maximize 5,000 A + 5,000 B
Such that
A R(A) + B R(B) <= 60
with 0 <= A <= Q(A) and 0 <= B <= Q(B)
Whereby Q(X) is the quantity of coffee X that Evelyn bought for that week.
"But here is the problem," Evelyn laments, "I do not know which coffee I should buy. The roasting times only become clear once roasting starts, making production optimization straightforward then. But when I purchase the beans, those times are unknown." Evelyn looks desperate. "But with our fixed costs now at $20,000 per week, I'm worried for The Cozy Bean's future."
Resolved to assist Evelyn, you refine the problem statement. Now, the primary decision is about the quantities of each coffee type to purchase, while the production amounts A and B will be set optimally later.
Maximize Expected Profit = Expected Revenue - 500 (Q(A) + Q(B)) - 20,000
Such that Revenue = Maximum 5,000 A + 5,000 B
s.t. A R(A) + B R(B) <= 60
with 0 <= A <= Q(A) and 0 <= B <= Q(B)
R(A) ~ Round(Norm(10, 2))
R(B) ~ 8 + Pois(2)
0 <= Q(A), Q(B) [fractions of SCUs are allowed]
Is one coffee better than the other? Or is there no difference, as the expectation operator and all terms are linear, and both mean and standard deviation for both types of coffee are the same anyway? What should Evelyn purchase?
Grab a coffee and think some more?
To maximize her expected profits, Evelyn should purchase 5 SCUs of Amber Harmony and 3.33 SCUs of Black Velvet. Her expected profit is then $7,210.
This result is counter-intuitive in many ways.
At first, Black Velvet appears disadvantageous because its minimum roasting time is 8 hours, while Amber Harmony may frequently roast in less than 8 hours. Plus, the Poisson-distributed Black Velvet runs a significant risk that the roasting times could be much, much longer than 10 hours, while the risk that the normally-distributed Amber Harmony needs very long roasting times declines exponentially.
As it turns out, if we were to choose just one coffee, Black Velvet would actually be the better choice, with an expected profit of $6,800 per week when purchasing 7.5 SCUs (the best we can do with Amber Harmony is $6,657 when purchasing 8.6 SCUs of that coffee). The reason why Black Velvet offers better profitability is because its probability mass for roasting times of 8 or 9 hours far exceeds that of Amber Harmony.
But why then is it not best to buy only Black Velvet? Because the coffee is so cheap that we can buy more than we will use. The solution above procures 8.33 SCUs of coffee, when, on expectation, we can only roast 6 SCUs. This provides a cushion that allows us to react once we know the roasting times of both coffees and then to roast more of the coffee that is dryer. But this strategy requires both coffees to be available.
Automated Decision Support
Decision-making under uncertainty is often counter-intuitive and the best course of action may be very surprising. Thankfully, you have help in the form of InsideOpt's Seeker. Here is the Seeker model for our problem above:
import seeker as skr
coffee = ['Amber Harmony', 'Black Velvet']
# Create a stochastic Seeker Environment
env = skr.Env("license.sio", True)
# Declare the decision variables
Q = {c: env.continuous(0, 10) for c in coffee}
# Set up the nested LP
# Revenue coefficients
lpObj = env.convert([5000, 5000])
# Maximum production
lpVarBounds = [env.convert(0), Q['Amber Harmony']
, env.convert(0), Q['Black Velvet']]
# Maximum roast time
noBound = env.convert(-1e5)
lpRowBounds = [noBound, env.convert(60)]
# Stochastic roast time constraint
R = {'Amber Harmony': env.max_0(env.round(env.normal(10, 2)))
, 'Black Velvet': 8 + env.poisson(2, 1e20)}
lpMatrix = [list(R.values())]
lp = env.lp(lpObj, lpVarBounds, lpRowBounds, lpMatrix, True)
# Enforce LP feasibility and optimality
env.enforce_eq(lp.get_solution_status(), 1)
# Compute profit and expected profit
revenue = lp.get_objective()
profit = revenue - 500 * env.sum(list(Q.values())) - 20000
expProfit = env.aggregate_mean(profit)
# Maximize expected profit
env.maximize(expProfit, 60)
# Write the solution
print("Buy Decisions", [Q[c].get_value() for c in Q])
print("Exp Profit", expProfit.get_value())
Buy Decisions [4.9997395442476105, 3.3346340091727367]
Exp Profit 7209.505947287972
As you can see, it is very easy in Seeker to formulate a nested LP optimization. What is more, notice that the nested LP in this case depends on both the outer decision variables Q as well as stochastic data in its maximum roast time constraint.
Risk Management
We built Seeker to make better decisions under uncertainty. However, the real value of this new solver lies in the ability to spend less time on solving problems and more time on discussing what problem should be solved. In this particular scenario, we Insiders would definitely suggest considering the risk of running a very low profit in a given week, especially if Evelyn's cash flow is tight.
Let us use Seeker to have a look at the variability of the profit:
import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
dat = profit.get_values()
datdf = pd.DataFrame([max(0,k) for k in dat], columns=["profit"])
ax = sns.kdeplot(x=datdf["profit"], log_scale=False)
sns.kdeplot(data=datdf, fill=True)
plt.show()
As the distribution of our profit shows, there is a good chance that Evelyn will be very lucky and make in excess of $10,000 in some weeks. However, there are also weeks when profits are very low or where she might even encounter a (temporary) loss.
We can ask Seeker to tell what risk Evelyn runs of making less than $1,000.
risk = env.aggregate_relative_frequency_leq(profit, 1000)
env.evaluate()
print("Risk <= $1,000:", risk.get_value())
Risk <= $1,000: 0.04056
Simultaneously Optimizing Risk and Profit
A 4% chance of having a low-profit week is not great but acceptable for Evelyn. She asks how much it would cost to lower the risk. We inquire what levels of risk and profit she considers fair and excellent. She replies that a risk of running a low profit of 3% and an expected profit of $5,000 would be fair while 1% risk and $8,000 expected profit would be excellent. We enter these values in Seeker's multi-objective optimizer:
env.multi_objective([risk, expProfit] # Objectives
, [0.03, 5000] # Fair Levels
, [0.01, 8000] # Excellent Levels
, [False, True] # Min Risk, Max Profit
, 60 # Time Limit
)
print("Reduced Risk", risk.get_value())
print("Buy Decisions", [Q[c].get_value() for c in Q])
print("Exp Profit", expProfit.get_value())
env.end()
Reduced Risk 0.01618
Buy Decisions [2.804282004443563, 4.914618222403016]
Exp Profit 7191.540962722829
Note how Seeker found some excellent value by reducing the overall amount of coffee from 8.33 SCUs to 7.71 SCUs while increasing the amount of Black Velvet by almost 50%. This costs Evelyn a meager $18 in expected profits, but reduces her risk by more than 60%! The probability to achieve a profit of $1,000 or less falls from 4% to 1.6%. Seeker is able to find such favorable trade-offs and thereby enables stakeholders to engage in a meaningful conversation about the appropriate levels of risk vs. rewards.
The Future of Optimization
Distributions of estimated data matter tremendously when making decisions under uncertainty. Even for small problems, point-forecasted MIP models are frequently 8-40% sub-optimal when compared with Seeker.
Stochastic optimization that simply replicates the deterministic model for 50-100 scenarios is insuffient for real-world applications.
Be skeptical when a salesperson tells you their solver provided provably optimal solutions. A near-optimal solution to a realistic world model is almost always superior to an optimal solution to an approximated model --- such as any model that used point forecasts and ignores all uncertainty.
Be Part of This Future
Are you ready to try Seeker for yourself? Test our limited demo version:
Go to https://colab.research.google.com/ and open a new Python Notebook
pip install insideopt-demo
import seekerdemo as skr
env = skr.Env() (or env = skr.Env("", True) for a stochastic environment)
The Seeker Documentation and a Seeker GPT can be found here.
]]>We hope this addition will make it easier to create models with Seeker. Obviously, LLMs are LLMs and do occasionally get carried away with their own world view, which may deviate from reality.
That is why we recommend always consulting the official documentation as well.
Have fun creating Seeker models!
PS: The image you see is DALL-E's visual interpretation of Seeker based on the GPT we built!
]]>We OR folks believe we support making better decisions. Do we?
If the thesis were correct that canonical OR (which is deterministic optimization) would lead to better decisions in practice, then more than the largest companies would use the technology.
They are not. Even the S&P500 companies only use OR for select applications, usually for transportation and logistics operations as well as revenue management. Our analysis is that traditional OR does, in fact, frequently lead to profit lost instead of profit gained.
Take the airline industry. As one of the early adopters of OR, and an avid investor in the technology, this industry is hardly thriving. Why is it that one-aircraft airlines often find a strong foothold in the industry (see the beginnings of any younger airline) while large airlines, with tons of synergetic potential that OR is supposed to leverage, are frequently struggling and always seem just one winter storm away from Chapter 11?
The inconvenient truth is that deterministically optimized operational plans look awesome on paper. They are even provably optimal. And yet, operational performance is lacking. Why? Obviously, because the future for which we optimized our plans was not the future that then happened. The plans we made were too brittle. They did not hold up in reality.
Alas, airlines lose their shirt not on paper but on the day of operation.
Why are MIP-optimized plans so brittle? Take this post. It describes the canonical view of machine-learning-to-operations-research (ML2OR) pipelines:
Where is the gap, you ask? It is quite simple, actually. In the above 4-step failure recipe, note how all uncertainty magically vanishes between Step 1 and Step 2. However, uncertainty cannot be solely dealt with in the predictive step. They must be considered in the optimization itself to obtain operational plans that hold up under real-life deviations from arithmetic mean expectations.
This is why we built InsideOpt Seeker. It is the first general-purpose stochastic optimization solver that allows you to optimize your plans efficiently against tens of thousands of scenarios. Why that many? Because a daily event that can occur with 0.3% probability will, on average, happen once a year. And you want operational plans that are robust. You want your risks mitigated. And you want to understand how risk minimization trades against expected KPI performance.
Your Success Recipe
Your first step:
Go to insideopt.com and pip install insideopt-seeker.
]]>https://www.reaktor.com/events/event-data-to-revenue
]]>DS City is known for its fine meats, but no company makes better sausages and roasts than The Roast Busters. They have come to you to seek your help on a seemingly easy task that is part of any introductory lesson in operations research: a simple production planning problem with two products and two side constraints. Surely you can do that, can't you?
The Roast Busters only make two products: sausages (S) and roasts (R). They employ five skilled workers who each work 4 hours per day on meat preparation and can produce a sausage with a hands-on effort of 1 minute and 12 seconds and a roast with 8 minutes of manual labor. They also have 25 "Sloth Pots" which are their secret to producing the most tender meats. The Sloth Pots run 24 hours per day. A sausage needs to slow-cook in a Sloth Pot for 24 minutes, a roast for 288 minutes (yes, they follow their recipes this precisely!).
You note down the side constraints for your optimization:
where Q_S is the number of sausages produced and Q_R is the number of roasts. So simple, just as in the very first OR course you took! Your ship starts to sink when you ask about the corresponding profits and maximal demands.
"Those are for you to figure out!" the Roast Busters tell you. You have to set the prices. The cost to produce a sausage is $1.30, and the cost of a roast is $6.00. We also know about the price sensitivity of Roast Busters customers (P_S is the price in dollars for a sausage, P_R the price in dollars for a roast):
The only thing you spot is that the first side constraint means that we can never produce more than 1,000 sausages and that we should therefore never ask for less than $3.33 for a sausage. But how are you going to find the optimal prices and production quantities for both products?
________
Scroll down for a bonus question and the solution!
Bonus question for the truly stellar operations researchers: How would you set the prices and production quantities when the customer demand varies around the estimate following a normal distribution with a standard deviation of 10% of that estimate (where the variability is independent for each product)?
Scroll down for the solution!
When you only have access to a linear solver, a typical way to handle a problem like this is as follows: First, we determine the profit-maximizing prices for our products, taking only maximum production levels into account. We find that taking $3.33 for sausages and $23 for roasts is optimal (analytically minimize (160-4x)*(x-6) for the latter using the first and second derivations). We set up a linear program using these prices and the corresponding demands of 1,000 sausages and 68 roasts. The optimal production levels we then get are 546 sausages and 68 roasts. We finally hand these numbers to our revenue management department, which keeps the cost of roasts at $23 but increases the price of sausages to $3.63 without lowering the expected demand below the 546 sausages we said we were going to produce. Our total profit based on this common procedure is $2,428.18.
Rather than solving the problem piecemeal as above, a better way to get to a solution is by employing a non-linear solver like InsideOpt Seeker(TM).
Maximize T_S * P_S - Q_S * 1.30 + T_R * P_R - Q_R * 6
such that
using the true sales variables T_S and T_R. This leads to prices P_S = $3.53 and P_R = $28.75 and production levels Q_S = 700 sausages and Q_R = 45 roasts. Our total profit is now $2584.75 per day, 6.45% more profit than the linear programming solution.
Not bad, but in reality our demands estimates come with some level of uncertainty. Traditional solvers fall short entirely as soon as our demand forecasts become stochastic. In the bonus question, the demands could vary normally with a standard deviation of 10% up or down from the demand estimate. For this case, InsideOpt Seeker(TM) suggests keeping the production levels the same (Q_S = 700 sausages and Q_R = 45 roasts) but lowering the prices slightly: P_S = $3.48 and P_R = $28.62. With these settings, Seeker assesses the expected profit to be $2,477.48—still a solid percent ahead of the solution of the linear programming approach when there is absolutely no variability in demand. However, there is variable demand, and the LP solution drops in expected profit to $2300.63 when the demand varies. That is 7.69% below the Seeker(TM) solution.
Can you really afford to continue using suboptimal optimizers?
For your interest, see the complete Seeker(TM) model for the stochastic bonus case below.
import seeker as skr # Create a Seeker Environment env = skr.Env("Seeker_Licence.sio", stochastic=True) env.set_stochastic_parameters(round(1e6), 0) # Create the Decision Variables price = [env.ordinal(1, 400) / 100, env.ordinal(1, 4000) / 100] quantity = [env.ordinal(0, 3000), env.ordinal(0, 300)] # Add Constraints env.enforce_leq(72 * quantity[0] + 480 * quantity[1], 72000) env.enforce_leq(24 * quantity[0] + 288 * quantity[1], 36000) # Derive Demand Values from the Prices demand = [env.max_0(6000 - 1500 * price[0]), env.max_0(160 - 4 * price[1])] noise = [env.normal(1, 0.1) for _ in range(2)] unc_demand = [demand[i] * noise[i] for i in range(2)] exp_demand = [env.aggregate_mean(unc_demand[i]) for i in range(2)] # Compute the True Sales Numbers sold = [env.min([unc_demand[i], quantity[i]]) for i in range(2)] # Compute the Resulting Profit cost = [1.3, 6] profit = [sold[i] * price[i] - cost[i] * quantity[i] for i in range(2)] exp_profit = [env.aggregate_mean(profit[i]) for i in range(2)] exp_total_profit = env.sum(exp_profit) # Optimize for 60 Seconds env.maximize(exp_total_profit, 60) # Extract the Solution print("Expected Profit", exp_total_profit.get_value()) print("Price", [price[i].get_value() for i in range(2)]) print("Quantity", [quantity[i].get_value() for i in range(2)]) print("Demand", [demand[i].get_value() for i in range(2)]) print("Evaluations", env.get_number_evaluations())
This program creates the output:
Expected Profit 2477.4831316738547
Price [3.48, 28.62]
Quantity [700.0, 45.0]
Demand [780.0, 45.72]
Evaluations 217945
As usual, we can also visualize how this expected profit is distributed:
We can also ask Seeker(TM) what the likelihood of a profit lower than $2,000 is, which it assesses at 1.85%. If The Roast Busters are fearing a cash flow problem, we can also ask Seeker(TM) to, e.g., minimize the risk of ending up with less than $2,000 while enforcing that the total expected profit remains at least $2,400.
# Add Risk Term and Constrain Objective risk = env.aggregate_relative_frequency_leq(2000, env.sum(profit)) env.enforce_geq(exp_total_profit, 2400) # Optimize for 60 Seconds env.minimize(risk, 60)
Expected Profit 2400.7260870068135
Price [3.33, 29.31]
Quantity [720.0, 42.0]
Demand [1005.0, 42.760000000000005]
Risk 0.001066
We note that Seeker(TM) lowers the price of sausages by about 5% but increases sausage production only mildly. By leaving a larger gap between production and expected demand, we obviously lower our opportunity, but we also run a lower risk of overproduction, which would cut into our profit. Overall, the risk of ending up with a profit lower than $2,000 is now down from 1.85% to 0.107%. That is a 17-fold reduction in risk, which costs us, on expectation, $77.
We built Seeker(TM) so that you can sculpt the risk profile of your operational plans to fit your business objectives. Please reach out to one of our specialists if you want to learn more about Seeker(TM). Or do you prefer butchering your business problems until your current solver can handle the pieces?
Two main players in the fruit industry are seeking to increase their sales in an overall growing market. The incumbent is Amazing Apples Inc.; the up-and-coming fruit company is Better Bananas LLC. Better Bananas has hired your firm to optimize their marketing campaign. But beware: marketing is madness, and you are bound to be surprised!
Better Bananas has designated $500,000 for their campaign. They are targeting three different age groups: TikTokers (T, under 30), Hashtaggers (H, 30–50), and SilverSurfers (S, over 50). Now they need to decide how to distribute their budget to these groups in increments of k = $50,000. The problem is that when they launch their campaign, they are sure that Amazing Apples will counter with their own campaign. And Amazing Apples has deep pockets; they can spend $1 million on their own marketing campaign.
Each company is only aiming to maximize its own sales; there is no incentive to hurt the sales of the other company. However, by marketing its own product, each company inadvertently diminishes the effect of the other's marketing.
Let us denote the marketing spend per age group G by company X with X_G (e.g., B_T for Better Bananas' spend on TikTokers or A_S for Amazing Apples' spend on SilverSurfers). Moreover, recall that k = 50,000.
Then, for Better Bananas, the expected growth in sales is given by this formula:
Bananas [in thousand pounds] = 300 * B_T/(A_T+k) + 350 * B_H/(A_H+k) + 400 * B_S/(A_S+k)
The formula for Amazing Apples is:
Apples [in thousand pounds] = 250 * A_T/(B_T+k) + 500 * A_H/(B_H+k) + 750 * A_S/(B_S+k)
The only additional information we have is that Better Bananas cannot spend more than $300,000 on any one age group, while Amazing Apples can spend at most $500,000 on any individual age group. After these maxima are reached, no further increase in sales is to be gained.
The simple question for you is: How much money should Better Bananas allocate to each age group? You have 10 tokens of $50,000 each to distribute and cannot allocate more than 6 tokens to any one age group.
____________
Scroll down for the solution.
___________
Maybe think a bit more? The solution is not obvious.
The optimal allocation is $50,000 to TikTokers, $150,000 to Hashtaggers, and $300,000 to SilverSurfers. The optimal reply by Amazing Apples then is to allocate $500,000 to TikTokers and an equal amount to Hashtaggers. With these allocations, we are expecting an increase in sales of 2.52 million pounds of bananas and 2.5 million pounds of apples.
Better Bananas' designation of $300,000 to SilverSurfers will not surprise, as the marketing spend on this age group leads to the largest increase in sales (the biggest bang for the buck). But why is it not optimal to spend the entire remaining $200,000 on the Hashtaggers?
The answer is simple: If we were to allocate $200,000 to the Hashtaggers, then it would be better for Amazing Apples to compete with us in the SilverSurfer than in the Hashtaggers age group. Particularly, Amazing Apples' optimal allocation of their $1 million would then be to spend $500,000 on TikTokers and the same amount on SilverSurfers. This would lead to increased sales of only 1.61 million pounds of bananas and a whopping 3.57 million pounds of apples (where the primary sales driver is that they have no competition marketing TikTokers).
Therefore, by deliberately lowering our marketing spend in the Hashtaggers segment, we leave enough room for Amazing Apples to invest here instead of in the SilverSurfer segment, which we care more about. Stated simpler: don't go bananas with your marketing.
This example shows how our business results can depend on the actions of other players who are not necessarily antagonists but who pursue their own objectives. There are many surprising and often counterintuitive effects that can occur in such a setting. Thankfully, InsideOpt Seeker(TM) can model these problems with ease. Below, you will find the complete model for this problem.
1 import seeker as skr 2 3 env = skr.Env("Seeker_License.sio") 4 k = 50000 5 investments_B = [env.ordinal(0,6)*k for _ in range(3)] 6 obj_A_const = [250, 500, 750] 7 obj_A = [ obj_A_const[i]/(investments_B[i]+k) for i in range(3) ] 8 var_bounds = env.convert([0, 10*k, 0, 10*k, 0, 10*k]) 9 row_bounds = env.convert([0, 1000000]) 10 matrix = env.convert([[1,1,1]]) 11 opt_model_A = env.lp(obj_A, var_bounds, row_bounds, matrix, maximize=True) 12 solution_A_value = opt_model_A.get_objective() 13 investments_A = opt_model_A.get_solution() 14 obj_B_const = [300, 350, 400] 15 env.enforce_leq(env.sum(investments_B),500000) 16 obj_B = env.sum([ obj_B_const[i] * investments_B[i] / (investments_A[i]+k) for i in range(3) ]) 17 18 env.maximize(obj_B,1) 19 20 print("Investments B:", [investments_B[i].get_value() for i in range(3)]) 21 print("Extra Bananas [1,000 pounds]:",obj_B.get_value()) 22 print("Investments A:", [investments_A[i].get_value() for i in range(3)]) 23 print("Extra Apples [1,000 pounds]:",solution_A_value.get_value()) 24 print("Evaluations:", env.get_number_evaluations())
Note that, in Seeker(TM), you can specify terms that conduct their own separate optimization. In Line 11, we specify a linear programming optimization model that expresses that Amazing Apples is pursuing its own separate objective function, which itself depends on our investment decisions. We obtain access to the optimal investment decisions from Amazing Apples in Line 13.
After optimizing our own objective for 1 second in Line 18, we obtain this output:
Investments B: [50000.0, 150000.0, 300000.0]
Extra Bananas [1,000 pounds]: 2522.727272727273
Investments A: [500000.0, 500000.0, 0.0]
Extra Apples [1,000 pounds]: 2500.0000
Evaluations: 45405
Overall, thanks to Seeker(TM), we increased the effectiveness of our campaign by over 55%. Not bad for a day's work!
]]>
You work at SafeData LLC in DS City. You were hired as a consultant by LastDrop.com, a drop-shipper. They have gathered some data on their operations, and they are perplexed by what they found. Can you help them?
LastDrop.com operates a big warehouse near the port where ample supplies of all products are always available. They also rent space in a smaller warehouse in the Minsky Midlands that gets supplies from the large central warehouse.
They sell two products, AceAir and BreezeBox, that directly compete with each other. LastDrop.com has a stellar data science team and an operations research team that is the envy of the industry.
The data science team has considered the following weekly sales data for the two products in the Minsky Midlands for the past three years:
Format: weekly units sold [AceAir BreezeBox]
[100 10] [9 101] [11 99] [11 99] [10 100]
[9 101] [10 100] [11 99] [9 101] [11 99]
[10 99] [11 99] [10 100] [9 101] [10 100]
[10 100] [10 100] [99 11] [8 102] [10 100]
[9 101] [11 99] [11 99] [12 98] [12 98]
[9 101] [12 99] [99 11] [8 102] [9 101]
[100 10] [9 101] [101 9] [9 101] [9 101]
[12 99] [11 99] [9 101] [11 99] [9 101]
....
[9 101] [10 100] [ 11 99] [10 100] [9 101]
[9 101] [11 99] [12 98] [11 99] [ 9 101]
(Notice that there is no seasonality, it is always hot in the Minsky Midlands.)
Based on their data, they found that the expected weekly demand for AceAirs in the Minsky Midlands is 19 units per week, whereas the expected demand for BreezeBoxes is 91 (as it turns out, these expected values are exactly correct).
They have a truck that runs from the central warehouse to the regional warehouse weekly and that can transport 110 units at most. If they run the truck, it costs them $350. In return, it costs $10 less per AceAir unit to ship from the regional warehouse, and for BreezeBoxes they still save $5 per unit when compared to shipping from the central warehouse, which they can always do if there is more demand than local supply. On the other hand, if not all relocated units sell, they incur additional inventory holding costs of $3 for AceAirs and $2 for BreezeBoxes at the local warehouse.
The OR team did the math based on this data and found that shipping 19 units of AceAir and 91 BreezeBoxes was provably optimal, with an expected cost of $350 compared to $645 when not relocating inventory.
LastDrop.com has been relocating inventory for a year. Now, due to some bridge closures followed by a truck driver strike, they have not been able to run the truck for the past 4 weeks. To their astonishment, instead of the expected 85% increase, they found that their operational costs went up by a mere 15% when compared with the average operational costs for the prior year. The demands for the past four weeks were [9 101] [10 100] [11 99] [10 100].
Now, the strike is about to end, and the bridges are open again. They have asked you to shed light on the matter. Should they resume the truck runs? And if so, how many units of each product should they ship?
____________
THIS IS A HARD PROBLEM - SCROLL DOWN FOR A HINT
____________
____________
Hint: Look at the sales data again. Do you notice the shift in demand between the two products in some weeks?
[10 100] -> [99 11] -> [8 102]
Out of the 50 weeks given here, this happens 5 times, so with 10% probability. Simplify the problem by assuming that sales are either [10 100] (with 90% probability) or [100 10] (with 10% probability). In this simplified setup, you should now be able to make an optimal shipping recommendation.
SCROLL DOWN FOR SOLUTION
____________
The company should resume shipping and relocate 10 AceAir units and 100 BreezeBoxes to the regional warehouse weekly.
Optimization based on expected values has an overfitting problem
Note that the data science and optimization departments at LastDrop.com did a perfect job: the expected demand for AceAirs is 19, and 91 for BreezeBoxes. And for the scenario where this correct demand forecast is exactly met, shipping the corresponding number of units is indeed provably optimal. The problem is: This forecasted mean scenario never happens.
Looking at the sales data, we see that the demand is bimodal: There is a high 90% chance that consumers will ask for ~10 AceAirs and ~100 BreezeBoxes, but in some weeks (with 10% probability) the demand is exactly reversed. And this variability makes all the difference because it means that the optimization overfits a scenario that has almost no chance of materializing. So much for provably optimal solutions when any data in the model is estimated!
Truly optimal solutions must take the variability into account
To address this problem, the DS and OR teams at LastDrop.com should have handled the integration of their respective components better. Instead of providing just the expected demands, the DS team should have provided an estimate of the distribution of demand. The OR team, on the other hand, should have used a stochastic solver like InsideOpt Seeker(TM) instead of plain mathematical programming.
By the way, in this example, the solution provided by the LastDrop.com teams incurs average operational costs of ~$520 (not $350 as hallucinated when overfitting the mean scenario in the perfectly deterministic world of integer programming), compared with ~$645 when not shipping at all (FYI, there are even problem instances for which not shipping at all is actually more cost-efficient than the 'optimized' solution based on mean estimates, while the stochastic solution provides significant savings). The fact that LastDrop.com's operational costs went up by a mere 15% in the past four weeks is due to the fact that they did not encounter an inversion of demands in this time period. When no inversion occurs, their operational cost is only ~$600.
The optimal stochastic solution, on the other hand, incurs average costs of ~$465 (including the 10% possibility of inversions). That means 10.5% operational savings for your client, not bad!
The next time you see a significant difference between the optimized solution value on paper and your actual operational costs (you are comparing these regularly, aren't you?), you will want to have a word with your DS and OR teams - and maybe reach out to one of our experts at InsideOpt!
In case you are curious, here is the InsideOpt Seeker(TM) model for this problem:
def main(): truck_capacity = 110 truck_costs = 350 inventory_costs = [3, 2] shipping_costs = [10, 5]
# create Seeker environment with path to license and
# set stochastic resolution to 10^6
env = Env("Seeker_License.sio", stochastic=True) env.set_stochastic_parameters(round(1e6), 0)
# create stochastic vector based on historical data
demand_model = Demand() demands = env.user_vector_distribution(demand_model)
# create decision variables: decision to relocate, and shipment quantities
relocate = env.categorical(0, 1) ship = [env.ordinal(0, truck_capacity), env.ordinal(0, truck_capacity)]
# define realized shipment quantities
real_ship = [env.min([relocate * truck_capacity, ship[i]]) for i in range(2)]
# enforce truck capacity
total_ship = env.sum(real_ship) env.enforce_leq(total_ship, truck_capacity)
# compute excess and shortage
excess = [env.max_0(real_ship[i] - demands[i]) for i in range(2)] shortage = [env.max_0(demands[i] - real_ship[i]) for i in range(2)]
# compute the costs
local_inventory_costs = [excess[i]*inventory_costs[i] for i in range(2)] central_shipping_costs = [shortage[i]*shipping_costs[i] for i in range(2)] relocation_costs = truck_costs*relocate costs = relocation_costs + env.sum(central_shipping_costs) + env.sum(local_inventory_costs) expected_costs = env.aggregate_mean(costs)
# minimize expected costs for half a minute
env.minimize(expected_costs, 30)
# report results
print("Estimated Costs:", expected_costs.get_value()) print("Relocate:", relocate.get_value()) print("AceAir:", real_ship[0].get_value(), " BreezeBox:", real_ship[1].get_value()) print("Evaluations:", env.get_number_evaluations())
# end the environment
env.end()
The Result:
Estimated Costs: 457.972692
Relocate: 1.0
AceAir: 10.0 BreezeBox: 100.0
Evaluations: 34164
We can also ask Seeker(TM) to return the density of the stochastic 'costs' variable by calling 'costs.get_values()' and plot it using seaborn:
In this way, we get a better understanding of the risks we run in our operations when executing an optimized plan. Do your operational plans come with such a risk profile?
Please reach out to one of our specialists at info@insideopt.com if you want to start using OR technology of the 21st century!
]]>The AI4TSP Competition is trying to foster research on the intersection of optimization (addressing the first issue of efficient computation for hard problems) and artificial intelligence (addressing the issue of handling uncertainty). TSP stands for Traveling Salesperson Problem, one of the most studied routing problems in the optimization community. The task is to determine the order in which to visit a given set of locations, starting from, and returning to, a given home location, such that the total travel time is minimized. In its original form, the travel times between all locations are known upfront. In the competition, these times were not known but sampled according to a probability distribution. The objective was to visit as many locations as possible within a given period of time, whereby each location was associated with a specific reward. To complicate matters further, the locations that were visited on the tour had to be reached within fixed time windows. Arriving too early meant having to wait until the location would open, arriving too late was associated with penalties.
When travel times are known, the problem looks innocent enough. However, consider this: The number of possible tours grows more than exponentially and is given by “n! = 1 * 2 * 3 … * n” (n factorial) for a problem instance with n locations. If we could evaluate, in parallel, one potential tour for every atom in the universe, and each atomic processor could evaluate the tours at Planck time, which is the shortest time unit that anything can be measured in, and we run that computer from the Big Bang until today - then we could not even enumerate all solutions for just one TSP instance with 91 locations. The biggest problems at the competition had 200 locations - with over 10 to the power of 375 potential solutions.
The competition consisted of two tracks. In the first, we had to determine a tour for a given TSP instance that would work well on expectation when averaged over all possible travel time scenarios. That is to say: A tour had to be chosen, and then we had to stick to that tour no matter how the travel times turned out when executing the tour. The results were then averaged ten times over 100,000 scenarios to determine the winner.
In the second track, we were allowed to build the tour on the fly. At every location, we could choose which location we were to go to next, taking into account how much time had already elapsed. The policy that determined how to choose the next location was evaluated on 100 travel time realizations for each of 1,000 different TSP instances to determine the winner.
InsideOpt optimization expert Dr. Meinolf Sellmann collaborated with Prof. Dr. Kevin Tierney, Dr. Tapan Shah at GE Research, Fynn Schmitt-Ulms, and Andre Hottung from the University of Bielefeld to compete and win 1st Prize in both tracks.
Congratulations, Meinolf and Team!
]]>