# Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

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?)
• I think the definition of "fractional relaxation" above not well-defined ("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") For example, consider finding a maximum matching (in general graphs). There is a natural encoding of solutions as 0/1 vectors (over the edges). Yet there are multiple (standard, but different) fractional relaxations of the problem. This is not uncommon. May 12, 2023 at 1:24
• @NealYoung suppose we define an optimization problem by a predicate $f$ and an integer valued function $g$. The pair $f,g$, represents the problem "Given an input vector $x$, find an integer vector $y$ that maximizes $g(x,y)$ among all integer vectors that satisfy $f(x,y)$". Then, the relaxation is the problem "Given an input vector $x$, find a rational vector $y$ that maximizes $g(x,y)$ among all rational vectors that satisfy $f(x,y)$". Why is it not well-defined? May 12, 2023 at 6:17
• @Erel Segal-Halevi An issue could be that two different predicates $f_1,f_2$ may determine the same set of integer vectors as allowable solutions for a given input $x$, but after the relaxation the allowed rational solution sets may become different, even though the integer vectors within the two sets are the same. In such a case the fractional optimum may depend on which defining function ($f_1$ or $f_2$) is used, even though the integer-output optimization problem remains the same, as the integer vectors in the two sets coincide. May 12, 2023 at 19:36
• Yes, the extensions of $f$ and $g$ are not uniquely defined. Consider, for example, the standard LP relaxation for max-cut, vs. the semi-definite relaxation. Or, any of the many integer LPs for which there are multiple relaxations obtained by adding various classes of valid inequalities. E.g. some extensions of $f$ may allow more rational solutions than others. E.g. you could in principle extend $f$ either to be false on every non-integer point, or to be true on every non-integer point. May 13, 2023 at 11:36
• @NealYoung What about the class of optimization problems that have at least one fractional relaxation that can be solved in polynomial time - is it a well-defined and non-trivial? May 15, 2023 at 8:20