It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any optimization problem in which the expected output is an integer vector: the solution of the relaxation is just the solution of the problem without the restriction that the output is an integer vector. My questions are:
- Is there a known complexity class of all optimization problems whose fractional relaxation is polynomial-time solvable?
- Does this class contain all polynomial-time solvable optimization problems? (that is: if an integer-output optimization problem is polynomial-time solvable, is its fractional relaxation necessarily polynomial-time solvable too?)