2
$\begingroup$

Is there a trick for explaining the following constraint as a set of linear (in)equalities?

$$ \sum_{i=1}^n|x_i-a_i|>0, $$ where $a_i$'s are real constants.

$\endgroup$
  • $\begingroup$ So, actually this means "not all $x_i$ equal to $a_i$" or equivalently "at least one $x_i$ that is not equal to $a_i$". Because the only case that the sum in LHS is not $>0$ is when every $x_i=a_i$. $\endgroup$ – Jimmy R. Dec 9 '14 at 22:15
1
$\begingroup$

Suggestion: This constraint actually excludes only the vector $$\vec{x}=\vec{a}$$ Therefore an idea would be to solve the LP without this constraint. If the result is exactly this vector then adjust appropriatelly (for example move $ε$ to some acceptable direction). If the result is not this exact vector, then you obtain at no extra cost that this solution is optimal also for the constrained LP.

The second case is straightforward, while the first case might be more complicated to resolve.


If you have (as in most LP's) that $x_i \ge 0$ and you have an $a_i<0$ then the constraint is automatically fullfilled in every feasible solution $x$. The point is that you might cirmuvent easily this constraint in many problems, depending on the specific details about the problem, while in full generality it might be more difficult (computationally).

$\endgroup$
0
$\begingroup$

Hint
We have by elementary cases
$|x|<a \Leftrightarrow -a < x \wedge x < a$
$|x|>a \Leftrightarrow x < -a \vee a < x$

$\endgroup$
  • $\begingroup$ Well! I look for a formulation that avoids an exponential number of linear inequalities. Does your suggestion guarantee that? $\endgroup$ – Hossein Dec 9 '14 at 22:23
  • 1
    $\begingroup$ @Hossein What is exponential about $2n$ constraints with pairwise OR and grouped by AND? $\endgroup$ – AlexR Dec 11 '14 at 8:59
  • $\begingroup$ Suppose the constraint $|x|+|y|+|z|\geq1$. One way for describing this constraint is to use the following $2^3$ constraints: $x+y+z\geq1$, $-x+y+z\geq1$, $x-y+z\geq1$, ..., $-x-y-z\geq1$. So, for a constraint which has $k$ absolute value terms, we have $2^k$ linear constraints, which is undesirable. However, I cannot understand the purpose of the hint completely. $\endgroup$ – Hossein Dec 11 '14 at 19:20
  • 1
    $\begingroup$ @Hossein from your example I thought you had only terms of the form $|x+y|\stackrel<> a$. Unfortunately this form of exponential growth is impossible to prevent for linear programs. For nonlinear programs you could square the inequality to obtain $(x+y)^2 \stackrel<> a^2$, though. $\endgroup$ – AlexR Dec 11 '14 at 21:24

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.