# Questions tagged [simplex]

For questions related to the simplex method for linear programming (LP), which solves LPs optimally by moving iteratively from in corner point of the feasible region to a better one.

65 questions
Filter by
Sorted by
Tagged with
501 views

### Guidelines for Linear Optimization approaches?

When solving a Linear Optimization model (or Linear Program), there are a lot of solution approaches. Just to name a few: Primal Simplex Dual Simplex Ellipsoid Method (as if) ...
• 1,895
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 ...
• 646
3k views

### Where is the original Dantzig Simplex 1947 paper?

I see from here and many other sources that Dantzig invented the Simplex method in 1947. After much searching, I found that the earliest publication is this in 1956. Does anyone know where the ...
• 365
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 ...
• 2,023
250 views

• 253
604 views

### Introducing a big M variable in given equations

While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution: \begin{...
742 views

### Simplex-Implementations in professional Solvers

Which non-textbook variants (primal/dual, revised) and techniques (e.g. steepest-edge) do professional solvers like Xpress, CPLEX, CLP use, to get the best out of the simplex algorithm? This ...
• 453
1k views

### Linear optimization problem with user-defined cost function

I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem: There are a ...
• 382
274 views

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

Why is the tailing off effect only a problem in column generation? If all columns were pregenerated, and one used the simplex method, wouldn't one see the tailing off effect? Is it simply not an issue ...
• 676
274 views

### Column generation: decreasing value of restricted master problem

I am using column generation to solve a minimization problem. At a given iteration, my subproblem finds a column with reduced cost $-1$, and in the following restricted master problem, this new column ...
364 views

### What is the Bound Flipping Ratio test?

The bound flipping ratio test (BFRT) appears to be an important feature of modern Simplex implementations. What is it, and how does it work?
• 2,866
13k views

### Solving a minimization problem using a Simplex method

There is a method of solving a minimization problem using the simplex method where you just need to multiply the objective function by -ve sign and then solve it using the simplex method. All you need ...
• 213
384 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 ...
• 900
274 views

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

Idea Sometimes I encounter problems where Simplex spends many iterations for final convergence to the optimal objective value. Let's suppose, this happens when solving branch and bound-tree nodes as ...
• 1,142
292 views

191 views

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

I'm working on an implementation of the simplex algorithm. I want to solve problems in real time every 30 minutes. They could be interpreted as a classic transportation problem. I couldn't really say ...
• 41
283 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 ...
• 223
2k views

• 1,196
279 views

### Manually indicate initial basis for coin-or lp solver CLP

I have a set partitioning formulation with each constraint being an equality constraint to meet the given demand (right-hand side of the constraint). For each constraint, I have a slack and a surplus ...
• 31
940 views

### In Linear programming, how to determine if shadow price does not change linearly?

As the title says, in linear programming, is there a way to determine that the shadow price does not change linearly for a resource? I understand one way is to simulate but is there a way to tell ...
• 141
68 views

### Block Simplex Algorithm, i.e., Block Active Set for Linear Programming

What investigation has there been of Block Simplex Algorithms, i.e., block active set for Linear Programming, i.e., block pivoting? This is a follow-up to Why do active set methods or the simplex ...
• 13.5k
440 views

### On solving the Restricted Master Problem in Column Generation technique

I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
46 views

### Derivations for two formulae for obtaining optimal dual variable values from the optimal primal tableau

We're being taught Industrial Engineering and Operations Research for the first time this semester. Referring to the book by Hamdy A. Taha, I noticed the mention of two formulae for swiftly obtaining ...
140 views

### Any good write up for Dual simplex with boxed variables?

I was wondering if there is any write up that shows how to perform dual simplex with boxed variables where l <= x <= u and preferably with a small example (...
• 253