1
$\begingroup$

One approach to solving NP-hard problems is to use an anytime algorithm: an algorithnm that starts with a heuristic solution and keeps improving it towards the optimum, and when it is stopped, it returns the best solution found so far. For example, the complete greedy algorithm is an anytime algorithm for number partitioning.

My question is: is there a generic integer linear programming solver, that works in this "anytime" manner?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Your definition of anytime is wrong. The right one is actually the first sentence of your first link "In computer science, an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends.". All MILP solvers are anytime $\endgroup$
    – fontanf
    Jun 11 at 10:32
  • 2
    $\begingroup$ As there is not much difference complexity-wise between finding a feasible solution and finding an optimal feasible solution, MILP solvers with all their primal-heuristics are as anytime as it gets. All of them also allow to focus on finding feasible solutions early followed up by better ones (often called "emphasis" which, among other things, shifts some time/budget towards primal-heuristics). A lot of MILP-solver functionality only kicks in when this (or better: more) feasible solution is available like large-neighborhood search and co. (reflecting your expected workflow). $\endgroup$
    – sascha
    Jun 11 at 11:29
  • 3
    $\begingroup$ Technically what you mention are not solvers but modelling tools which call solvers underneath. How you interrupt a solver is an individual programming question for each solver. You can set time limits, iteration limits, termination criteria, stop from a callback function, stop when the 543rd solution improvement has been made etc. etc. etc. It is a technical question the documentation of your solver (or modelling tool) will have. $\endgroup$
    – Michal Adamaszek
    Jun 13 at 8:02
  • 1
    $\begingroup$ Most MILP solvers have at least stop criteria related to elapsed time, number of nodes explored or gap, and often a callback for more custom criteria. As @Michal Adamaszek wrote, you need to check the documentations of the modelers you're using $\endgroup$
    – fontanf
    Jun 13 at 11:17
  • 1
    $\begingroup$ For some MILP's, finding any feasible solution is extremely hard- you might run for months without finding a feasible integer solution. $\endgroup$
    – Brian Borchers
    Jun 14 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

All commercial software capable of finding multiple solutions in one run will return the "best found so far" if an early exit condition is met (e.g. interrupt).

My solver for instance will even do that on CTRL+C.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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