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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$– adrianNCommented 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$ Commented Aug 6, 2016 at 16:15