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

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

• SAS solvers have a MAXTIME option. – RobPratt Sep 28 '20 at 21:37
• @RobPratt Any idea about the listed solvers ? – Best_fit Sep 28 '20 at 21:44
• I would expect any MI* solver to have this functionality. – RobPratt Sep 28 '20 at 21:47

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.

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.