0
$\begingroup$

I learned that the Simplex Algorithm can loop forever/return a suboptimal solution whenever it's degenerate.

For $n$ variables and $m$ constraints, this is when two or more sets of $n$ constraints are tight at a particular point.

Let's say that any three of the four constraints in $\{1, 2, 3, 4 \}$ yield the exact intersection point when tight.

Say that there are two more constraints $\{ 5, 6\}$ such that constraints $\{1, 5, 6\}$ when tight yield the vertex that is optimal.

Now, say that initially $\{1, 2, 3 \}$ are tight. For the sake of argument, let $\{ 1, 2, 5\}, \{1, 2, 6\}, \{ 1, 5, 3\}, \{1, 6, 3 \}, \{5, 2, 3 \}, \{6, 2, 3 \}$ are infeasible/smaller in objective.

Then, all feasible neighbours have the same objective (due to identical vertex) or less objective. If we set our Simplex to terminate at this point, it will lead to a suboptimal solution.

Otherwise, we set our Simplex rule such that maintaining the same objective is fine. However, then, consider the following execution: $\{1, 2, 3\} \implies \{1, 2, 4\} \implies \{1, 2, 3\}$ which is a loop! Since Simplex is deterministic and does not keep track of history, this will repeat forever with the same suboptimal solution.

This is the problem with degenerate vertices. The way we deal with them is to either use Bland's rule or make sure to never visit the same tight set again. The latter will lead to something where we iterate through all the combinations of the same vertex. Ultimately, there will be some combination that will be adjacent to some more optimal combination, at which point we start making progress again.

Am I correct in my understanding? Your help is much appreciated.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

"I learned that the Simplex Algorithm loops forever/returns suboptimal solution whenever it's degenerate." No, that's not at all true. What is true is that some versions of the Simplex Algorithm (e.g. with the Most Negative Coefficient Rule) go into an infinite loop (a cycle) on some problems when they encounter degeneracy. But most of the time degeneracy is harmless and the Simplex Algorithm will reach an optimal solution.

$\endgroup$
4
  • $\begingroup$ Hi, thank you for your response—I appreciate it. My question was bit more on the side of why Simplex loops rather than when it loops. I have updated the first sentence to "can loop". Sorry for the misunderstanding, and thank you for your time. I appreciate your note on the fact that degeneracy is harmless most of the times, so something practical applications may not need to worry too much about :) $\endgroup$ Commented Mar 30 at 5:27
  • $\begingroup$ You can't get a loop $\{1,2,3\} \to \{1,2,4\} \to \{1,2,3\}$, i.e. it can't happen that the variable that leaves the basis in one pivot gets a negative entry in the objective row. Here is an example of cycling with $4$ decision variables and $3$ constraints. $\endgroup$ Commented Mar 30 at 5:58
  • $\begingroup$ Thank you for your reply. Ignoring such details, is my general idea about cycling correct? (Replace $\{ 1, 2, 3\}$ or $\{1, 2, 4\}$ with any such cyclic chain: $C_1 \implies C_2 \implies \cdots \implies C_k \implies C_1$)? $\endgroup$ Commented Apr 11 at 21:32
  • $\begingroup$ Actually it's not really a matter of "tight" constraints, it's which variables are basic vs nonbasic. $\endgroup$ Commented Apr 15 at 17:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.