<p>No, it is not always possible.  The illustration below shows an example in which the smallest non-zero value must be <span class="math-container">$1/2^{\Omega(n)}$</span>.  </p>

<p><a href="https://i.sstatic.net/PlV8K.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PlV8K.png" alt="enter image description here"></a></p>

<p>The example is shown in the top of the illustration.  Round nodes are vertices; square nodes are hyperedges, each with connections to its (two or three) vertices.  Each vertex <span class="math-container">$v$</span> is labeled with its weight <span class="math-container">$x_v$</span> in the optimal LP solution, which is essentially unique.</p>

<p>In general, the hypergraph consists of the first three vertices (labeled <span class="math-container">$1/2$</span>) and their three edges to their left, followed by <span class="math-container">$N$</span> copies of the gadget shown in the middle (vertically).  The "inputs" to the gadget are the three vertices labeled <span class="math-container">$1/x$</span>.  The "outputs" are the three vertices labeled <span class="math-container">$1/2x$</span>; these are also the inputs for the next copy of the gadget (if any).  Above <span class="math-container">$N=3$</span>, but in general <span class="math-container">$N$</span> is arbitrarily large.  The sum of the hyperedge sizes is <span class="math-container">$n = \Theta(N)$</span>, and the given solution has a non-zero weight of value <span class="math-container">$\Theta(1/2^N) = 1/2^{\Theta(n)}$</span>.  This solution is obtained greedily by assigning weights maximally, from left to right.</p>

<p>To answer the question in the post, we will show that the given solution is the unique optimal solution.  The bottom part of the illustration above is for the proof (given below).</p>

<p><strong>Lemma 1.</strong> <em>The given LP solution is the unique optimum.</em></p>

<p><em>Proof sketch.</em>
Let <span class="math-container">$x$</span> be the LP solution given in the figure.  By inspection <span class="math-container">$x$</span> is feasible.  First we'll argue that <span class="math-container">$x$</span> is optimal, by giving a dual solution that achieves the same LP objective.
The dual LP is "covering vertices by edges":
<span class="math-container">$$\min \sum_e y_e ~:~ y_e \ge 0;~~(\forall v)~\sum_{e \ni v} y_e \ge 1.$$</span></p>

<p>We use the dual solution illustrated in the bottom part of the figure above, in green.  We give each edge weight equal to the green label at the bottom of its column.  This solution is obtained greedily, by assigning weights minimally from right to left.  By inspection, at least for the example, the dual solution is feasible and has the same cost as the primal solution <span class="math-container">$x$</span>. In general, by calculation, the cost achieved by the given primal solution <span class="math-container">$x$</span> is 
<span class="math-container">$$3[1/2 + N + 1/2^{N+2}],$$</span>
while the cost achieved by the given dual solution is the same:
<span class="math-container">$$3[(1/2 - 1/2^{N+2}) + 1/2^{N+1} + N].$$</span>
Therefore the primal and dual solutions are optimal.</p>

<p>To finish we argue that the optimal primal solution is unique.  Let <span class="math-container">$x^*$</span> be any optimal primal solution.
By complimentary slackness and the fact that all values are non-zero in the optimal dual solution, <span class="math-container">$x^*$</span> must make all primal constraints tight.  </p>

<p>Let <span class="math-container">$x^*_1, x^*_2, x^*_3$</span> be the variables of the first three vertices, given weight <span class="math-container">$1/2$</span> by <span class="math-container">$x$</span>.  That the first three constraints are tight implies <span class="math-container">$x^*_1 + x^*_2 = 1$</span> and <span class="math-container">$x^*_1 + x^*_3 = 1$</span> and <span class="math-container">$x^*_2 + x^*_3 = 1$</span>, which implies that <span class="math-container">$x^*_1 = x^*_2 = x^*_3 = 1/2$</span>, the same as in <span class="math-container">$x$</span>.</p>

<p>Given that, the same reasoning implies that <span class="math-container">$x^*$</span> gives each of the next three vertices weight <span class="math-container">$1/4$</span>, also the same as in <span class="math-container">$x$</span>. Given that, likewise, <span class="math-container">$x^*$</span> must give each of the next three vertices weight <span class="math-container">$3/4$</span>, the same as in <span class="math-container">$x$</span>.  Continuing this reasoning inductively, <span class="math-container">$x$</span> and <span class="math-container">$x^*$</span> must be identical.  <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2020-04-29T01:08:44.667Z
Thanks for your reply! But here n is the total occurrence of vertices in the graph, i.e., $n = \sum_{e \in E} |e|$. In this family of examples, $n = \Theta(k^2)$.
Xiao
CC BY-SA 4.0
2020-04-29T21:16:57.603Z
Oh, right, I was assuming $n$ was the number of vertices in the graph.  I've rewritten the answer completely to show the desired bound.  I think it's interesting --- this example shows that to represent an optimal solution requires at least $\Theta(n)$ bits of precision.  I guess for large $n$ most practical solvers won't be able to get the exact optimum.
Neal Young
CC BY-SA 4.0
2020-04-30T15:18:12.390Z
Nice! It is exactly the counter example for ruling out the possibility of bounding the smallest non-negative value by $\Omega(1/n)$. Just a small correction for exchanging 1/4 and 3/4 in the optimal edge cover.
Xiao
CC BY-SA 4.0
2020-04-30T15:29:26.650Z
I corrected the 1/4 (good catch).  Once you've checked that the answer is correct, can you please mark it as correct by checking the check box to the left at the top of the answer?  That's how stack exchange keeps track of what questions have been answered.  Thanks.
Neal Young
CC BY-SA 4.0
2020-04-28T21:28:14.863Z
2020-04-30T15:27:22.023Z
2020-04-30T15:27:22.023Z
Neal Young
<p>Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size <span class="math-container">$n = \sum_{e \in E}|e|$</span>. We introduce a variable <span class="math-container">$x_v$</span> for each vertex <span class="math-container">$v \in V$</span>. </p>

<p><span class="math-container">$$\max \sum_{v} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$</span>
<span class="math-container">$$s.t. \sum_{v: v \in e} x_v \le 1, \ \forall e \in E$$</span>
<span class="math-container">$$\ x_v \ge 0, \ \forall v \in V$$</span></p>

<p>Is it always possible to find an optimal solution such that the minimum non-zero variable has value at least <span class="math-container">$c \cdot 1/n$</span> for some constant <span class="math-container">$c$</span>? (If representing the contraints as <span class="math-container">$\mathbf{Ax} \le \mathbf{1}$</span>, there are <span class="math-container">$n$</span> entries as <span class="math-container">$1$</span> in <span class="math-container">$\mathbf{A}$</span> with remaining entries as <span class="math-container">$0$</span>.)</p>

<linear-programming>
Minimum non-zero variable in the optimal solution of linear programming
Xiao
# Minimum non-zero variable in the optimal solution of linear programming

(Asked by: username_0 on 2020-04-27)

Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size $n = \sum\_{e \in E}|e|$. We introduce a variable $x\_v$ for each vertex $v \in V$.

$$\max \sum\_{v} x\_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \sum\_{v: v \in e} x\_v \le 1, \ \forall e \in E$$
$$\ x\_v \ge 0, \ \forall v \in V$$

Is it always possible to find an optimal solution such that the minimum non-zero variable has value at least $c \cdot 1/n$ for some constant $c$? (If representing the contraints as $\mathbf{Ax} \le \mathbf{1}$, there are $n$ entries as $1$ in $\mathbf{A}$ with remaining entries as $0$.)

**Tags:** linear-programming

---

## 1 answers

### Answer by username_1 on 2020-04-28. Score: 4 | Accepted answer

No, it is not always possible. The illustration below shows an example in which the smallest non-zero value must be $1/2^{\Omega(n)}$.

[![enter image description here](https://i.sstatic.net/PlV8K.png)](https://i.sstatic.net/PlV8K.png)

The example is shown in the top of the illustration. Round nodes are vertices; square nodes are hyperedges, each with connections to its (two or three) vertices. Each vertex $v$ is labeled with its weight $x\_v$ in the optimal LP solution, which is essentially unique.

In general, the hypergraph consists of the first three vertices (labeled $1/2$) and their three edges to their left, followed by $N$ copies of the gadget shown in the middle (vertically). The "inputs" to the gadget are the three vertices labeled $1/x$. The "outputs" are the three vertices labeled $1/2x$; these are also the inputs for the next copy of the gadget (if any). Above $N=3$, but in general $N$ is arbitrarily large. The sum of the hyperedge sizes is $n = \Theta(N)$, and the given solution has a non-zero weight of value $\Theta(1/2^N) = 1/2^{\Theta(n)}$. This solution is obtained greedily by assigning weights maximally, from left to right.

To answer the question in the post, we will show that the given solution is the unique optimal solution. The bottom part of the illustration above is for the proof (given below).

**Lemma 1.** *The given LP solution is the unique optimum.*

*Proof sketch.*
Let $x$ be the LP solution given in the figure. By inspection $x$ is feasible. First we'll argue that $x$ is optimal, by giving a dual solution that achieves the same LP objective.
The dual LP is "covering vertices by edges":
$$\min \sum\_e y\_e ~:~ y\_e \ge 0;~~(\forall v)~\sum\_{e \ni v} y\_e \ge 1.$$

We use the dual solution illustrated in the bottom part of the figure above, in green. We give each edge weight equal to the green label at the bottom of its column. This solution is obtained greedily, by assigning weights minimally from right to left. By inspection, at least for the example, the dual solution is feasible and has the same cost as the primal solution $x$. In general, by calculation, the cost achieved by the given primal solution $x$ is
$$3[1/2 + N + 1/2^{N+2}],$$
while the cost achieved by the given dual solution is the same:
$$3[(1/2 - 1/2^{N+2}) + 1/2^{N+1} + N].$$
Therefore the primal and dual solutions are optimal.

To finish we argue that the optimal primal solution is unique. Let $x^\*$ be any optimal primal solution.
By complimentary slackness and the fact that all values are non-zero in the optimal dual solution, $x^\*$ must make all primal constraints tight.

Let $x^\*\_1, x^\*\_2, x^\*\_3$ be the variables of the first three vertices, given weight $1/2$ by $x$. That the first three constraints are tight implies $x^\*\_1 + x^\*\_2 = 1$ and $x^\*\_1 + x^\*\_3 = 1$ and $x^\*\_2 + x^\*\_3 = 1$, which implies that $x^\*\_1 = x^\*\_2 = x^\*\_3 = 1/2$, the same as in $x$.

Given that, the same reasoning implies that $x^\*$ gives each of the next three vertices weight $1/4$, also the same as in $x$. Given that, likewise, $x^\*$ must give each of the next three vertices weight $3/4$, the same as in $x$. Continuing this reasoning inductively, $x$ and $x^\*$ must be identical. $~~~\Box$

> **Comments:**
> **username_0**: Thanks for your reply! But here n is the total occurrence of vertices in the graph, i.e., $n = \sum_{e \in E} |e|$. In this family of examples, $n = \Theta(k^2)$.  
> **username_1**: Oh, right, I was assuming $n$ was the number of vertices in the graph.  I've rewritten the answer completely to show the desired bound.  I think it's interesting --- this example shows that to represent an optimal solution requires at least $\Theta(n)$ bits of precision.  I guess for large $n$ most practical solvers won't be able to get the exact optimum.  
> **username_0**: Nice! It is exactly the counter example for ruling out the possibility of bounding the smallest non-negative value by $\Omega(1/n)$. Just a small correction for exchanging 1/4 and 3/4 in the optimal edge cover.  
> **username_1**: I corrected the 1/4 (good catch).  Once you've checked that the answer is correct, can you please mark it as correct by checking the check box to the left at the top of the answer?  That's how stack exchange keeps track of what questions have been answered.  Thanks.  

---

