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


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}$

| cite | improve this answer | |
  • 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 '16 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 '16 at 16:15

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.