A typical linear program is written as L0: $min_{x \geq 0; A^T x \leq b}$ $c^Tx$. Here, $x \in \mathcal{R}^n$, $c \in \mathcal{R}^n$, $A \in \mathcal{R}^{m \times n}$, and $b \in \mathcal{R}^m$.

Now consider a matrix $M \in \mathcal{R}^{m \times m}$ which is multiplied on both sides of the inequality constraints such that the problem becomes L1: $min_{x \geq 0; MA^T x \leq Mb}$ $c^Tx$.

What should be the constraints on M such that L0 and L1 have the same

  1. feasible region
  2. and/or the same solutions

The answer is somewhat clear in the case of equality - M should be an invertible matrix (I might be wrong here too).

What mathematical concepts should I use to reason about the above problem? Any help is highly appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.