I don't know what is meant by "decision version of integer programming".

I know ILP, but this terminology has me confused.


It's the same was for all NP problems; the optimisation problem is

Find a valid solution $s$ that minimises¹ $f(s)$!

and the corresponding decision problem is

Is there a valid solution $s$ with $f(s) \leq k$?

You see that the former immediately solves the latter, and you can solve the former by using the latter with binary search over the set of feasible $k$.

  1. Of course, you can have "maximise" here and "$\geq k$" in the decision version.

The decision version of any problem is "Is there a solution?"

  • $\begingroup$ Does this version tell us if something is a solution, and/or how to find a solution? $\endgroup$ – Tim Nov 3 '14 at 1:17
  • $\begingroup$ You want not only an answer "yes" or "no" but also a reason why you should believe that answer. If the answer is "yes" then giving a solution would be helpful. If the answer is "no" then there may be a simple proof that no solution is possible in some cases, but in general the only reason to believe that the answer is "no" is that somebody carefully wrote the software giving the answer, made no mistakes, and the software wouldn't say "no" if that is not the correct answer. $\endgroup$ – gnasher729 Apr 14 '17 at 17:37
  • $\begingroup$ For each node n find the length of the longest edge $l_n$ starting from n. Then f (s) is at most the sum of those lengths, and if that sum is ≤ k then there is a solution. The answer is "yes" - without knowing any solution. (Although finding a solution is trivial in this case). I wonder if there are cases where I can prove f (s) ≤ k without finding a solution, where the solution is not trivial. $\endgroup$ – gnasher729 Apr 14 '17 at 17:41
  • $\begingroup$ @gnasher I'm not sure how your comments relate to my answer: were you responding to a comment that was deleted? I'm also not sure what you mean. A decision problem is literally, "yes or no". It's just a set. If you have an algorithm that decides that set, then you believe the answer because you proved the algorithm correct. But there's no requirement for, e.g., algorithms that decide sets to provide witnesses. $\endgroup$ – David Richerby Apr 14 '17 at 19:58

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.