1
$\begingroup$

I'm trying to write a linear programming problem statement. Values of the solution vector have a bound constraint: $0 \leq x_i \leq 1$.

Another constraint is that if we take a predefined subset of solution vector values, then it should contain only one nonzero value or no nonzero values.

So it can be informally formulated in this way (without loss of generality): a vector either should be zero or should have exactly one nonzero value. Is it possible to set such constraint for the vector $x$ in terms of inequality ($Ax \leq b$) or equality ($A_{e}x=b_{e}$) constraints? How to do that?

$\endgroup$
  • 1
    $\begingroup$ The constraint you describe specifies a set that is nonconvex (take two particular points of the set and show the average is not in the set). So, it cannot be written as a linear program. $\endgroup$ – Michael Jul 31 '15 at 5:59
  • $\begingroup$ If you are actually writing an integer linear program then you can do it (of course, such a thing specifies nonconvex constraints). $\endgroup$ – Michael Jul 31 '15 at 6:03
  • $\begingroup$ Really that is. OK, I'll also try to think over nonlinear convex objective... $\endgroup$ – Sergey Jul 31 '15 at 6:47
2
$\begingroup$

As already pointed out, the feasible space for the cardinality constraint is non-convex. (0, 1) and (1, 0) have 1 nonzero, but (0.5, 0.5) have two. Converting this to a nonlinear function is mathematically correct, but it is more practical to use a mixed-integer programming formulation.

You first, need to introduce an integer variable to indicate that each $x_i$ is nonzero. $$x_i - y_i \le 0 \hspace{0.25in} \forall i$$ $$ y_i \in \{ 0, 1 \} \hspace{0.25in} \forall i$$ These constraints will force $y_i$ to 1 if x_i is nonzero. For our purposes, it is not necessary to enforce the converse.

Then for any subset of that is constrained to have at most one nonzero, you add the constraint

$$ \sum_{i \in I'} y_i \le 1$$

Which can be satisfied if and only if 0 or 1 of the $x_i$ values are nonzero.

$\endgroup$
  • $\begingroup$ I checked this variant in my Matlab model and it works hust fine! Thanks! $\endgroup$ – Sergey Aug 5 '15 at 7:31
  • $\begingroup$ What if I would like the same indicator $y_i$ but without the constraint $0<=x_i<=1$? Is it possible? $\endgroup$ – Marek Židek Mar 31 '16 at 15:08
1
$\begingroup$

I only see the the option to define a non-linear constraint.

$$x_i\cdot x_j=0 \quad \forall \ i \neq j$$

$i,j \in \{1,2,\ldots , n\}$

If more than one of the variable is unequal zero, then the constraint wouldn´t be satisfied.

$\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.