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
4 votes
1 answer
156 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 ...
  • 65
2 votes
1 answer
156 views

Inconsistent teachings on how to choose a non basic variable to enter the basis (primal simplex)

During the primal simplex algorithm, a non-basic variable must be chosen to enter the basis. Many resources on the subject choose a variable based solely on its coefficient in the row of the tableau ...
  • 65
8 votes
1 answer
205 views

Column generation: decreasing value of restricted master problem

I am using column generation to solve a minimization problem. At a given iteration, my subproblem finds a column with reduced cost $-1$, and in the following restricted master problem, this new column ...
2 votes
0 answers
62 views

Simplex Method Manual pivoting in GLPK for a Warm Start

My question is kind of related to this 2015 post at Stackoverflow. About Simplex method tableau pivoting in Linear Programming -- this is proving to be difficult in GLPK.. I am using Linux, GLPK 5.0 ...
1 vote
1 answer
66 views

SoPlex basis file format

I'm running SoPlex from the command line to solve some linear programming problems. I'd like to get the basis of the solution, so I use the --writebas flag. However,...
  • 213
4 votes
2 answers
89 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 ...
  • 213
4 votes
1 answer
63 views

Upper bound on number of pivots to escape a degenerate point

Is it always possible to escape a degenerate point by a single pivot, or is it possible that several pivots are required? In other words is it possible to get away from a degenerate point by a single ...
  • 469
1 vote
0 answers
75 views

How to make unconstrained variables non-negative (as in excel solver) in AMPL?

This is a sequencing problem. I've got this variables ...
14 votes
4 answers
2k views

Where is the original Dantzig Simplex 1947 paper?

I see from here and many other sources that Dantzig invented the Simplex method in 1947. After much searching, I found that the earliest publication is this in 1956. Does anyone know where the ...
  • 335
7 votes
1 answer
246 views

Why are several of the decision variables zero at the corner point of a polytope?

I have the following equational Linear Program: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align} The matrix $A$ is $m\times n$, where $m\le n$, $c\in \mathbb{...
6 votes
0 answers
84 views

Dual instability, degeneracy, tailing off effect - Which are the causes and which are the effects?

Dual instability, degeneracy, and the tailing off effect are often mentioned together in papers. However, I cannot seem to find a clear explanation on which of these cause the other and vice versa? ...
  • 469
7 votes
1 answer
128 views

Why is the tailing off effect only a problem in column generation?

Why is the tailing off effect only a problem in column generation? If all columns were pregenerated, and one used the simplex method, wouldn't one see the tailing off effect? Is it simply not an issue ...
  • 469
7 votes
3 answers
341 views

Can the primal Simplex Method walk all optima in linear time?

It's typical that the Simplex Method implementation exits once it finds an optimum value. However, if I want to find all optima that exist at extreme points (not those that exist along a face), is it ...
  • 605
4 votes
1 answer
270 views

Why is it called the "Simplex" Algorithm/Method?

I have been trying to learn more about the Simplex Algorithm/Method. In particular, I am interested in knowing why this algorithm is called the "Simplex Algorithm". For instance, when ...
  • 1,839
5 votes
1 answer
1k views

Interpretation of Reduced Costs

I am looking for an answer to a question I can't quite get behind. (continuation of Linear Programming: Integer and non-integer decision variables) I am given the following mathematical optimization ...
  • 123
6 votes
1 answer
930 views

Linear Programming: Integer and non-integer decision variables

I am looking for an answer to a question I can't quite get behind. I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\...
  • 123
4 votes
1 answer
407 views

Best way to add dummy to transportation problem? Zero cost will be always chosen first?

I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply. In literature, dummy ...
3 votes
2 answers
96 views

Transformations that leave the linear program unchanged

A typical linear program is written as $$L_0:\min_{x \geq 0; A^\top x \leq b}c^\top x.$$ Here, $x \in \mathbb{R}^n$, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$. ...
  • 141
4 votes
3 answers
136 views

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 ...
3 votes
1 answer
601 views

Simplex (GLPK) doesn't find a feasible solution on this simple assignment problem, but there is an obvious one

Problem Assign 11 projects to 11 students, based on their preference. For this example, each students chooses only one project, for simplicity shake (as shown below). Student 1 one chooses project 1, ...
6 votes
0 answers
164 views

Provide basic solution to CLP

I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
6 votes
2 answers
471 views

Simplex algorithm and extreme points

For this question my short-hand is LP = linear program, BFS = basic feasible solution, SEF = standard equality form. Since the Simplex algorithm iterates from extreme point to extreme point (...
  • 201
5 votes
1 answer
1k views

Simplex Multiplier

I am reading through a book which provides an example of a linear program given by \begin{align}\min&\quad-24y_{1}-28y_{2}\\\text{s.t.}&\quad6y_{1}+10y_{2} \leq 2400\\&\quad8y_{1}+5y_{2} \...
  • 253
2 votes
0 answers
114 views

Simplex - Network flow problem : Arc from 1 to P with infinite capacity

The Network - Maximum flow problem below aims to find the maximum flow using simplex method : With the LP as follow : LP : \begin{Bmatrix} Z(Max) = \sum_{i=1}^{m} fi \\ Af =0 \end{Bmatrix} ...
8 votes
2 answers
858 views

Linear optimization problem with user-defined cost function

I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem: There are a ...
  • 382
6 votes
0 answers
81 views

Proof that the leaving variable cannot be selected as the entering one in the next round

Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
4 votes
0 answers
168 views

Does anyone have the criss cross algorithm programming code to solve linear programming problems?

I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...
  • 81
2 votes
1 answer
117 views

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 ...
3 votes
0 answers
206 views

On solving the Restricted Master Problem in Column Generation technique

I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
3 votes
1 answer
199 views

Manually indicate initial basis for coin-or lp solver CLP

I have a set partitioning formulation with each constraint being an equality constraint to meet the given demand (right-hand side of the constraint). For each constraint, I have a slack and a surplus ...
  • 31
7 votes
2 answers
244 views

Is the iteration-limited Simplex dual solution of a MIP node useful?

Idea Sometimes I encounter problems where Simplex spends many iterations for final convergence to the optimal objective value. Let's suppose, this happens when solving branch and bound-tree nodes as ...
  • 1,112
7 votes
2 answers
9k views

Solving a minimization problem using a Simplex method

There is a method of solving a minimization problem using the simplex method where you just need to multiply the objective function by -ve sign and then solve it using the simplex method. All you need ...
3 votes
0 answers
45 views

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 ...
3 votes
1 answer
329 views

In Linear programming, how to determine if shadow price does not change linearly?

As the title says, in linear programming, is there a way to determine that the shadow price does not change linearly for a resource? I understand one way is to simulate but is there a way to tell ...
  • 141
5 votes
0 answers
111 views

All optimal solutions

I have a following problem: If I have some function $aX+bY+cZ+mD+nF$ and I want to maximize it and have some constraints, how can I find ALL solutions for this maximum value of the function? To sum ...
5 votes
1 answer
130 views

Preemptive Goal programming by fixing nonbasic variables with non-zero reduced costs

I have been using the method of fixing nonbasic variables with non-zero reduced costs to do preemptive goal programming. It works for the most part. But I have recently noticed in a certain instance ...
7 votes
1 answer
786 views

Negative reduced cost for basic variable

I am observing something unusual : after solving a linear program, some basic variables have negative reduced costs (instead of $0$) : ...
  • 10.9k
6 votes
0 answers
75 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
1 answer
367 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
1 answer
165 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
1 answer
188 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
1 answer
465 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
1 answer
1k 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} & & &...
8 votes
1 answer
251 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
2 answers
470 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 ...
  • 443
18 votes
2 answers
420 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
1 answer
180 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 \\ & ...
  • 223
13 votes
3 answers
3k 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 ...
  • 1,943