19
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ this is a good question. I am looking forward to seeing some interesting answers. Meanwhile, have a look at this similar question: or.stackexchange.com/q/1122/39 $\endgroup$ – Oguz Toragay Sep 25 '19 at 5:00
  • 1
    $\begingroup$ Nice question that is also relevant to myself in the near future... I'd argue that unless you are VERY confident in your model/solver, you will never include a commitment of optimality. Then the problem boils down to finding the best solution in the given time frame. It probably is also wise to explain to the customer (on a higher level) the pitfalls of the problem which can eventually even lead to finding no solution at all (e.g. if the input data is flawed). Input data quality should also mentioned in the SLA (see "bullshit in, bullshit out" ;D) $\endgroup$ – JakobS Sep 25 '19 at 8:10
  • $\begingroup$ @JakobS How about writing this as an answer? $\endgroup$ – LarrySnyder610 Sep 25 '19 at 12:34
  • $\begingroup$ This is a nice question. As @LarrySnyder610 said and from a practical point of view to guarantee to get an optimal or suboptimal solution in a reasonable time, you should use both exact and heuristic methods (or hybrid method) to increase your flexibility. $\endgroup$ – A.Omidi Sep 25 '19 at 22:00
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Absolutely this - no executive will want to spend hundreds of thousands in computation to solve an NP hard problem when they can just spend tens of thousands to make up the difference. It's all about the Benjamins. Unless you're from Canada, in which case it's all about the Bordens. $\endgroup$ – corsiKa Sep 25 '19 at 18:24
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. You say "Once you have at least some test cases available, you should check whether your time requirements are met." - is it possible to generate these systematically? e.g: For gradient descent, we can create a function with a large number of local minima, and test our GD procedure on it. Is this possible for an arbitrary MIP or MINLP problem with a given number of decision variables and constraints? $\endgroup$ – Skander H. Sep 25 '19 at 8:29
  • 1
    $\begingroup$ Sure you can generate problems in one way or another (e.g. for an inventory problem use different products and shipping costs etc.) however I have found that artificial (which these are by definition) problems only get you so far. The truly best way is to use real-life instances from past shipments and go from there. $\endgroup$ – Richard Sep 25 '19 at 8:31
  • $\begingroup$ "the speed-up you get from e.g. multi-threading tapers off after ca. 20-30 cores (depends on solver and application), " regarding this: Do you have any references on running optimization algorithms and solvers on distributed environments and on the cloud? $\endgroup$ – Skander H. Sep 25 '19 at 9:03
  • $\begingroup$ I've seen this result a lot (e.g. from FICO at their user group meeting in Frankfurt last year), however right now I couldn't find references to that (maybe somebody else can). However, yesterday I came across this paper that does show a similar effect for nonlinear optimization solvers: arxiv.org/pdf/1909.08104.pdf $\endgroup$ – Richard Sep 25 '19 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.