How do we decide/plan an SLA for an NP-hard optimization process running in production?

Question

How do you decide or plan an SLA (Service Level Agreement) for an application that depends on an optimization process when the problems you deal with are NP-hard?

That is, if you are developing an optimization application that is integrated with other applications (execution, reporting, etc...) and you want to be able to guarantee that the scheduled optimization calculations are complete within a certain time frame, how can you guarantee a time frame if your problem is NP-Complete or NP-Hard, and therefore you cannot know beforehand how long it will take the solver to reach an optimal solution?

For example:

• You have an inventory optimization problem that is NP-hard, for a company that deals in 50000 products.
• You have designed an application to find the optimal inventory purchases and allocations using a suitable solver + modeling language + user interface.
• This optimization application feeds the optimal inventory decisions to an ordering system which then sends out the orders to suppliers and vendors.
• This optimization process runs on a weekly or daily schedule and needs to be completed within a certain time frame every time it runs, because it needs to synch up with the rest of the company's financial and ordering systems, and the orders need to go out on a regular cadence.

How can we time box the solver's running time, since there is a possibility that every now and then the instance that it is provided is a hard one and it takes an inordinate amount of time to find the optimal solution?

Do we just put a stopping criteria that says stop after x hours, and deliver whatever best solution you have at that point?

Do we "plan ahead" and make sure that ample running time is planned for and throw ridiculously large amounts of compute resources to make sure that it always completes?

Answer 1

Another approach is to include both an exact algorithm (e.g., MIP solver) and a very fast heuristic. If the exact algorithm times out, you can compare its best solution with the solution from the heuristic and return the best one. The advantage of this approach is that the heuristic can be tailored to your specific problem, and therefore might have a better chance of finding a good solution than the MIP solver, which may be finding feasible solutions "by accident."

Of course, the downside is that now you have two algorithms that need to be completed within the time limit, instead of one. So this approach only works if you have a reliably fast heuristic.

Moreover, this still doesn't give you guaranteed performance measures to include in an SLA; it just gives you a better chance of meeting whatever guarantees are included in the SLA.

Answer 2

I think there is three angles to attack this problem. A complete solution will probably feature each one of them

1. Large set of (hard) test cases: If you are worried about the hard instances, then I would create a large set of test cases which you can update anytime you find a new one that was difficult. These can be integrated into the build pipeline of your software, so every time you publish a new version of your application, you can see whether the tests still run (of course, these tests should run on the hardware to be used).
2. Algorithmic development and testing: Once you have at least some test cases available, you should check whether your time requirements are met. The most important thing here is that you have a quantifiable target. The sentence "I want it faster" is not good enough. If your time box is 4 hours, you may want to say that "I want my hard cases to reach a 1% optimality gap within 2 hours". This is quantifiable and can be used to drive the algorithmic development. A description of this process I very much liked can be found here (even though it is for MATLAB).
3. Hardware testing: Once you have at least some test cases available, and you settled (more or less) on your algorithm you can start checking different hardware. Of course this is easiest if you have e.g. a Gurobi Compute Server, where you can scale up and down and see what your problem instance does. If you work for a big company they may also have in-house clusters etc. However, a word of caution: the speed-up you get from e.g. multi-threading tapers off after ca. 20-30 cores (depends on solver and application), and may even increase run time again. So if you throw a 80 core beast at your problem, you may be slower than a 16 core machine. In fact, one of the easiest investments to make is to increase the RAM on your machine, so that the solver can hold more information in memory.

As for your original question of the SLA: first you should go through these steps and see what you need, and then go from there. In general I would probably always go for something that gives me a lot of flexibility and does not limit the amount of computing power I can use (certain vendors do that).

And lastly, NP-hardness itself is not an argument for "difficulty" in the practical sense. Some cases are hard, some are easy while all may be NP-hard.