Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms! Is solving an ILP easy and fast in practice? Is this solution exact or approximate?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot. Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can find an approximate solution as well (find the best solution they can within the time constraints). There are no hard-and-fast rules.
Of course, ILP is NP-hard, so you should not expect any ILP solver to be able to efficiently solve all ILP instances. Rather, what seems to happen in practice is that some instances can be solved in a reasonable amount of time, but others appear to be very hard. However, ILP solvers incorporate many sophisticated techniques for speeding up the solver, and these are sometimes effective. There's no good way to know for sure in advance whether your specific instance will be solvable efficiently or not, but to try it.
Why is it useful to reduce some other problem to ILP? That's not always useful or interesting... but in some cases it is. For example, it lets you take advantage of the sophisticated methods already implemented in ILP solvers, without having to re-invent them in the context of your other problem.
