1
$\begingroup$

Consider the task of minimizing $c^Tx$ subject to the constraint that $Ax \leq b$.

I had a couple of questions in relation to the simplex algorithm (applied to this problem):

  1. How does one initialize the algorithm (i.e., identify a basic feasible solution/vertex).

  2. Given a current vertex of $\{x:Ax \leq b\}$, how does one identify an "adjacent" vertex that possibly improves the objective.

It appears that most books/texts on the simplex algorithm discuss just the standard or canonical forms of LP. My question is how can one solve the above LP directly without having to change to the standard/canonical form (which in fact is the dual of the standard LP).

$\endgroup$
  • $\begingroup$ There is not just one simplex method; see this reference for instance. $\endgroup$ – Michael Grant Mar 19 '15 at 18:38
  • $\begingroup$ Thanks Michael for the reference. What is described here seems to be some kind of primal-dual simplex. I was wondering if one could directly address points 1 and 2 for the inequality LP (similar to what one would do for the simplex over the domain $Ax=b, x\geq 0$). $\endgroup$ – user171375 Mar 21 '15 at 10:34
  • $\begingroup$ I refer you to my comment below ChrKroer's answer. You are trying too hard here. $\endgroup$ – Michael Grant Mar 21 '15 at 14:46
0
$\begingroup$

You can convert your problem to any of the other forms. The easiest thing is probably to convert it to augmented form (or slack form, if you will), since the Simplex algorithm is often described for this.

Minimizing $c^Tx$ becomes maximizing $-c^Tx$.

The constraint $Ax\leq b$ becomes $Ax + s = b, s\geq 0$, where $s$ is a new vector of slack variables.

$\endgroup$
  • $\begingroup$ I agree. My question was how can one solve the above LP directly without having to change to the standard/canonical form? I have edited my question to reflect this. $\endgroup$ – user171375 Mar 19 '15 at 13:29
  • $\begingroup$ I see. I was indeed unsure whether you wanted a direct answer for your formulation or the extension of your formulation. $\endgroup$ – ChrKroer Mar 19 '15 at 15:45
  • $\begingroup$ Kunal, I think your desire to avoid conversion is misplaced. In order to take a simplex step with $Ax\leq b$, you will have to figure out how for to move your new variable $x_i$ before one of the inequalities achieves equality; i.e, $a_j^Tx=b_j$. The distance that you can go is exactly what the slack variable $s_j$ is. The conversion from $Ax\leq b$ to $Ax+s=b$, $s\geq 0$ is essential and natural. You're computing the values of $s$ anyway; if you were to write code, you would have to store their values somewhere. $\endgroup$ – Michael Grant Mar 20 '15 at 13:03
  • $\begingroup$ Indeed, from a computational perspective it's easier to work with $Ax=b$ (transferring the non-negativity constraints to the variables) than with $Ax\leq b$. $\endgroup$ – user171375 Mar 22 '15 at 10:05

Your Answer

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