4
$\begingroup$

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

I know ILP, but this terminology has me confused.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

It's the same as 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.
Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Does this version tell us if something is a solution, and/or how to find a solution? $\endgroup$
    – Tim
    Nov 3, 2014 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, 2017 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, 2017 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, 2017 at 19:58

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.