patternMinor
Can integer linear programs have non-integer OPT solutions?
Viewed 0 times
linearcannonoptsolutionsprogramsintegerhave
Problem
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?
Solution
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}$
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}$
Context
StackExchange Computer Science Q#62306, answer score: 6
Revisions (0)
No revisions yet.