Skip to main content

# Questions tagged [dual-simplex]

For questions about the dual Simplex method.

18 questions
Filter by
Sorted by
Tagged with
1 vote
1 answer
121 views

### Dual to Primal conversion

I recently tried to solve a primal minimization problem using its maximization dual. In the optimal simplex tableau of the dual, there was a slack variable and only one dual variable in the basis. So, ...
0 votes
0 answers
42 views

### Proof of Dual Simplex Ratio Test

I have been trying to find proof of the ratio test for Dual Simplex, that is, selecting the variable that enters the base. Specifically, I was interested in knowing why by making that choice, reduced ...
• 109
3 votes
1 answer
260 views

### Warm starting a LP problem with PuLP and Gurobi

I have a set of many similar linear programs (LP). All these LPs have the same objective function, and almost all constraints are the same. The only difference is for one linear constraint $f(x)=a_{i}$...
3 votes
1 answer
228 views

### Dual problem in IBM CPLEX

Im solving n-dimensional Knapsack problem as LP problem. I noticed that sometimes dual LP problem may be solved much faster than primal. My test problem contains 500k variables and 50k constraints, ...
• 131
2 votes
4 answers
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
4 votes
1 answer
493 views

### Finding a dual feasible basis for use with the dual simplex algorithm

I have learnt that the dual simplex method requires reduced costs to be non-negative or else it cannot be used. I wanted to know what could be done to find a dual feasible basis and came across this ...
• 137
4 votes
2 answers
274 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
11 votes
1 answer
2k views

### Linear Programming - Motivation behind the Dual Simplex Method

I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current ...
• 213
3 votes
0 answers
148 views

8 votes
2 answers
741 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
14 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 ...
• 2,023