Questions tagged [primal-simplex]

For questions about the primal Simplex method.

Filter by
Sorted by
Tagged with
1 vote
1 answer
148 views

Primal-Dual Simplex Algorithm

Are there any recommended textbooks or notes to learn the details about the primal-dual simplex algorithm?
Lin Sen's user avatar
  • 25
-1 votes
1 answer
53 views

Find a basis with the primal simplex method

To solve a minimization problem using the primal simplex firstly we need a basis. If I am not wrong, a variable is basic if it enters into this equation with a coefficient of one. So I have seen ...
Everything Pro's user avatar
4 votes
3 answers
323 views

Existence of extreme points in primal and dual LP

If the nonempty feasible set of a primal LP has extreme points does its dual also have extreme points? I know that a standard form LP (nonempty) always has extreme points. But I am not sure if we can ...
Krypt's user avatar
  • 77
2 votes
2 answers
196 views

Proof on Degenerate LP program

do all degenerate LP have have an equivalent non degenerate LP? for example the following is a degenerate LP $$A=\begin{bmatrix}1&0&0&0&1&1&0\\0&1&0&1&0&1&...
someone random's user avatar
3 votes
3 answers
341 views

Question regarding primal Simplex method

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 ...
someone random's user avatar
2 votes
1 answer
316 views

Inconsistent teachings on how to choose a non basic variable to enter the basis (primal simplex)

During the primal simplex algorithm, a non-basic variable must be chosen to enter the basis. Many resources on the subject choose a variable based solely on its coefficient in the row of the tableau ...
Ram's user avatar
  • 137
4 votes
2 answers
248 views

Phase I of the simplex method and Farkas certificates

Phase I of the simplex method solves an auxiliary optimization problem to determine an initial basic feasible solution, or concludes that no such exists. Is there a way to use the solution of this ...
fmg's user avatar
  • 213
7 votes
3 answers
382 views

Can the primal Simplex Method walk all optima in linear time?

It's typical that the Simplex Method implementation exits once it finds an optimum value. However, if I want to find all optima that exist at extreme points (not those that exist along a face), is it ...
Brannon's user avatar
  • 900
17 votes
3 answers
3k views

How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms

As part of a final project for my linear programming course, I have been asked to discuss implementations of pivot algorithms, including which combinations of the ideas we have talked about in class ...
Sean Kelley's user avatar
13 votes
3 answers
5k views

When should I use dual Simplex over primal Simplex?

In Gurobi the user can change the method parameter in order to force Gurobi to use a particular method for solving MIPs. The user can, amongst others, choose ...
YukiJ's user avatar
  • 2,013