How to avoid having your optimization models rusting?

Question

When designing optimization models for external organizations, I have witnessed the following:

1. We design an optimization model for a given problem.

2. We fine-tune it based on a portfolio of representative instances.

3. The model starts being used in production, it behaves well, providing good solutions in a reasonable time.

4. Over time, the business of the external organization changes, making the portfolio of instances that was used for the fine-tuning no longer representative. The results are now of much lower quality or the optimization takes much too long.

5. Silently the model stops being used.

Which approaches do you use to avoid having the model no longer fit the problem it is trying to solve?

I am mostly interested in approaches that can be applied both to exact solution methods as to heuristic solution methods.

Answer 1

I am in a similar situation, where we mainly solve this by providing the servers on which the algorithms are running. This allows us to frequently monitor the input data and solutions, as well as the user behavior (is the user frequently optimizing and then re-optimizing with some other parameters).

This applies to both exact methods and heuristics.

The behavior often starts to deteriorate when "a given problem" starts to become "a related problem" (as you note in 4).

If we see that clients are almost never running optimization jobs, then we can start to investigate why and maybe even sit down with them and discuss this. It could be that they want simple changes to the problem/algorithm in which case it can be easy to turn a loss into a win.

Often the assumptions made when developing the algorithm have changed (business logic, organisational changes, humans), leaving the algorithm to perform poorly/not solving the problem.

To boil it down, we solve it (with some degree of succes) to:

• Monitor the usage of the algorithm and collect data/statistics
• Dialogue with the end-users and monthly/quarterly status

I am guessing that a lot of Machine Learning code put into production could suffer the same fate as you describe. It might be a place to get good ideas (mental note for myself as well, as I am not an expert on that part)

Answer 2

Here are a couple lessons I've learned over the years on this problem. This is in addition to Tue Christensen's answer--there are lots of reasons your problem can "rust."

First, if you can formulate the problem as an LP/MIP, rather than custom algorithm or heuristic, you'll be able to take advantage of commercial solvers. It doesn't take many years for commercial solvers to get 10X faster. A while ago, we built a Lagrangian Relaxation algorithm approach to solve a particular problem. At the time, it was much better than the commercial tools. However, in several years, that wasn't the case. Our algorithm didn't get much faster, the commercial tools did. This helps prevent slowdowns if you can keep the solver refreshed.

Second, if you did formulate as an LP/MIP, it will be easier to allow the user to add side constraints or increase the size of the model. With a commercial solver, you'll have a better chance of the model evolving with the user and still be able to solve. In the above example, adding a side constraint to our Lagrangian Relaxation approach just didn't work at all.

Of course, with the second idea, you have to prevent your user from getting in trouble-- like by creating 10X more integer variables.

Answer 3

• This applies to Gurobi: I found that solver parameter tuning rarely helps (apart from picking the right method) and generally seem to make Gurobi perform worse when confronted with unusual instances.

• Keeping in touch with users helps obviously. Either by talking to people or by collecting logs (if you have the social skills of an OR practitioner 😉).

• When working on a project I usually develop and test multiple formulations and multiple heuristics. For some applications I let all the promising algorithms run concurrently.

• In general, I avoid timeouts by always generating a heuristic initial solution and using solvers "only" as solution polishing with time limits.

• As a software developer I found that it helps to let users give feedback with the lowest effort possible. This means (A) collecting crash logs, (B) usage statistics and (C) having feedback buttons in your application letting people submit feedback anonymously. There are also several great commercial tools for desktop apps and websites to let you monitor/collect user happiness scores.

• It is crucial that you design the interaction patterns in your app. People prefer to do things, instead of just waiting while the optimization is running. For example, you can start optimization even while users are still entering data/constraints in the background. Or you can start early with a suboptimal solution and provide a better solution later. These things obviously depend on the details of your concrete use case.

Answer 4

• If you have the optimizer run server-side with a web API, then you can easily track how often a problem is sent. Since you are not actually storing the problem data (which may though be relevant in order to improve performance and stay up to date, but that's another question), this should not raise any flags in that company. In fact, they may themselves want to use this as a KPI to see what's going on.
• If you have a desktop application, it depends how it is deployed. I write a lot of apps in C# and use "One-Click" applications, which update automatically when a new version is available. You could write a method that, whenever an update is performed, logs that somewhere. So you can see how many people update to the latest version.

To summarize, it depends on how the application is deployed, but in general I would try to find a measurable proxy for usage. Also, coordinate this with the external company, because IMO they should also be interested in knowing this.