Let the LP problem be:

\begin{array}{ccc} \text{max } & c^{T}x & &\\ \text{subject to: } & Ax = 0 \\ &x \ge z \end{array} and feasable solution space of above problem be $S_1$.

Let the second LP problem be:

\begin{array}{ccc} \text{max } & c^{T}x' & &\\ \text{subject to: } & A'x' = 0 \\ & x' \ge z' \\ & x = S_1(x) \end{array} and feasable solution space of second problem be $S_2$.

Here $x'$ is $x$ plus additional variables. And $x=S_1(x)$ means add previous values as constraints

For example $x=[x_1,x_2,...,x_n]$ and $x'=[<x>,x_{n+1},x_{n+2}]$

  1. What is relation between $S_1$ and $S_n$ in general?

Note: i'm still thinking :)

  • $\begingroup$ By "solution space" I assume you mean just the feasible solutions, and are ignoring your objective function? What do you think happens to the feasible solution set when you add additional constraints (extra rows)? If you add extra variables, there is no way to consider one solution set as a subset of the other because the solutions are in different vector spaces. $\endgroup$ – Morgan Rodgers Oct 13 '15 at 12:55
  • $\begingroup$ yeah you're right! i have to rethink. $\endgroup$ – Hursant B Oct 13 '15 at 13:05

Consider adding new columns (and the corresponding variables) but no new rows, not changing the entries of $A$, and suppose $z'_{n+1}, z'_{n+2} \le 0$. Then the old solution space is the intersection of the new solution space with the linear subspace $\{x: x_{n+1} = x_{n+2} = 0\}$.


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.