# Simplex updates for the inequality LP

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).

• There is not just one simplex method; see this reference for instance. – Michael Grant Mar 19 '15 at 18:38
• 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$). – user171375 Mar 21 '15 at 10:34
• I refer you to my comment below ChrKroer's answer. You are trying too hard here. – Michael Grant Mar 21 '15 at 14:46

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.
• 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. – Michael Grant Mar 20 '15 at 13:03
• 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$. – user171375 Mar 22 '15 at 10:05