3
$\begingroup$

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?)
Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented May 12, 2023 at 1:24
  • $\begingroup$ @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? $\endgroup$
    – Erel Segal-Halevi
    Commented May 12, 2023 at 6:17
  • 3
    $\begingroup$ @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. $\endgroup$
    – Andras Farago
    Commented May 12, 2023 at 19:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented May 13, 2023 at 11:36
  • $\begingroup$ @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? $\endgroup$
    – Erel Segal-Halevi
    Commented May 15, 2023 at 8:20

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.