1

Consider an LP for which you want to add the restriction that

Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$.

Demonstrate how to formulate this.

Rodrigo de Azevedo
  • 1
Daan
  • 21
  • 1
    With such a constraint, it is no longer linear. – fkraiem Jan 27 '14 at 22:14
  • Hello, Daan. For help on how to ask homework questions (as this question appears to be), please see this post. – AnonSubmitter85 Jan 27 '14 at 22:18
  • It is for my thesis i have data I need to formulate into my LP model but have trouble with defining the restrictions – Daan Jan 27 '14 at 22:40
  • 1
    As others have pointed out, this simply is not linear. It cannot be formulated as an LP. If, however, you are willing to accept binary variables into your model, then it can be. – Michael Grant Feb 10 '14 at 14:15
  • You could try a solver for Satisfiability Modulo Theories (SMT) like Z3. Your background theory would be linear arithmetic, but then you can use arbitrary Boolean combinations of linear constraints. – Fabio Somenzi Mar 02 '17 at 16:12

2 Answers2

1

The only way I can think to do this and preserve this being a linear programming problem is to split it into two problems. In one, have the constraints $x_1<3$ and $x_2 = x_3 = 0$. In the other, have the constraints $x_1 \geq 3$, $x_2\geq 0$ and $x_3 \geq 0$.

John Habert
  • 4,001
  • Then you get if x1<3+MY then x2[>=]M(1-Y) and x2=x3 and Y=binairy – Daan Jan 27 '14 at 22:35
  • then you have to add another Y = 0/1 constraint for the fact that x2 can also be >=0, how does that work then? – Daan Jan 27 '14 at 22:36
  • It might help to give a bit more of the setup you are using. With the type of linear programming problems I've taught, the constraints I've mentioned are easy to setup and work with for a 3 variable problem. – John Habert Jan 27 '14 at 22:40
  • Indeed you need to solve two problems (or use binary variables). However, $x_1<3$ does not define a closed set. The original problem is ill-posed in the sense that an optimal solution may not exist. – LinAlg Mar 07 '18 at 17:23
0

Let the column vectors $c^T=(c_1,c_2,c_3, \ldots, c_n)\in\mathbb{R}^n$, $b^T=(b_1,b_2,b_3, \ldots, b_m)\in\mathbb{R}^m$ and a matrix $A=(A_{ij})_{\substack{1\leq i\leq m\\ 1\leq j\leq n}}\in \mathbb{R}^{n\times m}$. Consider a typical linear programming problem $$ \min_{x\in \mathscr{F}} c^Tx \hspace{1cm} or \hspace{1cm} \begin{array}{rl} \min & c^Tx\\ \mbox{such that} & x\in \mathscr{F} \end{array} \hspace{1cm} or \hspace{1cm} \begin{array}{rl} \min & c^Tx\\ \mbox{such that} & Ax\geq b\\ \end{array} $$ for $\mathscr{F}=\{x\in\mathbb{R}^n:Ax\geq b \}$. For your restriction consider the sets $$ B=\left\{x\in \mathbb{R}^n\left| \begin{array}{l} x_1\geq 3 \\ x_2> 0\\ x_3> 0 \end{array}\right.\right\} \mbox{ and } C=\left\{x\in \mathbb{R}^n\left| \begin{array}{l} x_1< 3 \\ x_2= 0\\ x_3= 0 \end{array}\right.\right\}. $$ So by adding the above restrictions we have $$ \begin{array}{rl} \min & c^Tx\\ \mbox{such that} & x\in \mathscr{F} \\ & x\in (B\cup C) \end{array} \hspace{0.5cm} or \hspace{0.5cm} \begin{array}{rl} \min & c^Tx\\ \mbox{such that} & x\in (B\cup C)\cap \mathscr{F} \end{array} $$ But $B\cup C=\{x\in\mathbb{R}: x_1\geq 0, x_2\geq 0\}$. Then your linear programming problem comes to be $$ \begin{array}{rl} \min & c^Tx\\ \mbox{such that} & x\in (B\cup C)\cap \mathscr{F} \end{array} $$ Which in block matrix notation comes to be written as $$ \begin{array}{rl} \min & c^Tx\\ \mbox{ such that} & \left\lgroup \begin{array}{c} A \\ \tilde{A} \end{array} \right\rgroup \left\lgroup \begin{array}{c} x_1\\ x_2\\ \vdots\\ x_n \end{array} \right\rgroup \geq \left\lgroup \begin{array}{c} b\\ 0\\ 0 \end{array} \right\rgroup \end{array} $$ for $$ \tilde{A}= \left\lgroup \begin{matrix} 1&0&0&\ldots &0\\ 0&1&0&\ldots &0\\ \end{matrix} \right\rgroup_{2\times n} $$

Elias Costa
  • 14,658