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?
- 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?