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.
63
questions
0
votes
2
answers
48
views
The dual values and change in the variables values
For a constraint as Ax <= b, the dual shows the change in the objective function if the RHS increases by 1 unit. Now my question is that how we can determine how the optimal values will change by 1 ...
- 389
0
votes
0
answers
80
views
why the -1 in basis column for simplex tableau?
When I look at the tableau generated by Gurobi for a simple 3D problem with five constraints, I get this:
I expected to not have a -1 in basis columns 4, 5, 6 (referring to slack variables 1, 2, 3 if ...
- 892
2
votes
2
answers
498
views
How to handle strict inequalities?
Perhaps two trivial questions: What kind of problem is the following (please note the strict inequality)? How do we solve it?
$$\min_{x\geq 0}\{c^\top x: Ax < b\}$$
- 1,641
0
votes
0
answers
68
views
Simplex algorithm for stochastic constraints?
The OR-Notes by J E Beasley states:
Hence the problem:
minimise 5x+6y
subject to:
Prob(a1x + a2y >= 3) >= 1-alpha
x,y >= 0
...
- 501
3
votes
0
answers
52
views
Block Simplex Algorithm, i.e., Block Active Set for Linear Programming
What investigation has there been of Block Simplex Algorithms, i.e., block active set for Linear Programming, i.e., block pivoting? This is a follow-up to Why do active set methods or the simplex ...
- 13.1k
1
vote
0
answers
51
views
explain Givens rotation chain for maintaining Cholesky factorization
I'm attempting to implement the dual face algorithm from Pan's book chapter 22 (https://link.springer.com/book/10.1007/978-981-19-0147-8).
The part in question is pasted here:
Can you please explain ...
- 892
2
votes
1
answer
275
views
Are there two types of 'slack variables'?
In simplex algorithm, in order to handle inequation constraints, we need to convert them into equations by introducing so-called 'slack variables', like
$$
\mathbf{a}^T\mathbf{x} + b \leq 0\quad\...
- 1,036
5
votes
1
answer
205
views
Short cuts when using the simplex algorithm
I haven't really kept myself up to date with research on the simplex algorithm for several years. I have taught linear programming, but it has not focused on the cutting edge of things.
I remember ...
- 6,352
1
vote
1
answer
33
views
Computing simplex tableu for a given basis
I found the following problem in my book.
I know that I can compute the simplex tableau , let's call it S for a basis X_b=(x_1, x2, x_5)^T as ...
- 235
2
votes
4
answers
132
views
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 (...
- 253
4
votes
1
answer
441
views
Help me reproduce this tableau from the 'Integer Programming' book
From the Integer Programming book by Conforti et al, I've sniped the image below. At the bottom of this image there is the remnants of a tableau, presumably from several iterations of the simplex ...
- 892
2
votes
2
answers
329
views
Simplex method for multiple objectives
I am a user of Google OR Tools, which can interface with many LP & MIP solvers, plus it's own SAT based constraint programming solver.
My question, in the context of OR-Tools, is: how should I ...
- 501
3
votes
3
answers
334
views
Question regarding primal Simplex method
Given the following degenerate
optimization problem
\begin{align}\min&\quad c^Tx\\\text{s.t.}&\quad Ax=b,\\&\quad x\ge 0\end{align}
Using primal simplex algorithm (either revised or ...
1
vote
0
answers
84
views
How to incorporate artificial variables into the revised simplex method
Seems like we can convert >= constraints to <=, either by multiplying by -1 or using variable substitution. But for ...
- 171
4
votes
1
answer
381
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 ...
- 137
2
votes
1
answer
282
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 ...
- 137
8
votes
1
answer
265
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 ...
- 81
2
votes
0
answers
169
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 ...
- 155
1
vote
1
answer
104
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
232
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
75
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 ...
- 622
1
vote
0
answers
294
views
How to make unconstrained variables non-negative (as in excel solver) in AMPL?
This is a sequencing problem.
I've got this variables
...
- 11
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
281
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{...
- 133
6
votes
0
answers
103
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? ...
- 622
8
votes
1
answer
234
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 ...
- 622
7
votes
3
answers
378
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 ...
- 892
5
votes
2
answers
735
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,821
5
votes
1
answer
5k
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
1k
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
978
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 ...
- 49
3
votes
2
answers
97
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$.
...
- 161
4
votes
3
answers
169
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 ...
- 41
16
votes
3
answers
2k
views
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 ...
- 616
3
votes
1
answer
929
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, ...
- 133
6
votes
0
answers
222
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
868
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
2
answers
2k
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} \...
- 333
2
votes
0
answers
149
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}
...
- 125
8
votes
2
answers
1k
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
94
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
247
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
138
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 ...
- 125
3
votes
0
answers
360
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 ...
- 668
3
votes
1
answer
258
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
267
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,122
7
votes
2
answers
12k
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 ...
- 213
3
votes
0
answers
46
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 ...
- 131
3
votes
1
answer
696
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
160
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 ...