3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do not you mean s_N = c_N^T-c_b^T B^{-1} N >= 0? You cannot conclude anything when s_N<=0 and s_N!=0. $\endgroup$ Nov 11, 2022 at 10:10
  • $\begingroup$ This is the reason why the rule to choose the pivot variable is important: some rules can lead to cycling, in the case you mention. See en.wikipedia.org/wiki/… $\endgroup$ Nov 12, 2022 at 19:10

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your problem is unbounded $\endgroup$ Nov 11, 2022 at 13:17
  • $\begingroup$ Certainly not since we have x5 <= 1 by the third equation (x3 + x5 = 1 for x3 >= 0). $\endgroup$ Nov 11, 2022 at 13:26
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Do you have a proof that the case doesn't exist. I have been trying to formulate one but i have no ideas. $\endgroup$ Nov 11, 2022 at 12:33
  • 1
    $\begingroup$ See my second edit, the case that none of the negative reduced cost pivots leads to an improvement does exists, then all pivots are degenerate. We can't stop in that case, we have no proof of optimality. Solvers in this case perturb the problem and try to force an order on the pivots and do them all until either optimality is proven or the objective changes again. $\endgroup$ Nov 11, 2022 at 15:05
  • $\begingroup$ The case has a probability of existing directly proportional to the scale of degeneracy at optimal bases, Yet there is a proof that there is a non degenerate LP equivalent problem which proves otherwise for a suboptimal basis. I still can't confirm that. i need a mathematical proof. $\endgroup$ Nov 12, 2022 at 7:15
  • $\begingroup$ Where do you have that from: "here is a non degenerate LP equivalent problem which proves otherwise for a suboptimal basis"? If you point to to the source of that statement, maybe I can help. Practically speaking, one can perturb the problem by small random numbers to get a non-degenerate problem, but that is not equivalent (but the trick works for optimal basis as well), the perturbation needs to be removed again. $\endgroup$ Nov 14, 2022 at 8:00
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Therefore $B$ isn't being identified as a solution to the LP. Is that a thing? $\endgroup$ Nov 11, 2022 at 13:20
  • 3
    $\begingroup$ No, it means you are not done pivoting. After one or more pivots, you will either escape the degenerate corner in a direction that improves the objective or you will stay at that corner but get to a basis with all reduced costs nonnegative. $\endgroup$
    – prubin
    Nov 11, 2022 at 16:42
  • $\begingroup$ do this cases only occur at optimality, Is there possibility that the case will occur with suboptimal basis. though all proofs say that can't happen since there is always a LP equivalent problem that is non-degenerate. although i can't seem to trust the source. $\endgroup$ Nov 12, 2022 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.