18
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 ...
- 2,665
17
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.
...
- 2,685
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 ...
- 276
16
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 ...
- 2,685
16
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 ...
- 5,185
13
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 ...
- 29.7k
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 ...
- 2,237
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. ...
- 5,377
10
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, ...
- 321
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 ...
- 5,799
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$, ...
- 5,873
9
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 ...
8
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 ...
- 2,667
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 ...
- 2,685
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 ...
- 22.2k
8
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 ...
- 3,283
8
votes
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 ...
- 3,283
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. ...
- 29.7k
6
votes
Linear optimization problem with user-defined cost function
If you want to implement an algorithm by your own, then we suggest you a randomized, derivative-free search, even simpler than Nelder-Mead approaches. Given a feasible solution (respecting the sum ...
- 2,649
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 ...
- 29.7k
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 ...
- 5,377
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 ...
- 29.7k
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....
- 1,571
5
votes
Accepted
Simplex Multiplier
It is explained in this link as:
Simplex multipliers are essentially the shadow prices associated with a particular basic solution. Those are the multiples of their initial system of equations such ...
- 8,290
5
votes
What is the Bound Flipping Ratio test?
When taking a step in the dual simplex method, if a dual variable is zeroed, the dual objective may continue to improve if the variable passes through zero. To maintain dual feasibility, the variable ...
- 362
5
votes
Accepted
Doubt on finding simplex's initial canonical tableau (II Phase)
In page 17 of this note by Michel Goemans, the process of converting $T_2 \iff T_1$, has been explained. If you define $Ax=b$ as $A_Bx_B+A_Nx_N=b$ (in your formulation for $T_1$, $A_B=B$) in which $...
- 8,290
5
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 ...
- 10.2k
5
votes
Accepted
Why are several of the decision variables zero at the corner point of a polytope?
Each equation constraint defines a hyperplane in $\mathbb{R}^n$, as does each lower bound ($x_i =0$). When hyperplanes intersect, the dimension of the intersection is $n$ minus the number of ...
- 29.7k
4
votes
Solving a minimization problem using a Simplex method
The only requirements for the constraints, that I am aware of, when using the simplex algorithm to solve a minimization (and maximization) problem is to include the slack and surplus variables where ...
- 151
4
votes
Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?
Here is a link that includes all the information that you need. The matrix should include all the capacity limitations on all the connections between nodes. Actually, for your example, it should be a $...
- 8,290
Only top scored, non community-wiki answers of a minimum length are eligible