4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ It seems that it is an LP problem. LP is always solvable in polynomial time. $\endgroup$
    – Manglu
    Mar 29 at 12:06
  • $\begingroup$ @Erel Segal-Halevi, do you equivalently want to find all the vertex of the solution space polyhedron? $\endgroup$
    – A.Omidi
    Apr 2 at 9:39
  • $\begingroup$ @A.Omidi the vertices maximize the number of variables with value exactly 0. I want to maximize the number of variables with value at least 0. These are different things (I am not even sure that the solution to my problem is necessarily a vertex). $\endgroup$ Apr 2 at 12:01
  • $\begingroup$ @ErelSegal-Halevi, would you please, say what you mean by exactly $0$? $\endgroup$
    – A.Omidi
    Apr 2 at 12:46
  • $\begingroup$ @A.Omidi the page on basic feasible solution has a detailed explanation on this. But it is not related to my question. $\endgroup$ Apr 2 at 13:13

3 Answers 3

6
+50
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I believe it should be mentioned that this cannot be solved in polynomial time (since OP asked). $\endgroup$
    – Kuifje
    Mar 29 at 14:00
  • $\begingroup$ Since the new variables $y_i$ are binary, solving the new program requires, in the worst case, to check all $2^n$ possible combinations of their values, which is similar to the solution I described (checking all $2^n$ possible subsets of variables $x_i$). Is there a polynomial-time solution? $\endgroup$ Mar 30 at 19:34
  • 1
    $\begingroup$ I suspect that there is no polynomial-time algorithm, but the formulation I suggested should in practice perform much better than brute force. $\endgroup$
    – RobPratt
    Mar 30 at 20:19
  • $\begingroup$ Thanks! In the reduction, can you consider only the simpler program with 3 constraints $x_i + x_j\leq -1$ and $-x_i \leq 1$ and $x_i \leq 0$, and argue that maximizing the number of nonnegative variables is equivalent to maximizing the number of variables with value $0$, which is equivalent to maximizing the size of the independent set? $\endgroup$ Apr 4 at 19:36
  • $\begingroup$ Yes, that is the usual relationship between an optimization problem and a decision problem. $\endgroup$
    – RobPratt
    Apr 4 at 20:36
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I do not understand how this gives the solution with the largest number of nonnegative variables. $\endgroup$ Apr 4 at 10:08
  • $\begingroup$ It depends on the matrix, m>n or m<=n. For example, if $A$ was the identity matrix then there are not any variable equal to zero, so all variable are positive. Moreover, It depends on what method you apply: simplex or interior point... $\endgroup$ Apr 4 at 12:44

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.