1
$\begingroup$

Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities. I am interested in the hardness of computing the dimension of the polytope $P$.

Equivalently we can formulate this as the decision problem by asking whether the dimension of $P$ is $m$ for some $0 \leq m \leq n$. To prove that the dimension is indeed $m$, we need to show that

  1. There are $m+1$ affinely independent vectors in $P$ which yields that the dimension is at least $m$.
  2. There are $n-m$ independent equalities that are satisfied by $P$ which yields that the dimension is at most $m$.

I could not find any literature that considers this problem. Also I cannot think of a reduction to or from another problem.


Answer thanks to Neil Young:

  • Condition 1 can be checked in polynomial time while this is not obvious for Condition 2. Therefore the problem "is the dimension of $P$ at least $m$?" is in NP and similarly the problem "is the dimension at most $m$?" is in co-NP.

  • The decision problem "is $P$ empty?" is well known to be NP-hard. This problem can be reduced to the decision of dimension as follows: Add $m$ additional free variables to $P$ to obtain $P'$. Then $P$ is not empty iff the dimension of $P'$ is at least $m$. Therefore "is $P$ empty?" can be reduced to "is the dimension of $P'$ at least $m$?".

Together we obtain that "is the dimension of $P$ at least $m$?" is NP-complete and as a result that "is the dimension of $P$ equal $m$?" is NP-hard.

However, if we additionally assume that $P$ is non-empty then this reduction does not work. It is unclear to me whether the problem remains NP-complete.

(Edit thanks to Neal Young: Given a feasible solution, finding a second, different, feasible solution is NP-hard. And since two different vectors are affinely independent deciding "is the dimension of $P$ at least $1$?" is NP-hard for non-empty $P$. Again, by adding free variables, it follows that deciding "is dimension of $P$ at least $m$?" is NP-hard even for non-empty $P$)


Originally, my interest in this problem arose from studying the convex hull of the feasible set of an ILP corresponding to a combinatorial optimization problem. Such polytopes have some additional structure and the general "proof" from above does not hold. So my follow-up question is:

Are there examples of combinatorial optimization problems where it is hard to compute the dimension of the convex hull of all feasible solutions and where the set of feasible solutions is non-empty? And related: are there examples where it is hard to decide whether a valid inequality defines a facet (maybe even where the polytope is full dimensional and the facet has dimension $n-1$)?

$\endgroup$
5
  • 3
    $\begingroup$ Surely it's NP-hard, because determining whether an ILP is even feasible is NP-hard. Do you know whether the decision problem "is the dimension at least $m$"? is in NP? (At first glance, you could just guess a set of vectors for Condition 1 and check them... but you'd need to know that it suffices to consider vectors with encoding size polynomial in the encoding size of $(A, b)$...) If that problem is in NP, then your problem should be in DP (expressible as the intersection of languages in NP and coNP). $\endgroup$
    – Neal Young
    Nov 11, 2021 at 14:16
  • $\begingroup$ In my case I was thinking about bounded polytopes, even more specifically about 01-polytopes $P \subseteq \{0,1\}^n$. In that case a certificate for Conditions 1 and 2 can clearly be encoded in polynomial size and the problem is in NP. I am not sure about unbounded polyhedra. $\endgroup$
    – badboul
    Nov 11, 2021 at 15:38
  • $\begingroup$ Also in my case the polytopes are nonempty. Maybe the hardness of the decision problem "given $k$ affinely independent vectors in $P$, does there exist an additional vector that is affinely independent of the given $k$?" can be established by a reduction from feasibility of an ILP. Thanks for the pointer. $\endgroup$
    – badboul
    Nov 11, 2021 at 15:44
  • 2
    $\begingroup$ (i) How do you verify (in NP) Condition 2 for a given set of equalities even in the 0/1 case (given that you need to check whether all integer points in P satisfy those inequalities)? The problem "Does a given ILP polytope have dimension at most $k$" seems co-NP hard, e.g. by reduction from UNSAT. (ii) By "an additional vector that..." do you mean "an additional vector in P that..."? (iii) Assuming so, the case k=0 is testing whether P is empty (NP-hard), and it seems likely that the cases k >= 1 can be reduced to from any given polytope just by adding some artificial variables... $\endgroup$
    – Neal Young
    Nov 11, 2021 at 19:17
  • 2
    $\begingroup$ Please edit your question to include all relevant information, such as that you are working over $\{0,1\}^n$. People shouldn't have to read the comments to understand what you are asking. $\endgroup$
    – D.W.
    Nov 12, 2021 at 2:53

1 Answer 1

1
$\begingroup$

Yes, MORE-SAT, defined below, is one example of a combinatorial optimization problem for which the natural 0/1 integer linear program (ILP) is guaranteed to be feasible, and determining the dimension of the convex hull of the feasible solutions is NP-hard.

Here is the definition of MORE-SAT: Given a satisfiable CNF formula, does it have more than one satisfying assignment?

Lemma 1. MORE-SAT is NP-complete.

We postpone the proof, which is a standard exercise.

Given a MORE-SAT instance $\phi$, let ILP$(\phi)$ represent its ILP formulation via the standard ILP for CNF-SAT. Then the number of satisfying assignments to $\phi$ equals the number of feasible points in ILP$(\phi)$, so ILP$(\phi)$ is guaranteed to be feasible, and it has more than one feasible solution iff $\phi$ has more than one satisfying assignment. So it is NP-hard to determine whether the dimension of the convex hull of the feasible points of ILP$(\phi)$ is at least 1.

Note that it follows that the following problem is NP-hard: Given a feasible 0/1 integer linear program, does it have more than one feasible solution?

Proof sketch for Lemma 1. Here is a reduction from CNF-SAT. Given a CNF-SAT instance $\phi$, let $x_i$ denote its $i$th variable and $C_i$ denote its $i$th clause. Introduce a new variable $y$, and define MORE-SAT instance $$\phi' = C'_1 \wedge C'_2 \wedge \cdots \wedge C'_m \wedge D_1 \wedge D_2 \wedge \cdots \wedge D_n$$ where $C'_i = C_i \vee y$ (for each clause $C_i$ of $\phi)$ and $D_i = x_i \vee \overline y$ (for each variable $x_i$ of $\phi$).

Then setting $x_1 = x_2 = \cdots = x_n = y = $ true gives one satisfying assignment to $\phi'$, and the satisfying assignments with $y=$ false are exactly those where the assignment to $x$ satisfies $\phi$. So the number of satisfying assignments for $\phi'$ is exactly one more than the number for $\phi$. In particular, $\phi'$ is satisfiable, and it has more than one satisfying assignment iff $\phi$ is satisfiable. $~~~\Box$

Remark 1. Given that there are apparently parsimonious polynomial-time reductions from CNF-SAT to most other "natural" NP-complete problems, it follows that, for those other NP-complete problems, the problem of determining whether there is more than one solution (even when there is guaranteed to be at least one) is NP-hard, and likewise for the natural ILP formulations of many of those problems, determining whether the dimension is at least 1 (even when the ILP is guaranteed to be feasible) is NP-hard.

Remark 2. It seems an easy exercise to generalize this to show that the following problem is NP-hard for any given $k\ge 0$: Given a 0/1 ILP such that the convex hull $P$ of its feasible solutions has dimension at least $k$, does $P$ have dimension at least $k+1$? (Reduce from CNF-SAT. Given $\phi$, apply the reduction in Lemma 1 to obtain MORE-SAT instance $\phi'$, and let $\pi$ be the standard ILP for $\phi'$. Then obtain ILP $\pi'$ from $\pi$ by adding $k$ new unconstrained 0/1 variables $Z_1, Z_2, \ldots, Z_{k}$. Then $\pi'$ will have $2^{k}$ solutions with $X_1 = \cdots = X_n = Y=$ 1 and the $Z$'s set arbitrarily, and these solutions have dimension $k$. And $\phi$ is satisfiable iff $\pi'$ has additional solutions with $Y=0$, which happens iff the dimension strictly exceeds $k$...)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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