How to maximize the number of variables with value at least 0?

Question

Given a matrix $A$ and a vector $b$, I would like to find a vector $x$ satisfying the set of linear constraints $A x \leq b$, and subject to that, contains as many variables as possible with nonnegative value.

An obvious solution is to loop over all subsets of variables. For every subset $S$, check if the following set of constraints is feasible:

\begin{align} A x &\leq b; \\ x_i &\geq 0 && \forall i\in S \end{align}

Then, return the solution for the largest set $S$ for which the constraints are feasible. But this solution takes time exponential in the number of variables.

Is there a polynomial-time solution?

Answer 1

Let $L_i$ be a constant lower bound on $x_i$. Introduce binary variables $y_i$ and maximize $\sum_i y_i$ subject to $Ax\le b$ and $L_i (1-y_i)\le x_i$ for all $i$. The new constraints enforce the logical implications $y_i=1 \implies x_i\ge 0$, which you could alternatively enforce via indicator constraints.

---

For the NP-hardness, here's a reduction from independent set. Explicitly, you are given graph $G=(N,E)$ and positive integer $k$. Let binary decision variable $z_i$ indicate whether node $i$ is selected. You want to determine whether there is a solution to \begin{align} \sum_{i\in N} z_i &\ge k \\ z_i + z_j &\le 1 &&\text{for $(i,j)\in E$} \\ z_i &\in \{0,1\} &&\text{for $i \in N$} \end{align} Now take $x_i = z_i-1$ (so that $x_i \ge 0$ corresponds to $z_i = 1$) and rewrite the constraints as \begin{align} -\sum_{i\in N} x_i &\le |N|-k \\ x_i + x_j &\le -1 &&\text{for $(i,j)\in E$} \\ -x_i &\le 1 &&\text{for $i \in N$} \\ x_i &\le 0 &&\text{for $i \in N$} \end{align} This is in the form of your original problem, which is therefore at least as hard as independent set.

Answer 2

Minimizing the number of strictly negative variables, $x_j$, subject to the set of linear constraints, $Ax \leq b$, can be formulated as $$ \begin{array}{ll} \min & \| \; [x]_- \; \|_0\\ & A x \leq b. \end{array} $$

where $\| \cdot \|_0$ is the zero "norm" counting the number of nonzeroes and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$, truncating positive values to zero.

Complexity

This problem is NP-hard and thus you unfortunately wont find anyone able to solve it in polynomial time. This can be proven by its ability to solve the NP-complete binary satisfiability problem $$ A y \leq b,\; y \in \{0, 1\}, $$ equivalent to $$ A y \leq b,\; y \in \{0, -1\}, $$ representable by $$ \begin{array}{ll} \min & \| \; [ \substack{y\\z} ]_- \; \|_0\\ & A y \leq b,\; -1 \leq y \leq 0,\; y + z = -1, \end{array} $$

which is easily cast to the problem type considered.

Solution approaches

You can solve it exactly using mixed-integer linear programming as suggested by @RobPratt, or you can solve it approximately in polynomial time by using the one-norm yielding $$ \begin{array}{ll} \min & \| \; [x]_- \; \|_1\\ & A x \leq b. \end{array} $$

which can be linearized as $$ \begin{array}{ll} \min & \mathbf{1}^T x^-\\ & A x \leq b, \\ & x = x^+ + x^-, \\ & x^+, x^- \geq 0. \end{array} $$

where $\mathbf{1}$ is a vector of ones.

Answer 3

Remember that for a polyhedron to have vertices it is necessary that the number of hyperplanes (i.e. the number of constraints or rows of the system) is not less than the dimension of the vector space (number of components of the hyperplane, i.e. number of the unknowns): $m \geq n$. Generally speaking, an underdetermined system of inequalities (m inequalities in n unknowns with $n > m$) can be reduced to a linear system of equations by introducing the slack variables.

The system $ A x \leq b $ is rewritten as $ ( A | I ) \mathbf x = \mathbf b $ where $I$ is the identity matrix $m \cdot (n-r)$ and the vector $\mathbf x $ is understood as $ {\mathbf x } =(x_1, x_2, …, x_r, x_{r+1}, …, x_{r+m}) $. If the rank of matrix $ ( A | I ) $ is equal to $r$ then inside it is possible to identify $r$ linearly independent row vectors with $n$ unknows. Adding $n$ further inequalities for the unknown vector $ {\mathbf x }$ made of $n$ components such as to require that $ x_i \geq 0 \forall i $, it is possible to have a system of $m+n$ constraints: $m$ equalities and $n$ inequalities. At this point, by appropriately choosing $n-m=r$ components of $\mathbf x $ and setting them equal to zero (i.e. I set the $r$ free parameters equal to zero) we get $m$ hyperplanes in m variables. This is the trick behind the canonical form for linear programming problems and the related simplex solution algorithm.

The computational complexity of the simplex algorithm is not polynomial, while the Gaussian elimination method and Interior-point method are.

If $m<n$ then the polyhedron has no vertices since the independent hyperplanes are not in sufficient number to define a vertex in $R^n$: a vertex in effect consists of a single point. Therefore, the intersection of the $m$ hyperplanes can be a line (if $m=n-1$) or a plane (if $m=n-2$) and so on. Indicated with $r=m-n$, if the rank of the matrix $(A|I)$ is equalt to $m$ then the number of free parameters is exactly equal to $r$. The simplex method sets the $r$ variables equal to zero. In conclusion, a basic solution always presents $r=n-m$ zero components (nonbasic variables) and therefore in optimal blending/mixing problems (for example diet problem) a solution corresponds to a mix made up of a reduced number $m$ of elements compared to the $n$(=$m+r$) starting elements.