Question regarding primal Simplex method

Question

Given the following degenerate optimization problem \begin{align}\min&\quad c^Tx\\\text{s.t.}&\quad Ax=b,\\&\quad x\ge 0\end{align} Using primal simplex algorithm (either revised or tabular) what exactly is implied when all directions given by negative elements of $c_N^T-c_B^TB^{-1}N$ don't improve solution. if this case doesn't exist can we prove it, otherwise will $B$ be optimal in such situation.

Edit:
we only are considering single column pivots. And similarly a case where a given basic solution, simplex indicates there is improvement yet non of the pivot actually improve objective function regardless of whether the basic solution is optimal.

Answer 1

In the simplex method we only consider univariate search directions relative to the considered basis (i.e., picking one column from $x_N$ to move). In the situation you describe, all univariate search directions that are improving (i.e., negative reduced cost) are assumed degenerate (i.e., maximum step length within feasible set is zero). This is indeed possible, but doesn't exclude the existence of improving multivariate search directions and so doesn't imply anything about your solution.

Example Let $$\min c^Tx\\\text{s.t}Ax=b,\\x\ge 0$$

and let's throw some data into Julia:

c = [1 1 0 1 -2]';
A = [1 0 0 1 -1; 
     0 1 0 1 -1; 
     0 0 1 0  1]
b = [0 0 1]';

In the initial singleton basis there is only one improving univariate search direction ($x_4$), but you can't increase the value of $x_4$ from zero without breaking bounds on $x_1$ and $x_2$. Hence this is a case where, to quote the question, "simplex indicates there is improvement yet non of the pivot actually improve objective function":

bas=[1,2,3]
B=A[:,bas];
x=zeros(5); x[bas]=B\b; x    # 0 0 1  0 0
y=B'\c[bas]; c-A'*y          # 0 0 0 -1 0

Nevertheless, after the degenerate pivot with steplength 0, we find a new improving univariate search direction ($x_5$):

bas=[1,4,3];
B=A[:,bas];
x=zeros(5); x[bas]=B\b; x    # 0 0 1 0 0
y=B'\c[bas]; c-A'*y          # 0 1 0 0 -1

This time it is a nondegenerate pivot with steplength=1, leading to the optimal solution:

bas=[1,4,5]; B=A[:,bas];
x=zeros(5); x[bas]=B\b; x    # 0 0 0 1 1
y=B'\c[bas]; c-A'*y          # 0 1 1 0 0

This behavior occurs because the improving multivariate search direction $(\Delta x_4, \Delta x_5) = (1,1)$ was available to us in the initial basis, but we couldn't follow it using the simplex method, so we had to go through a degenerate pivot (in general there can be more) to turn it into a univariate search direction.

Answer 2

Assuming the current basis B is primal feasible, i.e. the primal solution x* computed for basis B satisfies all constraints, and that I interpret your notation correctly, this would imply that the dual solution (all equalities means duals are free) and reduced costs (only lower bounds) are dual feasible, which means B is an optimal basis.

Edit: I interpreted "don't improve solution" as there are no negative reduced cost, i.e. there are no negative elements. This might not be how the question was intended. I guess the answer then is, if there are negative directions, they improve the solution, so this case does not exist.

Edit again: Well, in the case of degeneracy, the step length for all negative elements can be zero, so that means a single pivot might not change the objective, but we can also not conclude optimality in this case because the reduced cost are not feasible and we hence have no certificate of optimality. I clearly misunderstood the question the first time I read it, sorry about that.

Answer 3

This can be a case where you already reached optimality, and at last iterations you are stuck at degeneracy