What are the solvers that give a feasible solution within a given time?

Question

What are the solvers that take the maximal computation time as a parameter and gives the best found feasible solution within this time.

Answer 1

Pretty much all of them. Any solver worth using will support timeouts and what you describe is basically running a solver with a timeout.

Solvers that are supposed to compute more than one solution (e.g. MILP, convex & global MINLP, global NLP, stochastic MILP & MINLP) will return the best one by timeout - the rest will typically return garbage if a solution is not computed by timeout.

Answer 2

In OptaPlanner (open source, java), we not just support the traditional approaches such as the solving wall clock time in application.properties:

# Terminate solving after 30 seconds.
# To run for 5 minutes use "5m" and for 2 hours use "2h".
optaplanner.solver.termination.spent-limit=30s

or the unimproved wall clock time:

# Terminate if the best score hasn't improved for 30 consecutive seconds.
optaplanner.solver.termination.unimproved-spent-limit=30s

or a certain score has been attained:

# Terminate when the first feasible solution has been found
optaplanner.solver.termination.best-score-limit=0hard/*soft

or an AND/OR combination of those and/or several other pre-configured terminations (full list here).

We also support asynchronous termination, which is very powerful in combination with best solution changed events, to give the end-users control over their own time:

SolverJob solverJob = solverManager.solveAndListen(...,
    // Each time we have a new best solution, show the latest one to the user
    newBestSolution -> showOnScreen(newBestSolution));
...
// When the user is satified with the shown solution and tired of waiting
terminateButton.onClick(solverJob.terminateEarly());

That feedback loop can be important.