is a solution of an ILP with local solvers optimal?

Question

I think integer linear programs are not convex but with relaxing integrality constraints it is convex. Now is it important if we solve them with a algorithm whose find local optimal solution for non-convex problems or with a algorithm whose find global optimal solution for convex problems? I mean if we solve them with a local algorithm , the solution might not be optimal? and if we solve them with a global solver the solution is optimal? how come?

Answer 1

In the strictest sense, the definition of a local optimal solution for pure integer linear programs is not very useful because every feasible point is a local solution. This is because there exists a neighborhood of every feasible point where it is the only feasible point, thereby trivially making it a local optimal solution. Other definitions of local optimality, such as being the best feasible solution in a larger neighborhood that contains other feasible solutions, might be useful depending on the context.

But yes, integer linear programs are nonconvex and generally require global optimization techniques to guarantee finding the best possible solution. The way global solvers guarantee finding feasible solutions is by performing clever exhaustive search that involves much more work than "local solvers". State-of-the-art solvers implement variants of branch-and-cut (see here for the basic idea). Depending on the specific problem, there may be heuristics that can yield good feasible solutions.