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.
32
questions
3
votes
1answer
121 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 ...
2
votes
2answers
92 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$.
...
4
votes
3answers
111 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 ...
1
vote
0answers
101 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}
...
3
votes
1answer
333 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, ...
8
votes
2answers
680 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 ...
2
votes
1answer
87 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 ...
7
votes
0answers
104 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
2answers
182 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 (...
5
votes
1answer
548 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} \...
6
votes
0answers
65 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
0answers
120 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 ...
3
votes
0answers
134 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
1answer
131 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 ...
7
votes
2answers
206 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 ...
7
votes
2answers
7k 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
1answer
115 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 ...
3
votes
0answers
42 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 ...
5
votes
0answers
105 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
1answer
110 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
1answer
489 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$) :
...
6
votes
0answers
59 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
154 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
137 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
171 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
343 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
615 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
1answer
177 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?
18
votes
2answers
374 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)
...
8
votes
2answers
358 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 ...
12
votes
1answer
129 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 \\ & ...
13
votes
3answers
1k 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 ...
