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 ...
user avatar
  • 2,665
16 votes

Linear Programming - Motivation behind the Dual Simplex Method

The primal simplex starts with a feasible basis, and finds "a better one" while keeping feasibility. On the other hand, the dual simplex starts with an optimal basis (typically infeasible), ...
user avatar
  • 10.2k
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 ...
user avatar
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, ...
user avatar
10 votes

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

You could try changing the parameter mipfocus to 2 or 3 (https://www.gurobi.com/documentation/9.0/refman/mipfocus.html) in order to let Gurobi focus more on improving the bound or proving optimality. ...
user avatar
  • 3,477
9 votes

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

If you have a recent enough version of Gurobi, there is a tuning tool that tries to find better parameter sets than the default settings. For best results, run it for a while (at least overnight) and ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
7 votes

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

In addition to the above answers: It depends on what you want from the MIP-run. If you want to your run to find feasible solutions quickly, then keep ...
user avatar
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....
user avatar
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 ...
user avatar
  • 29.6k
3 votes
Accepted

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

There is no way to do this with CPLEX directly as far as I know, but you can use CPLEX's C++ API to code the iterative process yourself. The API allows the user to build/modify the model in C++ as ...
user avatar
3 votes
Accepted

Specific usecase of two-phase simplex algorithm

The point of the 2-phase simplex is to find a feasible initial solution (a starting point for the "normal" simplex). Indeed finding a set of $X$ values that satisfy the constraints can be hard (...
user avatar
  • 10.2k
2 votes

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

Warm starting is used predominantly when solving problems that are only slightly different, and typically when only some coefficients have changed. The idea is that many of the feasible polyhedrons' ...
user avatar

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