1
$\begingroup$

My variables are [$x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8$]. All are continuous variables within the range of $[0,1]$. I want to impose a conditional constraint which is as follows:

if $x_6 \gt 0$ then $x_1 + x_3 =1$.

How can I go about doing this using linear inequalities?

$\endgroup$
  • $\begingroup$ What happen, if $x_6=0$ ? $\endgroup$ – callculus Oct 29 '15 at 10:46
2
$\begingroup$

The possible constraints of a linear program are of the form $$ a^\top \, x \, \triangle \, \beta, \quad \triangle \in \{ =, \le, \ge \} $$ These are statements about the solution vector $x$ being part of the hyperplane or lying in a half space below or above an affine hyperplane with normal $a$.

Your constraints would require half a hyperplane only, which is not possible to express by a set of full hyperplanes.

Note: The following all include the constraints $x_i \in [0,1]$, restricting the search space to a cube.

Here is a visualization in $(x_1, x_2, x_6)$:

problem 1

The search space is the union of the green square $x_6 = 0$ and the purple rectangle without bottom border $x_1 + x_2 = 1 \wedge x_6 > 0$. We can only model $x_1 + x_2 = 1$, but the extra part $x_1 + x_2 = 1 \wedge x_6 = 0$ is part of the first region, so we do not leave the search space. The solution can be found by running two optimizations and then selecting the best result.

This is a visualization of the second problem in $(x_1,x_2,x_3)$ only:

problem 2

The search space is the union of the yellow square $x \mid x_2 = 0$ and the purple square without the foremost side $x_2 > 0 \wedge x_3 = 0$. Again run as two problems and pick the best solution.

For all variables we hope as well, to describe the search space as union of spaces that can be modelled by LP constraints.

  • $X_1 = \{ x \mid x_2 = x_4 = x_6 = 0 \}$
  • $X_2 = \{ x \mid x_2 > 0 \wedge x_3 = x_5 = x_7 = 0 \}$
  • $X_3 = \{ x \mid x_2 = 0 \wedge x_4 > 0 \wedge x_5 = x_7 = 0 \}$
  • $X_4 = \{ x \mid x_2 = x_4 = 0 \wedge x_6 > 0 \wedge x_7 = 0 \}$

This seems to be covering the whole search space $X$, e.g.

  • $X_5 = \{ x \mid x_2 > 0 \wedge x_4 > 0 \wedge x_3 = x_5 = x_7 = 0 \subsetneq X_2$
  • $X_6 = \{ x \mid x_2 > 0 \wedge x_6 > 0 \wedge x_3 = x_5 = x_7 = 0 \subsetneq X_2$
  • $X_7 = \{ x \mid x_2 > 0 \wedge x_4 > 0 \wedge x_6 > 0 \wedge x_3 = x_5 = x_7 = 0 \subsetneq X_2$
$\endgroup$
1
$\begingroup$

This answer is somewhat informal, but: If you could formulate such "conditional constraints" in linear programming, it stands to reason that you should also be able to formulate constraints like "if $x_i > 0$, then $x_i = 1$"; but this would allow you to represent arbitrary $0,1$-integer programs, and $0,1$-integer programming is NP-hard while linear programming is polynomially solvable.

$\endgroup$
  • $\begingroup$ Very good point! $\endgroup$ – A.Γ. Oct 29 '15 at 15:55
  • 1
    $\begingroup$ The only minor thing: if $x>0$ then $x=1$ (i.e. strict inequality). $\endgroup$ – A.Γ. Oct 29 '15 at 18:34
  • $\begingroup$ Oops, yes, of course. $\endgroup$ – Gregory J. Puleo Oct 29 '15 at 19:15
  • $\begingroup$ Can the problem be solved if I introduce integer variables [0 1] for each existing continuous variable to track if that variable is >0 or =0 and solve using mixed integer linear programming? $\endgroup$ – user1234 Oct 30 '15 at 6:57
  • $\begingroup$ @user1234 yes, I think something like that would be the most natural way of doing this -- you can use the integer variables to guarantee that the constraints you don't want to use are automatically satisfied $\endgroup$ – Gregory J. Puleo Oct 30 '15 at 14:58
1
$\begingroup$

The problem is that the conditional constraint is not convex: take $z_1=(x_1,x_3,x_6)=(1,0,1)$ and $z_2=(1,1,0)$, then $$ \frac12(z_1+z_2)=(1,1/2,1/2) $$ is not in the set. Therefore, it cannot be, in general, described by linear inequalities which are convex (unless the rest of the constraints are so special that the intersection takes away this trouble, but it is very particular case).

What you can do is to split your LP in two optimizations: one with $x_6>0$ and $x_1+x_2=1$ and another with $x_6=0$. Take the solution that has the smaller objective.


UPDATE: As I understand, the problem takes the following form: denote the variables in the first set as $(x_1,x_2,x_3,x_4)$ and those in the second one as $(y_1,y_2,y_3,y_4)$, so the overall vector looks like $$ (x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4),\qquad x_i,y_j\in[0,1] $$ and no more constraints except for the mentioned in the question that $$ k=1,2,3\colon\quad s_k=\sum_{j=1}^ky_j>0\quad\Rightarrow\quad t_k=\sum_{i=k+1}^4x_i=0 $$ which can be shortly written as $s_kt_k=0$. Thus, the problem is

  • Some linear equalities and inequalities, and
  • Some pairwise products are zeros.

This is precisely the form of the KKT condition for linear programming (feasibility and complementary slackness principle). The problem is not linear, but can quite effectively (in polynomial time) be solved by the primal-dual interior point method for LP. See, for example, Chapter 14 in this book.

$\endgroup$
  • $\begingroup$ @user1234 Sounds like the complementary slackness principle in KKT: $x_6(x_1+x_2-1)=0$. It is only bilinear, unfortunately, and often are solved by considering cases $=0$ and $>0$ for all such variables. I would be surprised if there were one master LP that covered all the cases. $\endgroup$ – A.Γ. Oct 29 '15 at 11:00
  • $\begingroup$ @user1234 I do not understand what the last/first non-zero values mean. Could you give more details by editing the main question body where you have more space for them? It would be good to state the problem completely too, otherwise answerer may miss important features. $\endgroup$ – A.Γ. Oct 29 '15 at 11:42
  • $\begingroup$ updated above. Please have a look. $\endgroup$ – user1234 Oct 29 '15 at 12:02
  • $\begingroup$ @user1234 I wrote my thoughts on the problem. $\endgroup$ – A.Γ. Oct 30 '15 at 9:22
  • $\begingroup$ Thanks @A.G. I am a bit confused about a few things as I am not familiar with the primal-dual approach. Does matlab support the primal dual approach? The constraints will be : $y_1(x_2+x_3+x_4)=0$ $y_2(x_3+x_4)=0$ $y_3(x_4)=0$ How will i represent the multiplication in terms of the Aeq and beq matrix? $\endgroup$ – user1234 Oct 30 '15 at 12:06

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.