2
$\begingroup$

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

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

What should be the constraints on $M$ such that $L_0$ and $L_1$ 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?

Cross-posted on Math.SE.

$\endgroup$
2
  • 3
    $\begingroup$ Welcome to OR.SE. Note that it is usually best to wait a few days before cross-posting to avoid duplicate answers in a short time frame. $\endgroup$
    – TheSimpliFire
    May 25 at 15:31
  • $\begingroup$ Ahh! Good to know. Also, thanks for the edits :) $\endgroup$
    – pg2455
    May 25 at 15:32
4
$\begingroup$

I'll try to give a geometrical approach.

You are considering a polyhedron $$ P = \{x \in \mathbb{R}^{n} \ | \ Ax \leq b \}. $$ where $b \in \mathbb{R}^{m}$ and $A \in \mathbb{R}^{n \times m}$. (I'm using $Ax$ and not $A^{T}x$ to match the dimensions in the OP).

The easy case: no degeneracy

Let's assume that

  1. there is no primal degeneracy, i.e., no constraints are redundant w.r.t each other, and
  2. $P$ is full-dimensional (non-empty interior)

Then, $P$ has exactly $m$ facets, with the $i$-th facet being described by the $i$-th constraint $$ \sum_{j} A_{i, j} x_{j} \leq b_{i}. $$

Now, let $M \in \mathbb{R}^{m \times m}$, and consider $$ Q = \{x \in \mathbb{R}^{n} \ | \ (MA)x \leq Mb \}. $$ Geometrically, 1. asks under which condition on $M$ we have $Q = P$.

If $Q = P$, then each facet of $P$ is a facet of $Q$, and vice-versa. Thus, for every $i$, there exists $\sigma(i)$ such that the hyperplanes $$ \sum_{j} A_{i, j} x_{j} \leq b_{i} $$ and $$ \sum_{j} (MA)_{\sigma(i), j} x_{j} \leq (M b)_{\sigma(i)} $$ are (geometrically) identical.

Since the polyhedra are non-degenerate, the $i \leftrightarrow \sigma(i)$ mapping is one-to-one, i.e., $\sigma$ is permutation, which gives you permutation matrices. Assume for simplicity that $\sigma$ is the identity. From the identity between each pair of hyperplanes, you then get that $M$ is a diagonal matrix with positive coefficients.

To conclude, we get $M = D \times S$ where $D$ is diagonal with positive coefficients and $S$ is a permutation matrix. Note that this result only holds under the above two assumptions.

The hard case: degeneracy

As it's already been pointed out, depending on the data, there may be arbitrarily many valid $M$. Essentially, any redundant constraints can be aggregated in any way you want, without changing anything to the feasible region.

If you can isolate a set of non-redundant constraints, then you might apply the above result, combined with some (positive?) combination of the redundant constraints. Obviously, there may exist multiple sets of non-redundant constraints, and you will likely see a combinatorial explosion there.

$\endgroup$
1
  • $\begingroup$ Thank you very much! It makes sense. D with positive coefficients is like multiplying constraints with a positive number on both sides of the equation. it leaves the region unchanged. $\endgroup$
    – pg2455
    Jun 4 at 9:25
2
$\begingroup$

Permutation matrices will preserve the feasible region. Since you are not modifying the objective function, the solution will also be the same.

$\endgroup$
2
  • $\begingroup$ Ahh! Yes. I forgot to mention those matrices in the question. Are there any other matrices other than permutation matrices? $\endgroup$
    – pg2455
    May 26 at 10:27
  • $\begingroup$ If you allow for degeneracy and redundancy, there can be arbitrary many matrices preserving the feasible region. Imagine an empty feasible region because of a single infeasible constraint, e.g. sum(x) <= -1, then all other constraints can change arbitrarily without changing the feasible region. So, I guess, the question only makes sense for a well-defined region with all constraints strictly defining a segment of its border. $\endgroup$
    – mattmilten
    May 26 at 10:44

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.