0
$\begingroup$

I'm trying to find references for a linear programming problem where the variables $x_i$ we are searching for have to be above certain thresholds $d_i$.

So that the expression of the problem is:

maximize: $\textbf{c}^{T}\textbf{x}$

subject to: $\textbf{A}\textbf{x} \leq \textbf{b}$

and $\textbf{x}\geq \textbf{d}$ with $d_i > 0$

As opposed to the canonical form:

maximize: $\textbf{c}^{T}\textbf{x}$

subject to: $\textbf{A}\textbf{x} \leq \textbf{b}$

and $\textbf{x}\geq 0 $

Does changing the last constraint from $\textbf{x}\geq 0 $ to $\textbf{x}\geq \textbf{d}$ change anything in the problem? I assume it does, but I can't find any reference to how to approach it?

$\endgroup$
1
  • $\begingroup$ This constraint can also be modelled in the $A$ and $b$ parameters, since you can make a row get something like $-x_i \leq -d_i$, which is the same as $x_i \geq d_i$. $\endgroup$
    – Joppy
    Mar 28, 2018 at 16:37

1 Answer 1

Reset to default
4
$\begingroup$

Let $u=x-d$ or equivalently $x=u+d$. Then your problem can be written as

$\max_{u} c^{T}u+c^{T}d$

subject to

$Au \leq b+Ad$

$u\geq 0$.

$\endgroup$
2
  • $\begingroup$ wait just confirming, should it be Au <= b + Ad or Au <= b - Ad $\endgroup$
    – Sticky
    Nov 6, 2021 at 8:03
  • $\begingroup$ also since d is known (like b is known), then isn't it just max_u of c_transpose * u $\endgroup$
    – Sticky
    Nov 6, 2021 at 8:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .