Performance degradation when an incremental solve times out

[mbalduccini]

We have observed what seems to be performance degradation when we use incremental solving in optimization tasks and timeouts occur during a sequence of incremental solves. Consider a simplified case in which we run two solves in a row on the same ASP program using the incremental API. We run the first solve with a timeout of 5 sec and the second solve with a timeout of 60 sec. Both solves happen to time out, but the best cost found by the first (5 sec) solve is always better than the best cost found by the second (60 sec) solve. Is there anything we can do so that the 60 sec solve is more likely to return an equal or better cost than the 5 sec call? Perhaps there is a way to clean up the state of the search after the first solve so that the second call can start more or less "from scratch"? More details on one of the scenarios we experimented with is below.

Thanks!

The solving method carries out three main steps:

1. Set up an async solve by calling SolveHandle::solve(std::vector(),NULL,true)
2. Iteratively retrieve each model and keep track of the best cost vector found
3. If the timeout is reached, call SolveHandle::cancel() and return

We call the solving method twice in a row without changing the ASP program:

• First, we call it with a timeout of 5 sec. The call times out, with a best cost of 308100
• Next, we call it with a timeout of 60 sec. The call times out. The best cost returned is never as good as the cost found with the 5 sec timeout. In our experiments we have seen values as low as 309800 and as high as 366900.

Incidentally, we attempted the suggestions from https://github.com/potassco/clingo/issues/176 but they didn't make a difference.

[rkaminsk]

I fear, I cannot give a good answer. Hard optimization problems are challenging and the solver is likely to get stuck in local optima.

Some pointers:

• You can try the --forget-on-step option.
• In https://github.com/potassco/clingo/tree/wip/examples/clingo/opt-enum you find a heuristic to restart search from the last model found.

[mbalduccini]

Thanks! I'll study that example.