[Solved]: Can integer linear programs have non-integer OPT solutions?

Problem Detail: 

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?

Asked By : User

Answered By : Ricky Demer

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62306

3.2K people like this

 Download Related Notes/Documents