Does Simplex work for all standard-max problems?

[Ben2]

Mentor note: Fixed the LaTeX
1. Homework Statement
Maximize $5x_1 + 7x_2 + 3x_3$ subject to $x_1 + x_2 + x_3 \le 28, x_2 \le2 x_1$ and $x_1 \le x_3$.

Homework Equations

$x_1\ge 0, x_2\ge 0, x_3\ge 0$.

The Attempt at a Solution

Problem is workable by graphic methods, but the writer has been unable to
successfully apply the standard-max simplex algorithm. My interest is in finding a workable simplex solution and/or in determining why standard-max simplex won't work here. Thanks for the attention of all posters and site professionals!

 

[Mark44]

Mentor note: Fixed the LaTeX
1. Homework Statement
Maximize $5x_1 + 7x_2 + 3x_3$ subject to $x_1 + x_2 + x_3 \le 28, x_2 \le2 x_1$ and $x_1 \le x_3$.

Homework Equations

$x_1\ge 0, x_2\ge 0, x_3\ge 0$.

The Attempt at a Solution

Problem is workable by graphic methods, but the writer has been unable to
successfully apply the standard-max simplex algorithm. My interest is in finding a workable simplex solution and/or in determining why standard-max simplex won't work here. Thanks for the attention of all posters and site professionals!

Caveat: I haven't done any linear programming problems for many years. I haven't set up this problem, but it seems like a standard linear programming example.
The first three constraints should be rewritten as
$x_1 + x_2 + x_3 \le 28$
$-x_1 + x_2 \le 0$
$x_1 - x_3 \le 0$
and $x_1\ge 0, x_2\ge 0, x_3\ge 0$.

LaTeX Tips -- Use a pair of # characters at the beginning and end of a math expression to be rendered for inline LaTeX. Use a pair of $ characters at the beginning and end of a math expression to be rendered for standalone LaTeX.

For inequalities, use \le, not \leq, and \ge, not \geq.

 

[Ray Vickson]

Homework Statement

Maximize 5x_1 + 7x_2 + 3x_3 subject to x_1 + x_2 + x_3\leq28, x_2\leq2x_1 and x_1\leqx_3.

Homework Equations

x_1\geq0, x_2\geq0, x_3\geq0.

The Attempt at a Solution

Problem is workable by graphic methods, but the writer has been unable to
successfully apply the standard-max simplex algorithm. My interest is in finding a workable simplex solution and/or in determining why standard-max simplex won't work here. Thanks for the attention of all posters and site professionals!

State the problem as one having 3 variables and 3 constraints (plus non-negativity):
$$\begin{array}{rcl}
\max & Z = & 5 x_1 + 7 x_2 + 3 x_3 \\
\text{s.t.}&&x_1 + x_2 + x_3 \leq 28 \\
&&- 2x_1 + x_2 \leq 0 \\
&& x_1 - x_3 \leq 0 \\
&&x_1,x_2, x_3 \geq 0
\end{array}$$
So, if $s_1, s_2, s_3$ are the slack variables for constraints 1--3 and we write the objective equation as $Z - 5 x_1 - 7 x_2 - 3 x_3 = 0$ , the initial tableau for the problem is
$$
\begin{array}{ccccccc|c}
Z & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \text{RHS} \\ \hline
1 & -5 & -7 & -3 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 0 & 0 & 28\\
0 & -2 & 1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & -1 & 0 & 0 & 1 & 0
\end{array}$$

The simplex method works perfectly well here. If you do not think so, you need to show us your work and indicate where the method fails.

Note that in this problem some simplex steps may involve "degenerate" pivots, where the objective does not change from one iteration to the next, due to having some basic variables equal to 0; essentially, we change a 0 basic variable in one tableau into a non-basic variable (still zero) in another tableau. The simplex method may be "slowed down" a bit here, because it may need to pass through several such degenerate solutions on the way to the final, non-degenerate solution having no basic variables equal to zero.

 

[Ray Vickson]

Caveat: I haven't done any linear programming problems for many years. I haven't set up this problem, but it seems like a standard linear programming example.
The first three constraints should be rewritten as
$x_1 + x_2 + x_3 \le 28$
$-x_1 + x_2 \le 0$
$x_1 - x_3 \le 0$
and $x_1\ge 0, x_2\ge 0, x_3\ge 0$.

LaTeX Tips -- Use a pair of # characters at the beginning and end of a math expression to be rendered for inline LaTeX. Use a pair of $ characters at the beginning and end of a math expression to be rendered for standalone LaTeX.

For inequalities, use \le, not \leq, and \ge, not \geq.

The commands "\leq" and "\geq" are TeX/LaTeX standards, and work perfectly well in the PF implementation; I use them all the time without any problems.

 

[Mark44]

The commands "\leq" and "\geq" are TeX/LaTeX standards, and work perfectly well in the PF implementation; I use them all the time without any problems.

OK, thanks -- didn't know that. The \le and \ge operators work in MathJax, and have the advantage of requiring slightly less typing.

 

[WWGD]

The title of this thread does not seem to agree with the question in the OP. The title is , it seems, much more general while the question seems to refer to a specific question. AFAIK, the Simplex method requires some conditions for convergence. I will look them up ASAP.

 

[Ray Vickson]

The title of this thread does not seem to agree with the question in the OP. The title is , it seems, much more general while the question seems to refer to a specific question. AFAIK, the Simplex method requires some conditions for convergence. I will look them up ASAP.

Right. But let's wait until the OP responds, and shows the difficulties he/she is facing.

Anyway, there are simple "rules" that can be applied that guarantee the convergence in finitely many steps of the simplex method to an optimal resolution (either showing infeasibility or unboundedness of the problem if these properties apply, or else determining an optimal solution).

 

[kimbyd]

Mentor note: Fixed the LaTeX
1. Homework Statement
Maximize $5x_1 + 7x_2 + 3x_3$ subject to $x_1 + x_2 + x_3 \le 28, x_2 \le2 x_1$ and $x_1 \le x_3$.

Homework Equations

$x_1\ge 0, x_2\ge 0, x_3\ge 0$.

The Attempt at a Solution

Problem is workable by graphic methods, but the writer has been unable to
successfully apply the standard-max simplex algorithm. My interest is in finding a workable simplex solution and/or in determining why standard-max simplex won't work here. Thanks for the attention of all posters and site professionals!

1) This is exactly the kind of problem that the Simplex algorithm was designed to solve.
2) In some cases, however, the Simplex algorithm may stall due to degeneracy, and has worst-case exponential time complexity. Wikipedia describes these issues here.

From my reading, it should be efficient for many inputs similar to your example above, but there may be complicated situations where the algorithm stalls out and wastes quite a lot of time.

 

[Ray Vickson]

1) This is exactly the kind of problem that the Simplex algorithm was designed to solve.
2) In some cases, however, the Simplex algorithm may stall due to degeneracy, and has worst-case exponential time complexity. Wikipedia describes these issues here.

From my reading, it should be efficient for many inputs similar to your example above, but there may be complicated situations where the algorithm stalls out and wastes quite a lot of time.

Nevertheless, companies and other organizations have, for many years, been solving problems having many thousands of variables and many thousands of constraints, using Simplex. For much larger problems (say involving millions of variables and hundreds of thousands to millions of constraints), solvers sometimes use interior-point methods instead of Simplex. Some really big problems (having several hundred million variables) have been solved due to their special "network" structure, using network-flow implementations of the simplex method. Needless to say, simple textbook rules and prescriptions are not good enough for these really big cases.

 

[FactChecker]

You should recheck your Simplex calculations.
Using the Simplex implementation at https://www.zweigmedia.com/RealWorld/simplex.html, I got a solution.

The input format is:
Maximize z=5x1+7x2+3x3 subject to
x1+x2+x3<=28
-2x1+x2<=0
x1-x3<=0

It shows four Tableaus, ending with the solution
x3=7
x2=14
x1=7
z=154

 

[Ben2]

My thanks for the Mentor's corrections. I found the LaTeX inequality-symbol equivalents on this site's own "how-to" primer,
but will try to use them on this site.
FactChecker has the problem-formulation I intended. Let me apologize to anyone thrown off by my original statement.
I've recently gotten the final tableau referenced by FactChecker, with one intermediate tableau. However, the first pivot-element
was a "0" where the constant/element quotient was 0/0. I'm not sure if I'm familiar with all the "rules" mentioned in Ray
Vickson's second post.
The standard Simplex method I've seen in Finite-Math texts seemed to guarantee that each new tableau of
standard-max simplex automatically represents a basic feasible solution. My hand calculations on the given problem, mistake-ridden
though they may have been, prompt me to question that.
Re WWGD's comment, I tried setting this up as a mixed-constraint problem before finally getting the standard-max solution referenced above.
Thanks to all posters for extremely informative comments, and will access "bad" cases referenced by kimbyd.
Ben2

 

[FactChecker]

The standard Simplex method I've seen in Finite-Math texts seemed to guarantee that each new tableau of
standard-max simplex automatically represents a basic feasible solution.

Usually some artificial variables are added which are driven out (using artificially high cost values) to arrive at a feasible solution that only uses the original variables. I am not familiar with any other way to guarantee that a feasible solution can be found.

 

[Ray Vickson]

Usually some artificial variables are added which are driven out (using artificially high cost values) to arrive at a feasible solution that only uses the original variables. I am not familiar with any other way to guarantee that a feasible solution can be found.

Modern industrial-scale computer implementations of the simplex method avoid artificial variables, but instead consider starting at infeasible bases and trying to get rid of infeasibilites first, before optimizing. For example, consider the problem
$$\begin{array}{ccl}
\max & Z = & 4 x_1 + 6 x_2 - x_3 \\
\text{s.t.}&&5 x_1 + 2 x_2 + 8 x_3 = 80\\
&&4 x_1 + 9 x_2 +3 x_3 \leq 60\\
&&6 x_1 + 4 x_2 + 5 x_3 \geq 60\\
&& x_1, x_2, x_3 \geq 0
\end{array}$$
If we introduce a slack variable $s_1$ for the first inequality and a surplus variable $s_2$ for the second one, our problem can be written as that of maximizing $Z$ over the non-negative variables $x_1, x_2, x_3, s_1, s_2$ that are related by the equations
$$\begin{array}{ccc}
Z- 4 x_1 - 6x_2 + x_3 &=&0\\
5 x_1 + 2 x_2 + 8 x_3 &= &80\\
4x_1 + 9x_2 + 3x_3 + s_1 &=& 60\\
6x_1 + 4 x_2 + 5 x_3 - s_2 &=& 60
\end{array}$$
We don't even know if the problem is feasible, so determining that is the first order of business. We do not yet have an LP basis.

Without worrying about feasibility, let us choose an initial basis in which the basic variables are $x_1, s_2, s_3$. The equations can be re-written by putting basic variables on the left and non-basic variables on the right:
$$\begin{array}{ccl}
Z&=& 64 +(22/5) x_2 - (37/5) x_3 \\
x_1 &=& 16 -(2/5) x_2 - (8/5) x_3 \\
s_1 &=& -4 -(27/5) x_2 + (17/5) x_3 \\
s_2&=& 36 +(8/5) x_2 - (2/5) x_3
\end{array}$$
This basis is infeasible because it has $s_1 = -4 < 0$. Temporarily, we can think of this as a problem of trying to maximize $s_1$ (so as to drive it up towards zero), and for that reason we choose to increase $x_3$. Using the usual minimum-ratio rules to maintain feasibility of $x_1, s_2$ and to try to achieve feasibility of $s_1$, the ratios are
$$\begin{array}{l}
s_1 \;\text{ratio} = (-4)/(-17/5) = 1.176\\
s_2 \;\text{ratio} = 36/(23/5) = 7.826\\
x_1 \; \text{ratio} = 16/(8/5) = 10
\end{array}$$
The minimum ratio is for $s_1$, so $s_1$ leaves the basis and $x_3$ enters. The new equations are
$$\begin{array}{ccl}
Z &=& 940/17 -(199/17) x_2 - (37/17) s_1\\
x_1 &=&240/17 -(66/17) x_2+-(8/17) s_1\\
x_3 &=& 20/17+(37/17) x_2+(5/17)s_1 \\
s_2 &=& 520/17-(143/17) x_2 - (23/17) s_1
\end{array}$$
This gives us a feasible solution $Z = 940/17, x_1 = 240/17, x_3 = 20/17, s_2 = 520/17.$ The current $Z$-equation also shows that this solution is optimal

By the way: what would happen if we had a truly infeasible problem but did not use artificial variables? In this case the above method would eventually contain an equation something like $$\text{basic variable}\; x = -2 - 4 u_1 - 3 u_2 - \cdots$$ where $u_1, u_2, u_3 \ldots$ are the current non-basic variables. Note that the right-had-side is negative, and all the coefficients on the right are non-positive. That is, we have a negative basic variable, and increasing any of the non-basic variables up from 0 will not help (and may even make matters worse). This says that the basic variable $x$ cannot be larger than -2, so certainly cannot be non-negative. Our problem would be detected as being infeasible.

 

[FactChecker]

The standard Simplex method I've seen in Finite-Math texts seemed to guarantee that each new tableau of
standard-max simplex automatically represents a basic feasible solution.

That is true after an initial feasible solution has been found. The Simplex method will move from one feasible corner solution to another. But finding an initial feasible solution takes some tricks. Some variables ("slack" and "surplus") can be added which make it easy to start from a "psudo-feasible" solution with those variables. Then an initial Simplex phase can proceed to feasible solutions which use the original variables. The initial phase is very similar to the regular Simplex method that follows.

 

[kimbyd]

Nevertheless, companies and other organizations have, for many years, been solving problems having many thousands of variables and many thousands of constraints, using Simplex. For much larger problems (say involving millions of variables and hundreds of thousands to millions of constraints), solvers sometimes use interior-point methods instead of Simplex. Some really big problems (having several hundred million variables) have been solved due to their special "network" structure, using network-flow implementations of the simplex method. Needless to say, simple textbook rules and prescriptions are not good enough for these really big cases.

That makes good sense. From my reading, it sounds like Simplex "just works" most of the time, but if you're going to have any sort of system depend upon it, you have to be careful that it can stall out at times, and deal with those cases appropriately. There are solutions for those cases, so it's not a deal-breaker. It's just a little extra complexity that needs to be managed.

Edit:
And for any simple problem you should encounter, you should expect Simplex to work quite efficiently. Especially a textbook problem. You should only expect to encounter the pathological behavior if you're building a large-scale system designed to run a lot of Simplex calculations on a lot of different inputs.

If you try Simplex, and the answer is wrong, then there's a bug in how you're using/implementing the algorithm.

If you try Simplex, and you find it keeps cycling, then you might have hit a stall mentioned above. This shouldn't occur in textbook problems. The algorithm should eventually find a result even in this case, but it may take a little while. Still, if your number of inputs is small, even exponential-time complexity will run quickly in a computer If they're asking you to do it by hand, then it's either an error in your calculations or an error in the textbook (many textbooks have errata, so you might try to look those up if you think the textbook might have a mistake).

 

[FactChecker]

There are techniques to detect and move on from a stall. I would expect any well-used, reputable program to include such a technique. I would hesitate to recommend that a person deal with a stall himself on a very large problem. That would be extremely difficult. I find that even following the calculations on a small problem to be difficult. I could not imagine doing that with a thousand variables.

 

[kimbyd]

There are techniques to detect and move on from a stall. I would expect any well-used, reputable program to include such a technique. I would hesitate to recommend that a person deal with a stall himself on a very large problem. That would be extremely difficult. I find that even following the calculations on a small problem to be difficult. I could not imagine doing that with a thousand variables.

I definitely wasn't suggesting a person deal with the stall by hand, hence the statement that such a stall indicates a textbook error. Obviously the complexity has to be managed at the software implementation level.

 

[Ray Vickson]

That makes good sense. From my reading, it sounds like Simplex "just works" most of the time, but if you're going to have any sort of system depend upon it, you have to be careful that it can stall out at times, and deal with those cases appropriately. There are solutions for those cases, so it's not a deal-breaker. It's just a little extra complexity that needs to be managed.

Edit:
And for any simple problem you should encounter, you should expect Simplex to work quite efficiently. Especially a textbook problem. You should only expect to encounter the pathological behavior if you're building a large-scale system designed to run a lot of Simplex calculations on a lot of different inputs.

If you try Simplex, and the answer is wrong, then there's a bug in how you're using/implementing the algorithm.

If you try Simplex, and you find it keeps cycling, then you might have hit a stall mentioned above. This shouldn't occur in textbook problems. The algorithm should eventually find a result even in this case, but it may take a little while. Still, if your number of inputs is small, even exponential-time complexity will run quickly in a computer If they're asking you to do it by hand, then it's either an error in your calculations or an error in the textbook (many textbooks have errata, so you might try to look those up if you think the textbook might have a mistake).

It is possible for the Simplex method (if naively implemented) to cycle forever among a group of non-optimal solutions; i.e., stall permanently at non-optima. However, there are simple safeguards that can prevent that from happening, so stalling forever won't happen in a properly-implemented system, but stalling for quite a while sometimes will, despite all the safeguards. Commercial codes have various strategies to try to "unstall" the method, but of course, they will not work 100% of the time---just often enough to be useful. For gigantic problems, some systems will start with interior-point methods, perhaps to get near a basic feasible solution, then switch to the simplex method near the end to get an accurate, provably-optimal solution.

 

[StoneTemplePython]

I enjoyed this thread.

May I ask: does anyone here understand Semidefinite Programming? I decided over Xmas/New Years to finally learn this, though the book I selected seems to leave a lot of the theory to (not fully supported) exercises, so I am wondering if anyone here groks semidefinite algorithms.

 

[WWGD]

I enjoyed this thread.

May I ask: does anyone here understand Semidefinite Programming? I decided over Xmas/New Years to finally learn this, though the book I selected seems to leave a lot of the theory to (not fully supported) exercises, so I am wondering if anyone here groks semidefinite algorithms.

Definitely no in my part, sorry ;).