3
$\begingroup$

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

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

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.