Questions tagged [dual-simplex]

For questions about the dual Simplex method.

Filter by
Sorted by
Tagged with
0 votes
0 answers

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 ...
Pedro García's user avatar
3 votes
1 answer

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}$...
Quentin PLOUSSARD's user avatar
3 votes
1 answer

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, ...
John's user avatar
  • 131
2 votes
4 answers

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 (...
Morpheus's user avatar
  • 253
4 votes
1 answer

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 ...
Ram's user avatar
  • 137
4 votes
2 answers

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
11 votes
1 answer

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 ...
MathMan's user avatar
  • 213
3 votes
0 answers

How is the dual revised simplex method equivalent to running the RSM on the dual problem?

I've seen the claim (in the title) several places, but can't quite understand why it's true. From what I understand so far, the revised simplex method solves an LP in standard computational form, $$\...
LinearDysfunctional's user avatar
4 votes
3 answers

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 ...
ORpyhton's user avatar
17 votes
3 answers

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
2 votes
1 answer

Specific usecase of two-phase simplex algorithm

The problem below aims to find to most optimal way to transport the fuel : A company Er must transport a type of fuel from its two refineries Ra and Rb to its two points of sale PV1 and PV2. The ...
JirenOppaik's user avatar
12 votes
3 answers

Settings for a faster solution of a MILP (GUROBI, python)

Using GUROBI with python. When solving a MILP, I notice that the incumbent is very early (25sec) at the optimal point but the best bound is so slow to fall (maximization problem) that it takes ages (...
Makis Karasavvidis's user avatar
3 votes
0 answers

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 ...
Sakazuki Akainu's user avatar
10 votes
1 answer

How to access neighboring extreme points to an optimal extreme point of an LP?

Suppose that I have access to an optimal non-degenerate extreme point of an LP. I need to find some $\epsilon$-optimal extreme points. That is, a point $x$ where $c'x \le z^{*} + \epsilon$. One way ...
Hamed Rahimian's user avatar
5 votes
0 answers

Construct a direction of recession of the dual that is from growth to dual function

Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $ A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose ...
justlearningmath's user avatar
8 votes
2 answers

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 ...
Gehhilfe's user avatar
  • 443
13 votes
3 answers

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