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.

Filter by
Sorted by
Tagged with
6
votes
0answers
39 views

Demonstrating a given solution is basic for a MCFP?

Given a minimum-cost flow problem, how could I go about demonstrating that a specific solution (as sets of basic and non-basic (!) arcs that build a rooted spanning tree for a given graph) is basic ...
9
votes
1answer
73 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{...
10
votes
1answer
108 views

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 ...
9
votes
1answer
117 views

Doubt on finding simplex's initial canonical tableau (II Phase)

Good day. Given the following notation for an initial canonical tableau for a linear program in standard form: $$ T_1 = \begin{bmatrix} I & B^{-1}N & \bar{x}_{B} \\ 0^\intercal & \hat{x}...
6
votes
1answer
136 views

Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?

I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
4
votes
1answer
140 views

Having negative value for non basic variable gives a infeasible solution in simplex method?

I try to solve the following linear program with the simplex method: $$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & &...
9
votes
1answer
100 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?
8
votes
2answers
214 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 ...
17
votes
2answers
285 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) ...
12
votes
1answer
95 views

How to reduce recursion when using Gomory cutting planes to solve an integer program?

Consider the following simple integer program $$\begin{array}{ll} \text{maximize} & 3 x_1 - x_2\\ \text{subject to} & 3x_1 - x_2 \leqslant 3 \\ & -5x_1 - 4x_2 \leqslant -10 \\ & ...
12
votes
3answers
284 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 ...