# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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\}$$
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 ...
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 ...
1 vote
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 ...
275 views

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 ...
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 ...
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, ...
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 ...
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 (...
2k views

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} ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...