# Tag Info

## Hot answers tagged linear-programming

### Column generation: decreasing value of restricted master problem

The reduced cost is the instantaneous rate of change as you increase the value of the new variable from 0. The actual impact of the new variable on the objective function is piecewise linear and ...
• 31.9k
Accepted

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

As long as you choose something with a negative reduced cost, the simplex algorithm "works". See https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec13.pdf for examples of ways you can ...
• 2,342
Accepted

### Finding a dual feasible basis for use with the dual simplex algorithm

First of all, off course there are dual phase 1 methods that find a dual feasible basis that is not necessarily primal feasible as a first step in a 2-phase dual simplex method. In Maros: "...
• 2,914
Accepted

### How to call HiGHS solver from python PuLP MIP?

PuLP has an API for HiGHS but that version is not sent to pip yet. For the time being, you should pip install PuLP from Github. See the command taken from their readme below. (ps. You might need to ...
• 236
Accepted

### Non-Integral Optimal Solutions of Totally Unimodular Linear Programs

With presolver and crossover both disabled, the SAS interior point algorithm returns $x_{ij} = 1/n$ for the (TU) problem of sending one unit of flow from node $0$ to node $n+1$ in a directed network ...
• 23.1k

### How to find the product with best specs at least price?

If someone told you that linear programming could be applied to this problem, it could be that they were thinking of Data Envelopment Analysis (DEA), - see Wikipedia. DEA assumes a linear utility, i.e....
Accepted

### How to find the product with best specs at least price?

If you are just choosing between two or more products, it has nothing to do with linear programming. You are looking for a utility function to rank the products. Typically, this presumes that (a) you ...
• 31.9k
Accepted

### Convex not strictly convex!

I think you are confusing two things here. A linear program has a convex feasible region. The term "convex space" refers to an entire vector space, not to a particular region (such as an LP ...
• 31.9k
Accepted

### Flow problem with side constraints: how to eliminate subtours?

Let $S$ be the set of arcs in a subtour of size $4$. No-good cuts are simple but weak: $$\sum_{(i,j)\in S} x_{ij} \le 4 - 1$$ Depending on the objective, you might get by with instead imposing no-...
• 23.1k

### Are optimization results stochastic?

In Gurobi, there is a parameter called seed which "typically leads to different solution paths". But the default value is ...
• 604

### Totally unimodular towards linear programming relaxation

Does a TUM matrix $A$ always have a square submatrix $B$ with determinant $\pm 1?$ Technically, no. A matrix entirely filled with zeroes is TUM but obviously has no nonsingular submatrices. In the ...
• 31.9k
Accepted

### Developing the dual model

Your first dual constraint is wrong. The term $(1-\lambda)\times y^1$ should be included in the left side of the second dual constraint.
• 31.9k
Accepted

### How to enumerate all vertices of a polyhedron as a stream

You can check the lrs software implemented by David Avis from McGill. The software implements the reverse search algorithm described in this serie of papers: Reverse Search: Origins Since the output ...
• 1,700