Skip to main content
Operations Research

Return to Answer

added 69 characters in body
Source Link
Henrik Alsing Friberg
Henrik Alsing Friberg
  • 2k
  • 8
  • 16

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.

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" and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

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.

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.

deleted 5 characters in body
Source Link
Henrik Alsing Friberg
Henrik Alsing Friberg
  • 2k
  • 8
  • 16

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" and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

Complexity

This problem is NP-completehard 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.

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" and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

Complexity

This problem NP-complete 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.

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" and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

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.

added 55 characters in body
Source Link
Henrik Alsing Friberg
Henrik Alsing Friberg
  • 2k
  • 8
  • 16

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-normzero "norm" and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

Complexity

This problem NP-complete 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.

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 and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

Complexity

This problem NP-complete 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.

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" and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

Complexity

This problem NP-complete 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.

Source Link
Henrik Alsing Friberg
Henrik Alsing Friberg
  • 2k
  • 8
  • 16