# Anytime solver for integer linear program

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?

• 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 Jun 11 at 10:32
• 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). Jun 11 at 11:29
• 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. Jun 13 at 8:02
• 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 Jun 13 at 11:17
• For some MILP's, finding any feasible solution is extremely hard- you might run for months without finding a feasible integer solution. Jun 14 at 16:36