<p>The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:</p>
<p>In complements of planar graphs a maximum independent set can be found in polynomial time (because it is equivalent to finding a maximum clique in the complement, which is a planar graph, so it cannot have a clique larger than 4). On the other hand, finding the maximum <em>fractional</em> independent set in these graphs is NP-hard. See  M. Grötschel, L. Lovász, A. Schrijver &quot;Polynomial Algorithms for Perfect Graphs,&quot; pdf: <a href="https://core.ac.uk/download/pdf/301645427.pdf" rel="noreferrer">https://core.ac.uk/download/pdf/301645427.pdf</a>, page 335.</p>
<p>Therefore, it is not the case that the fractional relaxation always makes a problem easier, even tough it would be quite tempting to think so. Sometimes the relaxation can make it harder. Nevertheless, I could accept that probably in &quot;most cases&quot; the fractional relaxation makes the problem easier, if an appropriate definition of &quot;most cases&quot; can be found for this setting.</p>

CC BY-SA 4.0
2023-05-11T03:49:56.370Z
2023-05-11T03:49:56.370Z
Andras Farago
<p>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:</p>
<ul>
<li>Is there a known complexity class of all optimization problems whose fractional relaxation is polynomial-time solvable?</li>
<li>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?)</li>
</ul>

CC BY-SA 4.0
2023-05-12T01:24:17.117Z
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.
Neal Young
CC BY-SA 4.0
2023-05-12T06:17:45.690Z
@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?
Erel Segal-Halevi
CC BY-SA 4.0
2023-05-12T19:36:58.180Z
@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.
Andras Farago
CC BY-SA 4.0
2023-05-13T11:36:27.190Z
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](https://or.stackexchange.com/search?q=valid+inequality).  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.
Neal Young
CC BY-SA 4.0
2023-05-15T08:20:22.317Z
@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?
Erel Segal-Halevi
CC BY-SA 4.0
2023-05-16T20:15:12.060Z
I doubt it.  For example, for *any* optimization problem with only integer solutions you could take the fractional relaxation that allows *all* non-integer solutions to be feasible, and (assuming the optimization problem is a maximization problem) give the solution (1/2, 0, 0, .., 0) very large cost (bigger than the cost of any integer solution) and all other fractional solutions smaller cost.  Any such instance is trivially solvable.  You must have in mind some other restriction on the family of relaxations that you want to consider?
Neal Young
CC BY-SA 4.0
2023-05-17T21:31:04.150Z
Maybe you have in mind that the set of feasible solutions in the relaxation should be convex, and the cost function should be linear?
Neal Young
CC BY-SA 4.0
2023-05-18T10:47:20.583Z
@NealYoung I have a result for integer linear programs and their relaxations, and I wanted to extend it beyond linear programs.  Now I see that it is hard to define what exactly this means. Convexity is indeed a good option: $f$ should define a convex set, and $g$ should concave (for maximization).
Erel Segal-Halevi
<cc.complexity-theory><complexity-classes><optimization>
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
Erel Segal-Halevi
# Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

(Asked by: username_0 on 2023-05-11)

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?)

**Tags:** cc.complexity-theory, complexity-classes, optimization

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_2**: @username_0 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.  
> **username_1**: 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](https://or.stackexchange.com/search?q=valid+inequality).  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.  
> **username_0**: @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?  
> **username_1**: I doubt it.  For example, for *any* optimization problem with only integer solutions you could take the fractional relaxation that allows *all* non-integer solutions to be feasible, and (assuming the optimization problem is a maximization problem) give the solution (1/2, 0, 0, .., 0) very large cost (bigger than the cost of any integer solution) and all other fractional solutions smaller cost.  Any such instance is trivially solvable.  You must have in mind some other restriction on the family of relaxations that you want to consider?  
> **username_1**: Maybe you have in mind that the set of feasible solutions in the relaxation should be convex, and the cost function should be linear?  
> **username_0**: @NealYoung I have a result for integer linear programs and their relaxations, and I wanted to extend it beyond linear programs.  Now I see that it is hard to define what exactly this means. Convexity is indeed a good option: $f$ should define a convex set, and $g$ should concave (for maximization).  

---

## 1 answers

### Answer by username_2 on 2023-05-11. Score: 8 | Accepted answer

The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:

In complements of planar graphs a maximum independent set can be found in polynomial time (because it is equivalent to finding a maximum clique in the complement, which is a planar graph, so it cannot have a clique larger than 4). On the other hand, finding the maximum *fractional* independent set in these graphs is NP-hard. See M. Grötschel, L. Lovász, A. Schrijver "Polynomial Algorithms for Perfect Graphs," pdf: <https://core.ac.uk/download/pdf/301645427.pdf>, page 335.

Therefore, it is not the case that the fractional relaxation always makes a problem easier, even tough it would be quite tempting to think so. Sometimes the relaxation can make it harder. Nevertheless, I could accept that probably in "most cases" the fractional relaxation makes the problem easier, if an appropriate definition of "most cases" can be found for this setting.


---

