Skip to main content
25 votes
Accepted

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

There was an excellent lecture by Bob Bixby in 2015 at the Zuse Institute Berlin (ZIB) as part of Combinatorial Optimization at Work 2015. Bixby founded CPLEX and Gurobi, 2 of the 3 leading commercial ...
Mark L. Stone's user avatar
20 votes

Simplex-Implementations in professional Solvers

There is a series of three lectures of Robert Bixby (the Bi in Gurobi) on Solving Linear Programs: The Dual Simplex Algorithm. Have a look at the third part Implementing the algorithm where he talks ...
Marcus Ritt's user avatar
  • 2,725
19 votes
Accepted

Where is the original Dantzig Simplex 1947 paper?

Introduction When Dantzig devised the algorithm, he was working at the Pentagon and thus many things would have been designated as classified in the military. There are a few more details provided in ...
TheSimpliFire's user avatar
  • 5,412
18 votes
Accepted

Simplex-Implementations in professional Solvers

First of all, usually implementations are centered around the revised dual simplex, not the primal (even though solvers will still use a primal simplex method implementation for some tasks in the ...
Michael Feldmeier's user avatar
18 votes
Accepted

Guidelines for Linear Optimization approaches?

Let's start with the easy one: Ellipsoid Method Never use it. Even though it might appear efficient in the complexity-theory sense, it performs terrible and suffers heavily from numerical issues. ...
Michael Feldmeier's user avatar
16 votes
Accepted

Solving a minimization problem using a Simplex method

It has nothing to do even with linear programming. It's a simple mathematical fact: $$\min \left( f \left( x \right) \right) = - \max \left( -f \left( x \right) \right)$$ which still holds when you ...
oszkar's user avatar
  • 276
14 votes
Accepted

Linear optimization problem with user-defined cost function

First, the problem is not a linear optimization problem, at least not for the objective function shown (which is nonlinear due the conditional portion in lines 10-13 and particularly the division by ...
prubin's user avatar
  • 39.3k
13 votes

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

One of the best resource I know is the series of lectures on linear programming that was part of the CO@work workshop 2020. I especially recommend the lectures by Bob Bixby (he is the "bi" ...
mtanneau's user avatar
  • 4,173
13 votes
Accepted

How to reduce recursion when using Gomory cutting planes to solve an integer program?

The slow convergence of the Gomory cuts was well-known and source of frustration for the field up until the 90s. It seemed that Gomory cuts would be a cute idea, but not one that would lead to any ...
Michael Trick's user avatar
12 votes

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

The videos linked in the other answers contain some of what I will write here but both my writing and the videos are still only scratching on the surface of actual simplex implementations. I'll try to ...
Philipp Christophel's user avatar
12 votes

Why is it called the "Simplex" Algorithm/Method?

In the open-access paper George B. Dantzig, (2002) Linear Programming. Operations Research 50(1):42-47, the mathematician behind the simplex method writes: The term simplex method arose out of a ...
Henrik Alsing Friberg's user avatar
12 votes
Accepted

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

Converting previous comments into an answer: Unfortunately this is not the case for general LPs. To see this, consider an LP with exponentially many extreme points and a constant objective function. ...
Sune's user avatar
  • 6,552
11 votes

When should I use dual Simplex over primal Simplex?

Dual simplex is the method of choice for resolving an LP if you have an optimal solution and you change the problem by modifying the feasible region. Ranging the RHS, adding cuts or branching in MIP, ...
mjsaltzman's user avatar
10 votes

Simplex algorithm and extreme points

the Simplex algorithm iterates from extreme point to extreme point Technically, no. The simplex algorithm iterates from basis to basis. It just happens that feasible basic solutions correspond to ...
mtanneau's user avatar
  • 4,173
9 votes

Guidelines for Linear Optimization approaches?

Bob Bixby (as just one representative of many computational guys) talks regularly about progress in LP and MIP solving; for the 50th anniversary issue of "Operations Research" he wrote an article on ...
Marco Lübbecke's user avatar
9 votes
Accepted

Having negative value for non basic variable gives a infeasible solution in simplex method?

From the slack form we can observe two things about your starting point $(x_1,x_2) = (0,0)$. The starting point is not primal feasible. This follows from the fact that not all variables $x_1$, $x_2$, ...
Kevin Dalmeijer's user avatar
9 votes

When should I use dual Simplex over primal Simplex?

In addition to @Michael's comment you have to distinguish between the algorithm used to solve the root node of a problem and the algorithm used for the nodes in the branch-and-bound tree. gurobi (and ...
JakobS's user avatar
  • 2,767
9 votes
Accepted

Why is the tailing off effect only a problem in column generation?

"Tailing-off effect" is a generic term that refers to an something like "the algorithm is hitting a plateau and progress becomes very slow towards the end". In other words: after ...
mtanneau's user avatar
  • 4,173
8 votes
Accepted

When should I use dual Simplex over primal Simplex?

Not an expert on simplex, but here's my attempt on an answer: In general, the solution of the (previous) LP Relaxation will no longer be primal feasible when the primal LP is tightened (e.g. new cut ...
Michael Feldmeier's user avatar
8 votes
Accepted

Simplex (GLPK) doesn't find a feasible solution on this simple assignment problem, but there is an obvious one

Maybe the unnecessarily large value for $A$ is causing numerical trouble. Try instead $A = \max_{i,j} p_{i,j} = 9$. Probably your $=0$ in the declaration of $x$ should be $\ge 0$. In fact, you ...
RobPratt's user avatar
  • 32.3k
8 votes

Column generation: decreasing value of restricted master problem

The reduced cost is the instantaneous rate of change as you increase the value of the new variable from 0. The actual impact of the new variable on the objective function is piecewise linear and ...
prubin's user avatar
  • 39.3k
8 votes
Accepted

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

As long as you choose something with a negative reduced cost, the simplex algorithm "works". See https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec13.pdf for examples of ways you can ...
Michael Trick's user avatar
7 votes
Accepted

Linear Programming: Integer and non-integer decision variables

For the first question, suppose you somehow knew which days would be production days and fixed the values of the $z_t$ variables accordingly, while allowing $q_t$ and $i_t$ to be continuous variables. ...
prubin's user avatar
  • 39.3k
7 votes
Accepted

Help me reproduce this tableau from the 'Integer Programming' book

The dictionary is correct. You can check your work by using Robert Vanderbei's Simple Pivot Tool: The following sequence of pivots yields the same optimal dictionary: ...
RobPratt's user avatar
  • 32.3k
6 votes

Linear optimization problem with user-defined cost function

If you want to implement an algorithm on your own, then we suggest a randomized, derivative-free search, even simpler than a Nelder-Mead approach. Given a feasible solution (respecting the sum equal ...
Hexaly's user avatar
  • 2,986
6 votes

Is the iteration-limited Simplex dual solution of a MIP node useful?

It is common practice for MIP solvers to solve node LPs (other than at the root node) via dual simplex. I can't say with certainty that they terminate dual simplex prematurely if the objective value ...
prubin's user avatar
  • 39.3k
6 votes

Is the iteration-limited Simplex dual solution of a MIP node useful?

Yes, you can solve the dual and use that as a (weaker) bound than the optimal solution of the LP. This leads to the trade off between faster processing nodes vs processing more nodes. This approach is ...
Sune's user avatar
  • 6,552
6 votes

warmstarting simplex algorithm- how much can problems differ from each other?

Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about ...
prubin's user avatar
  • 39.3k
6 votes

warmstarting simplex algorithm- how much can problems differ from each other?

I actually have quite a few points. As usual, things are not as clear cut. I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model....
Erwin Kalvelagen's user avatar
6 votes
Accepted

Interpretation of Reduced Costs

The reduced costs (or marginal costs), tell you by how much the objective function will increase (or decrease), if the corresponding variable increases by one unit. So if you are minimizing, the ...
Kuifje's user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible