Why is it that every integer linear program has optimal solutions that are integers? At least in online text books, they are always integers. Can solutions of ILPs only be integers?

enter image description here


1 Answer 1


Something that might be causing you confusion: "integer linear programming", by definition, restricts the variables to integer values.
Linear programming instances in which the input numbers are integers can easily have only non-integer solutions. Consider:

$\begin{cases} \begin{alignat}{1} 2 &\cdot x \le 1 \\[1.5ex] -2 &\cdot x \le -1 \end{alignat} \end{cases}$

  • 2
    $\begingroup$ Note that in general, if you drop the restriction for integer solutions you indeed get better objective values. That's called relaxing your ILP to an LP. $\endgroup$
    – adrianN
    Aug 5, 2016 at 7:46
  • $\begingroup$ In practice, you usually solve an ILP by solving it as an LP, and if the optimal solution is not optimal then adding another constraint that removes that solution but no integer solution. $\endgroup$
    – gnasher729
    Aug 6, 2016 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.